Identyfikatory
Warianty tytułu
Języki publikacji
Abstrakty
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
Rocznik
Tom
Strony
69--75
Opis fizyczny
Bibliogr. 9 poz., tab.
Twórcy
autor
- Enigma Information Security Systems Sp. z o.o., Cietrzewia st 8, 02-492 Warsaw, Poland, achmielowiec@enigma.com.pl
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.
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-BAT3-0013-0012