Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

Request Permissions   Purchase Content 
 
 

 

Generating random factored Gaussian integers, easily


Authors: Noah Lebowitz-Lockard and Carl Pomerance
Journal: Math. Comp. 85 (2016), 503-516
MSC (2010): Primary 11416; Secondary 65C10, 11K45
DOI: https://doi.org/10.1090/mcom/3000
Published electronically: June 23, 2015
MathSciNet review: 3404459
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, PRIMES is in P, Ann. of Math. (2) 160 (2004), no. 2, 781-793. MR 2123939 (2006a:11170), https://doi.org/10.4007/annals.2004.160.781
  • [2] Eric Bach, How to generate factored random numbers, SIAM J. Comput. 17 (1988), no. 2, 179-193. Special issue on cryptography. MR 935336 (89e:11082), https://doi.org/10.1137/0217012
  • [3] Henri Cohen, A Course in Computational Algebraic Number Theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. MR 1228206 (94i:11105)
  • [4] Richard Crandall and Carl Pomerance, Prime Numbers: A Computational Perspective, 2nd ed., Springer, New York, 2005. MR 2156291 (2006a:11005)
  • [5] Adam Kalai, Generating random factored numbers, easily, J. Cryptology 16 (2003), no. 4, 287-289. MR 2002046 (2004g:11119), https://doi.org/10.1007/s00145-003-0051-5
  • [6] 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.
  • [7] Paul Pollack, Not Always Buried Deep: A Second Course in Elementary Number Theory, American Mathematical Society, Providence, RI, 2009. MR 2555430 (2010i:11003)
  • [8] 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
  • [9] J. Barkley Rosser and Lowell Schoenfeld, Approximate formulas for some functions of prime numbers, Illinois J. Math. 6 (1962), 64-94. MR 0137689 (25 #1139)
  • [10] René Schoof, Elliptic curves over finite fields and the computation of square roots $ \operatorname {mod} p$, Math. Comp. 44 (1985), no. 170, 483-494. MR 777280 (86e:11122), https://doi.org/10.2307/2007968
  • [11] Edwin Weiss, Algebraic Number Theory, McGraw-Hill Book Co., Inc., New York-San Francisco-Toronto-London, 1963. MR 0159805 (28 #3021)
  • [12] S. Wigert, Sur l'ordre de grandeur du nombre des diviseurs d'un entier, Ark. Math., 3 (1906/1907), 1-9.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11416, 65C10, 11K45

Retrieve articles in all journals with MSC (2010): 11416, 65C10, 11K45


Additional Information

Noah Lebowitz-Lockard
Affiliation: Department of Mathematics and Computer Science, Emory University, Atlanta, Georgia 30307
Email: nlebowi@emory.edu

Carl Pomerance
Affiliation: Mathematics Department, Dartmouth College, Hanover, New Hampshire 03755
Email: carl.pomerance@dartmouth.edu

DOI: https://doi.org/10.1090/mcom/3000
Received by editor(s): July 19, 2013
Received by editor(s) in revised form: April 22, 2014
Published electronically: June 23, 2015
Additional Notes: This paper is based on the 2013 senior thesis of the first author written under the direction of the second author at Dartmouth College. The second author was supported in part by NSF grant DMS-1001180.
Article copyright: © Copyright 2015 American Mathematical Society

American Mathematical Society