REVIEW PAPER
COMPARISON OF ALGORITHMS FOR FACTORIZATION OF LARGE NUMBERS HAVING SEVERAL DISTINCT PRIME FACTORS
1
Wojskowa Akademia Techniczna im. Jarosława Dąbrowskiego w Warszawie
Publication date: 2014-12-05
SBN 2014;6(2): 151-162
KEYWORDS
ABSTRACT
We present analysis of security of the most known assymetric algorythm RSA
and its modern version MultiPrime RSA. We focused on more precisious estimations of
time complexity of two factorization algorithms: Elliptic Curve Method and General
Number Field Sieve. Additionally for the MultiPrime RSA algorithm we computed the
maximal number of prime factors for given modulus length which does not decrease the
security level.
REFERENCES (17)
1.
I. F. Blake, G. Seroussi, and N. Smart, Elliptic Curves in Cryptography, Cambridge University Press, (1999).
2.
J. Cilleruelo, J. Rue, P. Sarka, and A. Zumalacarregui, The least common multiple of sets of positive integers, ArXiv e-prints arXiv:1112.3013v1 [math.NT], (2011).
3.
Compaq. Cryptography Using Compaq MultiPrime Technology in a Parallel Processing Environment, Compaq, (2000).
5.
J. H. Ellis, The story of non-secret encryption, Available from http://cryptome.org/jya/ellisd..., (1997).
7.
P. Gaudry, A. Kruppa, F. Morain, L. Muller, E. Thom and P. Zimmermann, cado-nfs, An Implementation of the Number Field Sieve Algorithm, Release 1.1, available from http://cado-nfs.gforge. inria.fr/.
8.
W. Geiselmann and R. Steinwandt, A Dedicated Sieving Hardware, In Public Key Cryptography, 6th International Workshop on Practice and Theoryin Public Key Cryptography, PKC 2003 Proceedings, LNCS 2567, pp. 254–266, (2002).
9.
A. Granville Smooth numbers: computational number theory and beyond, In Algorithmic Number Theory MSRI Publications, no. 44: pp. 267–323 (2008).
10.
M. Jason Hinek, On the security of Multi – prime RSA. In J. Mathematical Cryptology, no. 2(2), pp 117–147 (2008).
11.
A. K. Lenstra, Unbelievable Security. Matching AES Security Using Public Key Systems, In Advances in Cryptology - ASIACRYPT 2001, pp 67–86 (2001).
12.
A. K. Lenstra, H. W. Lenstra, M. S. Manasse, and J. M. Pollard, The number field sieve, In Proc 22nd Annual ACM Symposium on the Theory of Computing, pp. 564–572 (1990).
13.
A. K. Lenstra, A. Shamir, J. Tomlinson, and E. Tromer, Analysis of Bernstein’s Factorization Circuit. In Advances in Cryptology – ASIACRYPT 2002, pp. 1–26, (2002).
14.
H. W. Lenstra, Factoring Integers with Elliptic Curves, In The Annals of Mathematics 126 : pp. 649–673 (1987).
15.
C. Pomerance, Smooth numbers and the quadratic sieve, In Algorithmic Number Theory MSRI Publications, no. 44 : pp. 69–81 (2008).
17.
I. Tolkov, Counting points on elliptic curves: Hasse’s theorem and recent developments, http://igor.tolkov.com/essays/..., (2009).
| ISSN: | 2082-2677 |
We process personal data collected when visiting the website. The function of obtaining information about users and their behavior is carried out by voluntarily entered information in forms and saving cookies in end devices. Data, including cookies, are used to provide services, improve the user experience and to analyze the traffic in accordance with the Privacy policy. Data are also collected and processed by Google Analytics tool (more).
You can change cookies settings in your browser. Restricted use of cookies in the browser configuration may affect some functionalities of the website.
You can change cookies settings in your browser. Restricted use of cookies in the browser configuration may affect some functionalities of the website.
