Fast Algorithms for Large-Integer Arithmetic

Richard Crandall () and Carl Pomerance ()
Additional contact information
Richard Crandall: Center for Advanced Computation
Carl Pomerance: Dartmouth University, Department of Mathematics

Chapter Chapter 9 in Prime Numbers, 2001, pp 407-496 from Springer

Abstract: Abstract In this chapter we explore the galaxy of “fast” algorithms that admit of applications in prime number and factorization computations. In modern times, it is of paramount importance to be able to manipulate multiple-precision integers, meaning integers that in practice, on prevailing machinery, have to be broken up into pieces, with machine operations to involve those pieces, with a view to eventual reassembly of desired results. Although multiple-precision addition and subtraction of, integers is quite common in numerical studies, we assume that notions of these very simple fundamental operations are understood, and start with multiplication, which is perhaps the simplest arithmetic algorithm whose classical form admits of genuine enhancements.

Keywords: Fast Fourier Transform; Discrete Fourier Transform; Fast Algorithm; Elliptic Multiplication; Fast Fourier Transform Algorithm (search for similar items in EconPapers)
Date: 2001
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-1-4684-9316-0_9

Ordering information: This item can be ordered from
http://www.springer.com/9781468493160

DOI: 10.1007/978-1-4684-9316-0_9

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().