Primality proving with Gauss and Jacobi sums

• Autorzy: Chmielowiec A.
• Języki publikacji: EN

Abstrakty

EN

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((lnN)Cln ln lnN) for some constant C. This is almost polynomial time since for all practical purposes the function ln ln lnN acts like a constant.

Słowa kluczowe

EN

prime numbers; primality proving; cyclotomic ring; Gauss sum; Jacobi sum; APR

• Wydawca: Instytut Łączności - Państwowy Instytut Badawczy
• Czasopismo: Journal of Telecommunications and Information Technology
• Rocznik: 2004
• Tom: nr 4
• Strony: 69--75
• Opis fizyczny: Bibliogr. 9 poz., tab.

Twórcy

autor

Chmielowiec A.

• Enigma Information Security Systems Sp. z o.o., Cietrzewia st 8, 02-492 Warsaw, Poland,

Bibliografia

• [1] M. Agrawal, N. Kayal, and N. Saxena, "Technical report", Department of Computer Science and Engineering Indian Institute of Technology, Kanpur, 2002.
• [2] O. Atkin and F. Morain, "Elliptic curves and primality proving", A.M.S., vol. 61, pp. 29-68, 1993.
• [3] L. Adleman, C. Pomerance, and R. Rumely, "On distinguishing prime numbers from composite numbers", Ann. Math., vol. 117, pp. 173-206, 1983.
• [4] E. Bach and J, Schallit, Algorithmic Number Theory. Cambridge: MIT Press, 1996.
• [5] W. Bosma and M. van der Hulst, "Primality proving with cyclotomy", Ph.D. thesis, Amsterdam, University of Amsterdam, 1990.
• [6] H. Cohen, A Course in Computational Algebraic Number Theory. Berlin: Springer-Verlag, 1993.
• [7] R. Crandall and C. Pomerance, Prime Numbers: A Computational Perspetive. New York: Springer-Verlag, 2001.
• [8] K. Ireland and M. Rosen, A classical Introduction to Modern Number Theory. New York: Springer-Verlag, 1990.
• [9] J. Rotman, Galois Theory. New York: Springer-Verlag, 1990.