Generating random factored ideals in number fields

Charles, Zachary

doi:10.1090/mcom/3283

Generating random factored ideals in number fields
HTML articles powered by AMS MathViewer

by Zachary Charles PDF

Math. Comp. 87 (2018), 2047-2056 Request permission

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.

References

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