Primality proving with Gauss and Jacobi sums

Authors

  • Andrzej Chmielowiec Enigma Information Security Systems, Warsaw, Poland

DOI:

https://doi.org/10.26636/jtit.2004.4.262

Keywords:

prime numbers, primality proving, yclotomic ring, Gauss sum, Jacobi sum, APR

Abstract

This article presents a primality test known as APR (Adleman, Pomerance and Rumely) which was invented in 1980. It was later simplified and improved by Cohen and Lenstra. It can be used to prove primality of numbers with thousands of bits in a reasonable amount of time. The running time of this algorithm for number N is O((ln N) C ln ln ln N) for some constant C. This is almost polynomial time since for all practical purposes the function ln ln ln N acts like a constant.

Downloads

Download data is not yet available.

References

[1] M. Agrawal, N. Kayal, and N. Saxena, "Technical report", Department of Computer Science and Engineering Indian Institute of Technology, Kanpur, 2002.
View in Google Scholar

[2] O. Atkin and F. Morain, "Elliptic curves and primality proving", A.M.S., vol. 61, pp. 29-68, 1993.
View in Google Scholar

[3] L. Adleman, C. Pomerance, and R. Rumely, "On distinguishing prime numbers from composite numbers", Ann. Math., vol. 117, pp. 173-206, 1983.
View in Google Scholar

[4] E. Bach and J, Schallit, Algorithmic Number Theory. Cambridge: MIT Press, 1996.
View in Google Scholar

[5] W. Bosma and M. van der Hulst, "Primality proving with cyclotomy", Ph.D. thesis, Amsterdam, University of Amsterdam, 1990.
View in Google Scholar

[6] H. Cohen, A Course in Computational Algebraic Number Theory. Berlin: Springer-Verlag, 1993.
View in Google Scholar

[7] R. Crandall and C. Pomerance, Prime Numbers: A Computational Perspective. New York: Springer-Verlag, 2001.
View in Google Scholar

[8] K. Ireland and M. Rosen, A classical Introduction to Modern Number Theory. New York: Springer-Verlag, 1990.
View in Google Scholar

[9] J. Rotman, Galois Theory. New York: Springer-Verlag, 1990.
View in Google Scholar

Downloads

Submitted

2023-04-09

Published

2004-12-30

Issue

No. 4 (2004)

Section

ARTICLES FROM THIS ISSUE

License

Copyright (c) 2004 Journal of Telecommunications and Information Technology

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

How to Cite

[1]
A. Chmielowiec, “Primality proving with Gauss and Jacobi sums”, JTIT, vol. 18, no. 4, pp. 69–75, Dec. 2004, doi: 10.26636/jtit.2004.4.262.

Most read articles by the same author(s)