Abstract
We present an algorithm that computes the product of two $n$-bit integers in $O(n \log n)$ bit operations, thus confirming a conjecture of Schönhage and Strassen from 1971. Our complexity analysis takes place in the multitape Turing machine model, with integers encoded in the usual binary representation. Central to the new algorithm is a novel “Gaussian resampling” technique that enables us to reduce the integer multiplication problem to a collection of multidimensional discrete Fourier transforms over the complex numbers, whose dimensions are all powers of two. These transforms may then be evaluated rapidly by means of Nussbaumer’s fast polynomial transforms.
-
[AC-convolution]
R. Agarwal and J. Cooley, "New algorithms for digital convolution," IEEE Trans. Acoustics, Speech, and Signal Process., vol. 25, iss. 5, pp. 392-410, 1977.@ARTICLE{AC-convolution,
author = {Agarwal, R. and Cooley, J.},
title = {New algorithms for digital convolution},
journal = {IEEE Trans. Acoustics, Speech, and Signal Process.},
volume = {25},
number = {5},
year = {1977},
pages = {392--410},
doi = {10.1109/TASSP.1977.1162981},
url = {https://doi.org/10.1109/TASSP.1977.1162981},
zblnumber = {},
} -
[Blu-dft] A. I. Bluestein, "A linear filtering approach to the computation of discrete Fourier transform," IEEE Trans. Audio and Electroacoustics, vol. 18, iss. 4, pp. 451-455, 1970.
@ARTICLE{Blu-dft,
author = {Bluestein, A. I.},
title = {A linear filtering approach to the computation of discrete {F}ourier transform},
journal = {IEEE Trans. Audio and Electroacoustics},
volume = {18},
number = {4},
year = {1970},
pages = {451--455},
doi = {10.1109/TAU.1970.1162132},
url = {https://doi.org/10.1109/TAU.1970.1162132},
zblnumber = {},
} -
[BB-pi-agm] J. M. Borwein and P. B. Borwein, Pi and the AGM, John Wiley & Sons, Inc., New York, 1987.
@BOOK{BB-pi-agm,
author = {Borwein, Jonathan M. and Borwein, Peter B.},
title = {Pi and the {AGM}},
series = {Canadian Math. Soc. Ser. Monogr. Adv. Texts},
note = {A study in analytic number theory and computational complexity, A Wiley-Interscience Publication},
publisher = {John Wiley \& Sons, Inc., New York},
year = {1987},
pages = {xvi+414},
isbn = {0-471-83138-7},
mrclass = {11Y60 (68Q30)},
mrnumber = {0877728},
mrreviewer = {H. London},
zblnumber = {0903.11001},
} -
[BGS-recurrences] A. Bostan, P. Gaudry, and &. Schost, "Linear recurrences with polynomial coefficients and application to integer factorization and Cartier-Manin operator," SIAM J. Comput., vol. 36, iss. 6, pp. 1777-1806, 2007.
@ARTICLE{BGS-recurrences,
author = {Bostan, Alin and Gaudry, Pierrick and Schost, \'{E}ric},
title = {Linear recurrences with polynomial coefficients and application to integer factorization and {C}artier-{M}anin operator},
journal = {SIAM J. Comput.},
fjournal = {SIAM Journal on Computing},
volume = {36},
year = {2007},
number = {6},
pages = {1777--1806},
issn = {0097-5397},
mrclass = {11Y16 (11Y05 68Q25)},
mrnumber = {2299425},
mrreviewer = {Robert Juricevic},
doi = {10.1137/S0097539704443793},
url = {https://doi.org/10.1137/S0097539704443793},
zblnumber = {1210.11126},
} -
[BZ-mca] R. P. Brent and P. Zimmermann, Modern Computer Arithmetic, Cambridge Univ. Press, Cambridge, 2011, vol. 18.
@BOOK{BZ-mca,
author = {Brent, Richard P. and Zimmermann, Paul},
title = {Modern Computer Arithmetic},
series = {Cambridge Monogr. Appl. Comp. Math.},
volume = {18},
publisher = {Cambridge Univ. Press, Cambridge},
year = {2011},
pages = {xvi+221},
isbn = {978-0-521-19469-3},
mrclass = {65Y04},
mrnumber = {2760886},
doi = {10.1017/CBO9780511921698},
url = {https://doi.org/10.1017/CBO9780511921698},
zblnumber = {1230.68014},
} -
[CA-minimum] S. A. Cook and . O. l Aanderaa, "On the minimum computation time of functions," Trans. Amer. Math. Soc., vol. 142, pp. 291-314, 1969.
@ARTICLE{CA-minimum,
author = {Cook, Stephen A. and Aanderaa, {S}t\aa l O.},
title = {On the minimum computation time of functions},
journal = {Trans. Amer. Math. Soc.},
fjournal = {Transactions of the American Mathematical Society},
volume = {142},
year = {1969},
pages = {291--314},
issn = {0002-9947},
mrclass = {94.40},
mrnumber = {0249212},
mrreviewer = {S. Winograd},
doi = {10.2307/1995359},
url = {https://doi.org/10.2307/1995359},
zblnumber = {0188.33402},
} -
[CT-fft] J. W. Cooley and J. W. Tukey, "An algorithm for the machine calculation of complex Fourier series," Math. Comp., vol. 19, pp. 297-301, 1965.
@ARTICLE{CT-fft,
author = {Cooley, James W. and Tukey, John W.},
title = {An algorithm for the machine calculation of complex {F}ourier series},
journal = {Math. Comp.},
fjournal = {Mathematics of Computation},
volume = {19},
year = {1965},
pages = {297--301},
issn = {0025-5718},
mrclass = {65.90},
mrnumber = {0178586},
doi = {10.2307/2003354},
url = {https://doi.org/10.2307/2003354},
zblnumber = {0127.09002},
} -
[CT-zmult] S. Covanov and E. Thomé, "Fast integer multiplication using generalized Fermat primes," Math. Comp., vol. 88, iss. 317, pp. 1449-1477, 2019.
@ARTICLE{CT-zmult,
author = {Covanov, Svyatoslav and Thomé,
Emmanuel},
title = {Fast integer multiplication using generalized {F}ermat primes},
journal = {Math. Comp.},
fjournal = {Mathematics of Computation},
volume = {88},
year = {2019},
number = {317},
pages = {1449--1477},
issn = {0025-5718},
mrclass = {11Y16 (11A41 68W30)},
mrnumber = {3904152},
mrreviewer = {Samuel S. Wagstaff, Jr.},
doi = {10.1090/mcom/3367},
url = {https://doi.org/10.1090/mcom/3367},
zblnumber = {1412.68304},
} -
[CF-DWT] R. Crandall and B. Fagin, "Discrete weighted transforms and large-integer arithmetic," Math. Comp., vol. 62, iss. 205, pp. 305-324, 1994.
@ARTICLE{CF-DWT,
author = {Crandall, Richard and Fagin, Barry},
title = {Discrete weighted transforms and large-integer arithmetic},
journal = {Math. Comp.},
fjournal = {Mathematics of Computation},
volume = {62},
year = {1994},
number = {205},
pages = {305--324},
issn = {0025-5718},
mrclass = {11Y11 (11A51 11Y05)},
mrnumber = {1185244},
mrreviewer = {Duncan A. Buell},
doi = {10.2307/2153411},
url = {https://doi.org/10.2307/2153411},
zblnumber = {0839.11065},
} -
[DKSS-intmult] A. De, P. P. Kurur, C. Saha, and R. Saptharishi, "Fast integer multiplication using modular arithmetic," SIAM J. Comput., vol. 42, iss. 2, pp. 685-699, 2013.
@ARTICLE{DKSS-intmult,
author = {De, Anindya and Kurur, Piyush P. and Saha, Chandan and Saptharishi, Ramprasad},
title = {Fast integer multiplication using modular arithmetic},
journal = {SIAM J. Comput.},
fjournal = {SIAM Journal on Computing},
volume = {42},
year = {2013},
number = {2},
pages = {685--699},
issn = {0097-5397},
mrclass = {68W30 (68Q25 68W40)},
mrnumber = {3044110},
doi = {10.1137/100811167},
url = {https://doi.org/10.1137/100811167},
zblnumber = {1271.68247},
} -
[DR-nonequispaced] A. Dutt and V. Rokhlin, "Fast Fourier transforms for nonequispaced data," SIAM J. Sci. Comput., vol. 14, iss. 6, pp. 1368-1393, 1993.
@ARTICLE{DR-nonequispaced,
author = {Dutt, A. and Rokhlin, V.},
title = {Fast {F}ourier transforms for nonequispaced data},
journal = {SIAM J. Sci. Comput.},
fjournal = {SIAM Journal on Scientific Computing},
volume = {14},
year = {1993},
number = {6},
pages = {1368--1393},
issn = {1064-8275},
mrclass = {65T20 (65R10)},
mrnumber = {1241591},
doi = {10.1137/0914081},
url = {https://doi.org/10.1137/0914081},
zblnumber = {0791.65108},
} -
[Fur-faster1] M. Fürer, "Faster integer multiplication," in STOC’07—Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007, pp. 57-66.
@INPROCEEDINGS{Fur-faster1,
author = {F{ü}rer, Martin},
title = {Faster integer multiplication},
booktitle = {S{TOC}'07---{P}roceedings of the 39th {A}nnual {ACM} {S}ymposium on {T}heory of {C}omputing},
pages = {57--66},
publisher = {ACM, New York},
year = {2007},
mrclass = {68W30 (68Q25)},
mrnumber = {2402428},
doi = {10.1145/1250790.1250800},
url = {https://doi.org/10.1145/1250790.1250800},
zblnumber = {1179.68198},
} -
[Fur-faster2] M. Fürer, "Faster integer multiplication," SIAM J. Comput., vol. 39, iss. 3, pp. 979-1005, 2009.
@ARTICLE{Fur-faster2,
author = {F{ü}rer, Martin},
title = {Faster integer multiplication},
journal = {SIAM J. Comput.},
fjournal = {SIAM Journal on Computing},
volume = {39},
year = {2009},
number = {3},
pages = {979--1005},
issn = {0097-5397},
mrclass = {68W30 (68Q25 68W40)},
mrnumber = {2538847},
mrreviewer = {Peter Bürgisser},
doi = {10.1137/070711761},
url = {https://doi.org/10.1137/070711761},
zblnumber = {1192.68926},
} -
[vzGG-compalg3] J. von zur Gathen and J. Gerhard, Modern Computer Algebra, Third ed., Cambridge Univ. Press, Cambridge, 2013.
@BOOK{vzGG-compalg3,
author = {von zur Gathen, Joachim and Gerhard, Jürgen},
title = {Modern {C}omputer {A}lgebra},
edition = {Third},
publisher = {Cambridge Univ. Press, Cambridge},
year = {2013},
pages = {xiv+795},
isbn = {978-1-107-03903-2},
mrclass = {68W30 (11Y05 11Y11 13Pxx)},
mrnumber = {3087522},
doi = {10.1017/CBO9781139856065},
url = {https://doi.org/10.1017/CBO9781139856065},
zblnumber = {1277.68002},
} -
[GKZ-SS] P. Gaudry, A. Kruppa, and P. Zimmermann, "A GMP-based implementation of Schönhage-Strassen’s large integer multiplication algorithm," in ISSAC 2007, ACM, New York, 2007, pp. 167-174.
@INCOLLECTION{GKZ-SS,
author = {Gaudry, Pierrick and Kruppa, Alexander and Zimmermann, Paul},
title = {A {GMP}-based implementation of {S}chönhage-{S}trassen's large integer multiplication algorithm},
booktitle = {I{SSAC} 2007},
pages = {167--174},
publisher = {ACM, New York},
year = {2007},
mrclass = {11Y16 (68W30)},
mrnumber = {2396199},
doi = {10.1145/1277548.1277572},
url = {https://doi.org/10.1145/1277548.1277572},
zblnumber = {1190.68088},
} -
[Goo-fourier] I. J. Good, "The interaction algorithm and practical Fourier analysis," J. Roy. Statist. Soc. Ser. B, vol. 20, pp. 361-372, 1958.
@ARTICLE{Goo-fourier,
author = {Good, I. J.},
title = {The interaction algorithm and practical {F}ourier analysis},
journal = {J. Roy. Statist. Soc. Ser. B},
fjournal = {Journal of the Royal Statistical Society. Series B. Methodological},
volume = {20},
year = {1958},
pages = {361--372},
issn = {0035-9246},
mrclass = {62.00},
mrnumber = {0102888},
mrreviewer = {T. Kitagawa},
doi = {10.1111/j.2517-6161.1958.tb00300.x},
url = {https://doi.org/10.1111/j.2517-6161.1958.tb00300.x},
zblnumber = {0086.12403},
} -
[gmp-6.1.2] T. Granlund, The GNU Multiple Precision Arithmetic Library (Version 6.1.2).
@MISC{gmp-6.1.2,
author = {Granlund, T.},
title = {The {GNU} {M}ultiple {P}recision {A}rithmetic {L}ibrary ({V}ersion 6.1.2)},
url = {http://gmplib.org/},
zblnumber = {},
} -
[Har-truncmul] D. Harvey, Faster truncated integer multiplication, 2017.
@MISC{Har-truncmul,
author = {Harvey, David},
title = {Faster truncated integer multiplication},
arxiv={1703.00640},
year = {2017},
zblnumber = {},
} -
[HvdH-cyclotomic1] D. Harvey and J. van der Hoeven, Faster integer and polynomial multiplication using cyclotomic coefficient rings, 2017.
@misc{HvdH-cyclotomic1,
author = {Harvey, David and van der Hoeven, Joris},
title = {Faster integer and polynomial multiplication using cyclotomic coefficient rings},
arxiv={1712.03693},
year = {2017},
zblnumber = {},
} -
[HvdH-zmatmult] D. Harvey and J. van der Hoeven, "On the complexity of integer matrix multiplication," J. Symbolic Comput., vol. 89, pp. 1-8, 2018.
@ARTICLE{HvdH-zmatmult,
author = {Harvey, David and van der Hoeven, Joris},
title = {On the complexity of integer matrix multiplication},
journal = {J. Symbolic Comput.},
fjournal = {Journal of Symbolic Computation},
volume = {89},
year = {2018},
pages = {1--8},
issn = {0747-7171},
mrclass = {68W30 (68Q17 68W40)},
mrnumber = {3804803},
doi = {10.1016/j.jsc.2017.11.001},
url = {https://doi.org/10.1016/j.jsc.2017.11.001},
zblnumber = {1395.68152},
} -
[HvdH-vanilla] D. Harvey and J. van der Hoeven, "Faster integer multiplication using plain vanilla FFT primes," Math. Comp., vol. 88, iss. 315, pp. 501-514, 2019.
@ARTICLE{HvdH-vanilla,
author = {Harvey, David and van der Hoeven, Joris},
title = {Faster integer multiplication using plain vanilla {FFT} primes},
journal = {Math. Comp.},
fjournal = {Mathematics of Computation},
volume = {88},
year = {2019},
number = {315},
pages = {501--514},
issn = {0025-5718},
mrclass = {11Y16 (68W30 68W40)},
mrnumber = {3854069},
mrreviewer = {Samuel S. Wagstaff, Jr.},
doi = {10.1090/mcom/3328},
url = {https://doi.org/10.1090/mcom/3328},
zblnumber = {1394.68182},
} -
[HvdH-lattice] D. Harvey and J. van der Hoeven, "Faster integer multiplication using short lattice vectors," in Proceedings of the Thirteenth Algorithmic Number Theory Symposium, 2019, pp. 293-310.
@INPROCEEDINGS{HvdH-lattice,
author = {Harvey, David and van der Hoeven, Joris},
title = {Faster integer multiplication using short lattice vectors},
booktitle = {Proceedings of the {T}hirteenth {A}lgorithmic {N}umber {T}heory {S}ymposium},
series = {Open Book Ser.},
volume = {2},
pages = {293--310},
publisher = {Math. Sci. Publ., Berkeley, CA},
year = {2019},
mrclass = {68W40 (11H06 52C07)},
mrnumber = {3952018},
mrreviewer = {Dorothy Bollman},
doi = {10.2140/obs.2019.2.293},
zblnumber = {1394.68182},
} -
[HvdH-cyclotomic2] D. Harvey and J. van der Hoeven, "Faster polynomial multiplication over finite fields using cyclotomic coefficient rings," J. Complexity, vol. 54, p. 101404, 2019.
@ARTICLE{HvdH-cyclotomic2,
author = {Harvey, David and van der Hoeven, Joris},
title = {Faster polynomial multiplication over finite fields using cyclotomic coefficient rings},
journal = {J. Complexity},
fjournal = {Journal of Complexity},
volume = {54},
year = {2019},
pages = {101404, 18pp.},
issn = {0885-064X},
mrclass = {65Y20 (12Y05 65T60)},
mrnumber = {3983215},
doi = {10.1016/j.jco.2019.03.004},
url = {https://doi.org/10.1016/j.jco.2019.03.004},
zblnumber = {1423.12010},
} -
[HvdH-ffnlogn] D. Harvey and J. van der Hoeven, Polynomial multiplication over finite fields in time $O(n\log n)$, 2019.
@misc{HvdH-ffnlogn,
author = {Harvey, David and van der Hoeven, Joris},
title={Polynomial multiplication over finite fields in time {$O(n\log n)$}},
note={HAL preprint},
url={http://hal.archives-ouvertes.fr/hal-02070816},
year={2019},
} -
[HvdHL-mul] D. Harvey, J. van der Hoeven, and G. Lecerf, "Even faster integer multiplication," J. Complexity, vol. 36, pp. 1-30, 2016.
@ARTICLE{HvdHL-mul,
author = {Harvey, David and van der Hoeven, Joris and Lecerf, Grégoire},
title = {Even faster integer multiplication},
journal = {J. Complexity},
fjournal = {Journal of Complexity},
volume = {36},
year = {2016},
pages = {1--30},
issn = {0885-064X},
mrclass = {65Y20 (11Y16 65T50 65Y04 68Q25)},
mrnumber = {3530637},
mrreviewer = {Jaumin E. Ajdari},
doi = {10.1016/j.jco.2016.03.001},
url = {https://doi.org/10.1016/j.jco.2016.03.001},
zblnumber = {1350.68145},
} -
[HvdHL-ffmul] D. Harvey, J. van der Hoeven, and G. Lecerf, "Faster polynomial multiplication over finite fields," J. ACM, vol. 63, iss. 6, p. 52, 2017.
@ARTICLE{HvdHL-ffmul,
author = {Harvey, David and van der Hoeven, Joris and Lecerf, Grégoire},
title = {Faster polynomial multiplication over finite fields},
journal = {J. ACM},
fjournal = {Journal of the ACM},
volume = {63},
year = {2017},
number = {6},
pages = {Art. 52, 23},
issn = {0004-5411},
mrclass = {94A60 (12Y05 68Q25)},
mrnumber = {3614860},
mrreviewer = {Jaumin E. Ajdari},
doi = {10.1145/3005344},
url = {https://doi.org/10.1145/3005344},
zblnumber = {1426.68310},
} -
[HB-linnik] D. R. Heath-Brown, "Zero-free regions for Dirichlet $L$-functions, and the least prime in an arithmetic progression," Proc. London Math. Soc. (3), vol. 64, iss. 2, pp. 265-338, 1992.
@ARTICLE{HB-linnik,
author = {Heath-Brown, D. R.},
title = {Zero-free regions for {D}irichlet {$L$}-functions, and the least prime in an arithmetic progression},
journal = {Proc. London Math. Soc. (3)},
fjournal = {Proceedings of the London Mathematical Society. Third Series},
volume = {64},
year = {1992},
number = {2},
pages = {265--338},
issn = {0024-6115},
mrclass = {11N13 (11M26)},
mrnumber = {1143227},
mrreviewer = {Andrew Granville},
doi = {10.1112/plms/s3-64.2.265},
url = {https://doi.org/10.1112/plms/s3-64.2.265},
zblnumber = {0739.11033},
} -
[HJB-gauss-fft] M. T. Heideman, D. H. Johnson, and S. C. Burrus, "Gauss and the history of the fast Fourier transform," Arch. Hist. Exact Sci., vol. 34, iss. 3, pp. 265-277, 1985.
@ARTICLE{HJB-gauss-fft,
author = {Heideman, Michael T. and Johnson, Don H. and Burrus, C. Sidney},
title = {Gauss and the history of the fast {F}ourier transform},
journal = {Arch. Hist. Exact Sci.},
fjournal = {Archive for History of Exact Sciences},
volume = {34},
year = {1985},
number = {3},
pages = {265--277},
issn = {0003-9519},
mrclass = {01A55 (42-03 65T05)},
mrnumber = {0815154},
mrreviewer = {Garry J. Tee},
doi = {10.1007/BF00348431},
url = {https://doi.org/10.1007/BF00348431},
zblnumber = {0577.01027},
} -
[vdH-relaxed] J. van der Hoeven, "Faster relaxed multiplication," in ISSAC 2014—Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, 2014, pp. 405-412.
@INPROCEEDINGS{vdH-relaxed,
author = {van der Hoeven, Joris},
title = {Faster relaxed multiplication},
booktitle = {I{SSAC} 2014---{P}roceedings of the 39th {I}nternational {S}ymposium on {S}ymbolic and {A}lgebraic {C}omputation},
pages = {405--412},
publisher = {ACM, New York},
year = {2014},
mrclass = {68W30 (13F25 65D99 65Y20 68Q25)},
mrnumber = {3239953},
doi = {10.1145/2608628.2608657},
url = {https://doi.org/10.1145/2608628.2608657},
zblnumber = {1325.68305},
} -
[vdH:chinese] J. van der Hoeven, Faster Chinese remaindering, 2016.
@MISC{vdH:chinese,
author = {van der Hoeven, Joris},
title = {Faster {Chinese} remaindering},
note = {HAL preprint},
url = {http://hal.archives-ouvertes.fr/hal-01403810},
year = {2016},
} -
[Knu-TAOCP3] D. E. Knuth, The Art of Computer Programming. Vol. 3, Addison-Wesley, Reading, MA, 1998.
@BOOK{Knu-TAOCP3,
author = {Knuth, Donald E.},
title = {The Art of Computer Programming. {V}ol. 3},
note = {Sorting and searching, Second edition \mr{0445948}},
publisher = {Addison-Wesley, Reading, MA},
year = {1998},
pages = {xiv+780},
isbn = {0-201-89685-0},
mrclass = {68-02},
mrnumber = {3077154},
zblnumber = {},
} -
[Nus-conv] H. J. Nussbaumer, "Fast polynomial transform algorithms for digital convolution," IEEE Trans. Acoust. Speech Signal Process., vol. 28, iss. 2, pp. 205-215, 1980.
@ARTICLE{Nus-conv,
author = {Nussbaumer, Henri J.},
title = {Fast polynomial transform algorithms for digital convolution},
journal = {IEEE Trans. Acoust. Speech Signal Process.},
fjournal = {Institute of Electrical and Electronics Engineers. Transactions on Acoustics, Speech, and Signal Processing},
volume = {28},
year = {1980},
number = {2},
pages = {205--215},
issn = {0096-3518},
mrclass = {94A05 (65F99)},
mrnumber = {0563380},
doi = {10.1109/TASSP.1980.1163372},
url = {https://doi.org/10.1109/TASSP.1980.1163372},
zblnumber = {0524.65093},
} -
[NQ-polynomial] H. J. Nussbaumer and P. Quandalle, "Computation of convolutions and discrete Fourier transforms by polynomial transforms," IBM J. Res. Develop., vol. 22, iss. 2, pp. 134-144, 1978.
@ARTICLE{NQ-polynomial,
author = {Nussbaumer, Henri J. and Quandalle, P.},
title = {Computation of convolutions and discrete {F}ourier transforms by polynomial transforms},
journal = {IBM J. Res. Develop.},
fjournal = {International Business Machines Corporation. Journal of Research and Development},
volume = {22},
year = {1978},
number = {2},
pages = {134--144},
issn = {0018-8646},
mrclass = {65D15 (65T05)},
mrnumber = {0471260},
mrreviewer = {Y. L. Luke},
doi = {10.1147/rd.222.0134},
url = {https://doi.org/10.1147/rd.222.0134},
zblnumber = {0379.65062},
} -
[NQ-dfts] H. J. Nussbaumer and P. Quandalle, "Fast computation of discrete Fourier transforms using polynomial transforms," IEEE Trans. Acoust. Speech Signal Process., vol. 27, iss. 2, pp. 169-181, 1979.
@ARTICLE{NQ-dfts,
author = {Nussbaumer, Henri J. and Quandalle, Philippe},
title = {Fast computation of discrete {F}ourier transforms using polynomial transforms},
journal = {IEEE Trans. Acoust. Speech Signal Process.},
fjournal = {Institute of Electrical and Electronics Engineers. Transactions on Acoustics, Speech, and Signal Processing},
volume = {27},
year = {1979},
number = {2},
pages = {169--181},
issn = {0096-3518},
mrclass = {94A11},
mrnumber = {0523618},
doi = {10.1109/TASSP.1979.1163216},
url = {https://doi.org/10.1109/TASSP.1979.1163216},
zblnumber = {0443.65109},
} -
[Pap-complexity] C. H. Papadimitriou, Computational Complexity, Addison-Wesley Publ. Co., Reading, MA, 1994.
@BOOK{Pap-complexity,
author = {Papadimitriou, Christos H.},
title = {Computational Complexity},
publisher = {Addison-Wesley Publ. Co., Reading, MA},
year = {1994},
pages = {xvi+523},
isbn = {0-201-53082-1},
mrclass = {68Q15 (68-02 68Q25)},
mrnumber = {1251285},
mrreviewer = {Johan H\aa stad},
zblnumber = {0833.68049},
} -
[PFM-overlap] M. S. Paterson, M. J. Fischer, and A. R. Meyer, "An improved overlap argument for on-line multiplication," in Complexity of Computation, 1974, pp. 97-111. siam.
@INPROCEEDINGS{PFM-overlap,
author = {Paterson, Michael S. and Fischer, Michael J. and Meyer, Albert R.},
title = {An improved overlap argument for on-line multiplication},
booktitle = {Complexity of Computation},
venue = {{P}roc. {S}ympos., {N}ew {Y}ork, 1973},
pages = {97--111. SIAM-AMS Proc., Vol. VII},
year = {1974},
mrclass = {68A20},
mrnumber = {0423875},
mrreviewer = {Maurice Mignotte},
zblnumber = {},
} -
[Pol-ntt] J. M. Pollard, "The fast Fourier transform in a finite field," Math. Comp., vol. 25, pp. 365-374, 1971.
@ARTICLE{Pol-ntt,
author = {Pollard, J. M.},
title = {The fast {F}ourier transform in a finite field},
journal = {Math. Comp.},
fjournal = {Mathematics of Computation},
volume = {25},
year = {1971},
pages = {365--374},
issn = {0025-5718},
mrclass = {65T05},
mrnumber = {0301966},
mrreviewer = {P. J. Nicholson},
doi = {10.2307/2004932},
url = {https://doi.org/10.2307/2004932},
zblnumber = {0221.12015},
} -
[Rad-prime] C. M. Rader, "Discrete Fourier transforms when the number of data samples is prime," Proc. IEEE, vol. 56, iss. 6, pp. 1107-1108, 1968.
@ARTICLE{Rad-prime,
author = {Rader, C. M.},
title = {Discrete {Fourier} transforms when the number of data samples is prime},
journal = {Proc. IEEE},
volume = {56},
number = {6},
year = {1968},
pages = {1107--1108},
doi = {10.1109/PROC.1968.6477},
url = {https://doi.org/10.1109/PROC.1968.6477},
zblnumber = {},
} -
[RS-primes] B. J. Rosser and L. Schoenfeld, "Approximate formulas for some functions of prime numbers," Illinois J. Math., vol. 6, pp. 64-94, 1962.
@ARTICLE{RS-primes,
author = {Rosser, J. Barkley and Schoenfeld, Lowell},
title = {Approximate formulas for some functions of prime numbers},
journal = {Illinois J. Math.},
fjournal = {Illinois Journal of Mathematics},
volume = {6},
year = {1962},
pages = {64--94},
issn = {0019-2082},
mrclass = {10.42},
mrnumber = {0137689},
mrreviewer = {B. K. Ghosh},
doi = {10.1215/ijm/1255631807},
url = {https://doi.org/10.1215/ijm/1255631807},
zblnumber = {0122.05001},
} -
[SS-multiply] A. Schönhage and V. Strassen, "Schnelle Multiplikation grosser Zahlen," Computing (Arch. Elektron. Rechnen), vol. 7, pp. 281-292, 1971.
@ARTICLE{SS-multiply,
author = {Schönhage, A. and Strassen, V.},
title = {Schnelle {M}ultiplikation grosser {Z}ahlen},
journal = {Computing (Arch. Elektron. Rechnen)},
fjournal = {Computing. Archiv für Elektronisches Rechnen. Archives for Electronic Computing},
volume = {7},
year = {1971},
pages = {281--292},
issn = {0010-485X},
mrclass = {68A20},
mrnumber = {0292344},
doi = {10.1007/bf02242355},
url = {https://doi.org/10.1007/bf02242355},
zblnumber = {},
} -
[Sip-computation] M. Sipser, Introduction to the Theory of Computation, 2nd ed., , 2006.
@BOOK{Sip-computation,
author = {Sipser, Michael},
title = {Introduction to the Theory of Computation},
titlenote = {Thomson Course Technology},
year = {2006},
edition = {2nd},
zblnumber = {},
} -
[Tho-physics] L. H. Thomas, "Using computers to solve problems in physics," Appl. Digital Computers, vol. 458, pp. 42-57, 1963.
@ARTICLE{Tho-physics,
author = {Thomas, L. H.},
title = {Using computers to solve problems in physics},
journal = {Appl. Digital Computers},
volume = {458},
year = {1963},
pages = {42--57},
zblnumber = {},
} -
[Xyl-linnik] T. Xylouris, "On the least prime in an arithmetic progression and estimates for the zeros of Dirichlet $L$-functions," Acta Arith., vol. 150, iss. 1, pp. 65-91, 2011.
@ARTICLE{Xyl-linnik,
author = {Xylouris, Triantafyllos},
title = {On the least prime in an arithmetic progression and estimates for the zeros of {D}irichlet {$L$}-functions},
journal = {Acta Arith.},
fjournal = {Acta Arithmetica},
volume = {150},
year = {2011},
number = {1},
pages = {65--91},
issn = {0065-1036},
mrclass = {11N13 (11M06)},
mrnumber = {2825574},
mrreviewer = {S. W. Graham},
doi = {10.4064/aa150-1-4},
url = {https://doi.org/10.4064/aa150-1-4},
zblnumber = {1248.11067},
}
Full Article