Abstract:We present a randomized polynomial-time algorithm to generate an ideal and its factorization uniformly at random in a given number field. We do this by generating a random integer and its factorization according to the distribution of norms of ideals at most $N$ in the given number field. Using this randomly generated norm, we can produce a random factored ideal in the ring of algebraic integers uniformly at random among ideals with norm up to $N$, in randomized polynomial time. We also present a variant of this algorithm for generating random factored ideals in function fields.
- Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, PRIMES is in P, Ann. of Math. (2) 160 (2004), no. 2, 781–793. MR 2123939, DOI 10.4007/annals.2004.160.781
- Eric Bach, Analytic methods in the analysis and design of number-theoretic algorithms, ACM Distinguished Dissertations, MIT Press, Cambridge, MA, 1985. MR 807772
- Eric Bach, How to generate factored random numbers, SIAM J. Comput. 17 (1988), no. 2, 179–193. Special issue on cryptography. MR 935336, DOI 10.1137/0217012
- Alexandre L. Chistov, Efficient factoring polynomials over local fields and its applications, Proceedings of the International Congress of Mathematicians, Vol. I, II (Kyoto, 1990) Math. Soc. Japan, Tokyo, 1991, pp. 1509–1519. MR 1159333
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to algorithms, 2nd ed., MIT Press, Cambridge, MA; McGraw-Hill Book Co., Boston, MA, 2001. MR 1848805
- S. Ikehara, An extension of landau’s theorem in the analytical theory of numbers, Journal of Mathematics and Physics 10 (1931), no. 1-4, 1–12.
- Adam Kalai, Generating random factored numbers, easily, J. Cryptology 16 (2003), no. 4, 287–289. MR 2002046, DOI 10.1007/s00145-003-0051-5
- Donald E. Knuth, The art of computer programming. Vol. 2: Seminumerical algorithms, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1969. MR 0286318
- Noah Lebowitz-Lockard and Carl Pomerance, Generating random factored Gaussian integers, easily, Math. Comp. 85 (2016), no. 297, 503–516. MR 3404459, DOI 10.1090/mcom/3000
- H. W. Lenstra, Jr., Primality testing with gaussian periods, Proceedings of the 22nd Conference Kanpur on Foundations of Software Technology and Theoretical Computer Science (London, UK), FST TCS ’02, Springer-Verlag, 2002.
- J. S. Milne, Algebraic number theory, 2013, Available at www.jmilne.org/math/, p. 161.
- J. Barkley Rosser and Lowell Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962), 64–94. MR 137689
- Zachary Charles
- Affiliation: Department of Mathematics, University of Wisconsin-Madison, Madison, Wisconsin 53706
- MR Author ID: 1002462
- Email: email@example.com
- Received by editor(s): December 14, 2016
- Received by editor(s) in revised form: February 8, 2017
- Published electronically: October 17, 2017
- © Copyright 2017 American Mathematical Society
- Journal: Math. Comp. 87 (2018), 2047-2056
- MSC (2010): Primary 11Y16; Secondary 68Q25
- DOI: https://doi.org/10.1090/mcom/3283
- MathSciNet review: 3787402