Factoring integers (Q2721282)

The paper shows a panorama of the best factoring methods that are known. Namely the author examines the quadratic sieve, the number field sieve and Lenstra's elliptic curve factoring method. Previously the author proposed some naive factoring algorithms written in Ubasic (where for instance the Ubasic command \(\text{eul}(N)\) is invoked to calculate the Euler \(\varphi\)-function of \(N\) in order to decide whether the character is prime or composite to \(N\)). NEWLINENEWLINENEWLINEThe paper wants to be self-contained, and therefore it also includes (see section 3) the concepts and mathematical tools that will be needed later. The treatment is elementary, focusing only on the description of each method and neglecting the deepest reasons that make such a method work efficiently. The bibliography is equally succinct. NEWLINENEWLINENEWLINEA serious drawback of the paper is the lack of an estimate of the running time of each algorithm and an explanation as to why the three analyzed methods are better than previous ones. The author deos not comment on (for instance when describing the public key cryptosystem RSA, see section 2) either the different level of computational complexity of the factoring problem or the related primality problem (this last one has been recently proved to be polynomial: see \textit{Agraval, Kayal} and \textit{Saxena}, Prime is in P, Preprint, August 2002).NEWLINENEWLINEFor the entire collection see [Zbl 0948.00027].