Some parallel algorithms for integer factorisation

DOI10.1007/3-540-48311-X_1MaRDI QIDQ4945780zbMATH OpenFDO

Authors Richard P. Brent

Publication date 19 October 2000

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-48311-X_1

zbMATH Keywords

elliptic curve methodfactoringnumber field sievesurvey

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to number theory (11-02) Factorization (11Y05) Number-theoretic algorithms; complexity (11Y16) Parallel algorithms in computer science (68W10) Symbolic computation and algebraic computation (68W30)

Review text

This paper surveys all the current methods used to factor numbers. It starts with a discussion of the relevant machine arithmetic and then goes on to discuss methods such as Pollard's rho and \(p-1\) method. Then the author discusses Lenstra's elliptic curve method (ECM), which is based on the \(p-1\) method. Various aspects of ECM are discussed including the implementation on a parallel machine and the second phase of the ECM algorithm. Finally the author discusses the three main modern sieve based algorithms, namely the multi-polynomial quadratic sieve (MPQS), the special number field sieve (SNFS) and the general number field sieve (GNFS). A report on the factoization of RSA-140 is given and it is stated that the factorization of RSA-155 is being carried out (a program which has now been completed). For the entire collection see [Zbl 0921.00036].

Cited in

(16)

• Efficient parallel algorithms to test square-freeness and factorize strings
• scientific article; zbMATH DE number 1696618 (Why is no real title available?)
• SIMD-Based Implementations of Sieving in Integer-Factoring Algorithms
• Implementing the Continued Fraction Factoring Algorithm on Parallel Machines
• scientific article; zbMATH DE number 4165009 (Why is no real title available?)
• scientific article; zbMATH DE number 4045819 (Why is no real title available?)
• Parallel implementation of Schönhage's integer GCD algorithm
• scientific article; zbMATH DE number 554529 (Why is no real title available?)
• scientific article; zbMATH DE number 780072 (Why is no real title available?)
• scientific article; zbMATH DE number 1424563 (Why is no real title available?)
• Factoring Numbers on the Massively Parallel Computer
• History of integer factorisation
• scientific article; zbMATH DE number 5492361 (Why is no real title available?)
• An integrated parallel GNFS algorithm for integer factorization based on linbox montgomery block Lanczos method over GF(2)
• A security analysis of two classes of RSA-like cryptosystems
• The case of small prime numbers versus the Okamoto-Uchiyama cryptosystem

Describes a project that uses

Uses Software

• Algorithm 524

This page was built for publication: Some parallel algorithms for integer factorisation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4945780)