Factoring integers
type: Item
instance of: scholarly article
zbMATH Open document ID: 1001.11054
author: Pedro Ricardo López Bautista
publication date: 2001-07-01T00:00:00Z
Mathematics Subject Classification ID: 11Y05
zbMATH DE Number: 1612639
zbMATH Keywords: factoring algorithms
zbMATH Keywords: factoring methods
zbMATH Keywords: quadratic sieve
zbMATH Keywords: number field sieve
zbMATH Keywords: Lenstra's elliptic curve factoring method
describes a project that uses: UBASIC
MaRDI profile type: Publication
title: Factoring integers
review text: 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].
reviewed by: Juan Tena Ayuso
description: scientific article; zbMATH DE number 1612639