×
Harvey, David; van der Hoeven, Joris

Polynomial multiplication over finite fields in time \(O(n\log n)\). (English) Zbl 1493.11157

J. ACM 69, No. 2, Article No. 12, 40 p. (2022).

Cited in 9 Documents

MSC:

11Y16 Number-theoretic algorithms; complexity
68M07 Mathematical problems of computer architecture
68W30 Symbolic computation and algebraic computation
11T06 Polynomials over finite fields

Keywords:

polynomial multiplication; integer multiplication; algorithm; complexity bound; FFT; finite field

Citations:

Zbl 1480.11162
Cite Review PDF
Full Text: DOI HAL

References:

[1] Agarwal, R. and Cooley, J.. 1977. New algorithms for digital convolution. IEEE Trans. Acoust., Speech Sig. Process.25, 5 (1977), 392-410. · Zbl 0413.65087
[2] Agrawal, M., Kayal, N., and Saxena, N.. 2004. PRIMES is in P.Ann. Math.160, 2 (2004), 781-793. · Zbl 1071.11070
[3] Barrett, P.. 1987. Implementing the Rivest Shamir and Adleman public key encryption algorithm on a standard digital signal processor. In Proceedings of the Advances in Cryptology Conference. 311-323.
[4] Bluestein, L. I.. 1970. A linear filtering approach to the computation of discrete Fourier transform. IEEE Trans. Aud. Electroacoust.18, 4 (1970), 451-455.
[5] Bostan, A., Gaudry, P., and Schost, É.. 2007. Linear recurrences with polynomial coefficients and application to integer factorization and Cartier-Manin operator. SIAM J. Comput.36 (2007), 1777-1806. · Zbl 1210.11126
[6] Boyer, C. B.. 1985. A History of Mathematics. Princeton University Press. · Zbl 0562.01001
[7] Brent, R. P. and Zimmermann, P.. 2010. Modern Computer Arithmetic. Cambridge University Press. · Zbl 1230.68014
[8] Cantor, D. G. and Kaltofen, E.. 1991. On fast multiplication of polynomials over arbitrary algebras. Acta Inform.28 (1991), 693-701. · Zbl 0766.68055
[9] Cooley, J. W. and Tukey, J. W.. 1965. An algorithm for the machine calculation of complex Fourier series. Math. Comput.19 (1965), 297-301. · Zbl 0127.09002
[10] Covanov, S. and Thomé, E.. 2019. Fast integer multiplication using generalized Fermat primes. Math. Comput.88 (2019), 1449-1477. · Zbl 1412.68304
[11] De, A., Kurur, P. P., Saha, C., and Saptharishi, R.. 2013. Fast integer multiplication using modular arithmetic. SIAM J. Comput.42, 2 (2013), 685-699. · Zbl 1271.68247
[12] Fürer, M.. 2007. Faster integer multiplication. In Proceedings of the 39th ACM Symposium on Theory of Computing.57-66. · Zbl 1179.68198
[13] Fürer, M.. 2009. Faster integer multiplication. SIAM J. Comput.39, 3 (2009), 979-1005. · Zbl 1192.68926
[14] Gathen, J. von zur and Gerhard, J.. 2013. Modern Computer Algebra. (3rd ed.) Cambridge University Press, New York. · Zbl 1277.68002
[15] Good, I. J.. 1958. The interaction algorithm and practical Fourier analysis. J. Roy. Statist. Societ. , Series B.20, 2 (1958), 361-372. · Zbl 0086.12403
[16] Harvey, D.. 2014. Faster arithmetic for number-theoretic transforms. J. Symb. Comput.60 (2014), 113-119. · Zbl 1284.65195
[17] Harvey, D.. 2017. Faster truncated integer multiplication. Retrieved from https://arxiv.org/abs/1703.00640.
[18] Harvey, D. and van der Hoeven, J.. 2017. Faster Integer and Polynomial Multiplication Using Cyclotomic Coefficient Rings. Technical Report. Retrieved from http://arxiv.org/abs/1712.03693. · Zbl 1423.12010
[19] Harvey, D. and van der Hoeven, J.. 2019. Faster integer multiplication using plain vanilla FFT primes. Math. Comput.88, 315 (2019), 501-514. · Zbl 1394.68182
[20] Harvey, D. and van der Hoeven, J.. 2019. Faster integer multiplication using short lattice vectors. In Proceedings of the 13th Algorithmic Number Theory Symposium. 293-310. · Zbl 07721131
[21] Harvey, D. and van der Hoeven, J.. 2019. Faster polynomial multiplication over finite fields using cyclotomic coefficient rings. Shortened version of Reference [18]. Appeared electronically in J. Complex.DOI: .
[22] Harvey, D. and van der Hoeven, J.. 2021. Integer multiplication in time \(O (n \log n) \). Ann. Math.193, 2 (2021), 563-617. · Zbl 1480.11162
[23] Harvey, D., van der Hoeven, J., and Lecerf, G.. 2014. Faster Polynomial Multiplication over Finite Fields. Technical Report. Retrieved from http://arxiv.org/abs/1407.3361. · Zbl 1426.68310
[24] Harvey, D., van der Hoeven, J., and Lecerf, G.. 2016. Even faster integer multiplication. J. Complex.36 (2016), 1-30. · Zbl 1350.68145
[25] Harvey, D., van der Hoeven, J., and Lecerf, G.. 2016. Fast polynomial multiplication over \(\mathbb{F}_{2^{60}} \). In Proceedings of the ACM International Symposium on Symbolic and Algebraic Computation. 255-262. · Zbl 1360.68935
[26] Harvey, D., van der Hoeven, J., and Lecerf, G.. 2017. Faster polynomial multiplication over finite fields. J. ACM63, 6 (2017). · Zbl 1426.68310
[27] Heath-Brown, D. R.. 1992. Zero-free regions for Dirichlet L-functions, and the least prime in an arithmetic progression. Proc. London Math. Societ.64, 3 (1992), 265-338. · Zbl 0739.11033
[28] Heideman, M. T., Johnson, D. H., and Burrus, C. S.. 1985. Gauss and the history of the fast Fourier transform. Arch. Hist. Exact Sci.34, 3 (1985), 265-277. · Zbl 0577.01027
[29] van der Hoeven, J.. 2002. Relax, but don’t be too lazy. J. Symb. Comput.34 (2002), 479-542. · Zbl 1011.68189
[30] van der Hoeven, J.. 2016. Faster Chinese Remaindering. Technical Report. Retrieved from https://hal.archives-ouvertes.fr/hal-01403810.
[31] van der Hoeven, J., R. Larrieu, and Lecerf, G.. 2017. Implementing fast carryless multiplication. In Proceedings of the International Conference on Mathematical Aspects of Computer and Information Sciences, Lect. Notes in Computer Science. Springer International Publishing. · Zbl 1497.68586
[32] Karatsuba, A. A.. 1995. The complexity of computations. Proc. Steklov Inst. Math. 211 (1995), 169-183. English translation. · Zbl 0872.68068
[33] Karatsuba, A. and Ofman, J.. 1963. Multiplication of multidigit numbers on automata. Sov. Phys. Doklady7 (1963), 595-596.
[34] Knuth, D. E.. 1969. The Art of Computer Programming , volume 2: Seminumerical Algorithms. Addison-Wesley. · Zbl 0191.18001
[35] Knuth, D. E.. 1998. The Art of Computer Programming , volume 3: Sorting and Searching. Addison-Wesley, Reading, MA. · Zbl 0895.68054
[36] Lang, S.. 2002. Algebra. Springer Verlag.
[37] Li, J., Pratt, K., and Shakan, G.. 2017. A lower bound for the least prime in an arithmetic progression. Quart. J. Math.68, 3 (2017), 729-758. · Zbl 1426.11091
[38] Linnik, Yu. V.. 1944. On the least prime in an arithmetic progression I. The basic theorem. Rec. Math. (Mat. Sbornik) N.S., 15, 57 (1944), 139-178. · Zbl 0063.03584
[39] Linnik, Yu. V.. 1944. On the least prime in an arithmetic progression II. The Deuring-Heilbronn phenomenon. Rec. Math. (Mat. Sbornik) N.S.15, 57 (1944), 347-368. · Zbl 0063.03585
[40] Neugebauer, O.. 1957. The Exact Sciences in Antiquity. Brown University Press, Providence, R.I. · Zbl 0084.00201
[41] Nussbaumer, H. J.. 1980. Fast polynomial transform algorithms for digital convolution. IEEE Trans. Acoust. Speech Sig. Process.28, 2 (1980), 205-215. · Zbl 0524.65093
[42] Nussbaumer, H. J.. 1982. Fast Fourier Transforms and Convolution Algorithms (2nd. ed.). Springer-Verlag.
[43] Nussbaumer, H. J. and Quandalle, P.. 1978. Computation of convolutions and discrete Fourier transforms by polynomial transforms. IBM J. Res. Develop.22, 2 (1978), 134-144. · Zbl 0379.65062
[44] Papadimitriou, C. H.. 1994. Computational Complexity. Addison-Wesley. · Zbl 0833.68049
[45] Pollard, J. M.. 1971. The fast Fourier transform in a finite field. Math. Comput.25, 114 (1971), 365-374. · Zbl 0221.12015
[46] Rader, C. M.. 1968. Discrete Fourier transforms when the number of data samples is prime. Proc. IEEE 56 (1968), 1107-1108.
[47] Schönhage, A.. 1966. Multiplikation großer zahlen. Computing1, 3 (1966), 182-196. · Zbl 0196.52104
[48] Schönhage, A.. 1977. Schnelle multiplikation von polynomen über körpern der charakteristik 2. Acta Inform.7 (1977), 395-398. · Zbl 0362.65011
[49] Schönhage, A. and Strassen, V.. 1971. Schnelle multiplikation großer zahlen. Computing7 (1971), 281-292. · Zbl 0223.68007
[50] Schost, É.. Multivariate power series multiplication. 2005. In Proceedings of the ACM International Symposium on Symbolic and Algebraic Computation. 293-300 · Zbl 1360.68955
[51] Shoup, V.. 1990. New algorithms for finding irreducible polynomials over finite fields. Math. Comput. 54 (1990), 435-447. · Zbl 0712.11077
[52] Shoup, V.. 1992. Searching for primitive roots in finite fields. Math. Comput. 58 (1992), 369-380. · Zbl 0747.11060
[53] Shparlinski, I.. 1996. On finding primitive roots in finite fields. Theoret. Comput. Sci.157, 2 (1996), 273-275. · Zbl 0871.11091
[54] Smith, D. E.. 1958. History of Mathematics, volume 2. Dover. · Zbl 0081.00411
[55] Thomas, L. H.. 1963. Using computers to solve problems in physics. Applic. Dig. Comput. 458 (1963), 42-57.
[56] Toom, A. L.. 1963. The complexity of a scheme of functional elements realizing the multiplication of integers. Sov. Math.4, 2 (1963), 714-716. · Zbl 0203.15604
[57] Xylouris, T.. 2011. On the least prime in an arithmetic progression and estimates for the zeros of Dirichlet L-functions. Acta Arith.1 (2011), 65-91. · Zbl 1248.11067
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.