Generating random factored Gaussian integers, easily

Lebowitz-Lockard, Noah; Pomerance, Carl

doi:10.1090/mcom/3000

Generating random factored Gaussian integers, easily
HTML articles powered by AMS MathViewer

by Noah Lebowitz-Lockard and Carl Pomerance;

Math. Comp. 85 (2016), 503-516

DOI: https://doi.org/10.1090/mcom/3000

Published electronically: June 23, 2015

PDF | Request permission

Abstract:

We present a (random) polynomial-time algorithm to generate a random Gaussian integer with the uniform distribution among those with norm at most $N$, along with its prime factorization. The method generalizes to finding a random ideal in the ring of integers of a quadratic number field together with its prime ideal factorization. We also discuss the analogous problem for higher degree number 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, 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
Henri Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. MR 1228206, DOI 10.1007/978-3-662-02945-9
Richard Crandall and Carl Pomerance, Prime numbers, 2nd ed., Springer, New York, 2005. A computational perspective. MR 2156291
Adam Kalai, Generating random factored numbers, easily, J. Cryptology 16 (2003), no. 4, 287–289. MR 2002046, DOI 10.1007/s00145-003-0051-5
E. Landau, Über die Einteilung der positiven ganzen Zahlen in vier Klassen nach der Mindestzahl der zu ihrer additiven Zusammensetzung erforderlichen Quadrate, Arch. Math. Phys., (3) 13 (1908), 305–312; Collected works, Vol. 4, Thales Verlag, Essen, 1986, 59–66.
Paul Pollack, Not always buried deep, American Mathematical Society, Providence, RI, 2009. A second course in elementary number theory. MR 2555430, DOI 10.1090/mbk/068
S. Ramanujan, Highly composite numbers [Proc. London Math. Soc. (2) 14 (1915), 347–409], Collected papers of Srinivasa Ramanujan, AMS Chelsea Publ., Providence, RI, 2000, pp. 78–128. MR 2280858
J. Barkley Rosser and Lowell Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962), 64–94. MR 137689
René Schoof, Elliptic curves over finite fields and the computation of square roots mod $p$, Math. Comp. 44 (1985), no. 170, 483–494. MR 777280, DOI 10.1090/S0025-5718-1985-0777280-6
Edwin Weiss, Algebraic number theory, McGraw-Hill Book Co., Inc., New York-San Francisco-Toronto-London, 1963. MR 159805
S. Wigert, Sur l’ordre de grandeur du nombre des diviseurs d’un entier, Ark. Math., 3 (1906/1907), 1–9.