Factoring large integers
R. Sherman Lehman
Source record
Source: Crossref
Published: Jan 1, 1974
DOI: 10.1090/s0025-5718-1974-0340163-2
Open original source ↗Source abstract
A modification of Fermat’s difference of squares method is used for factoring large integers. This modification permits factoring n in O ( n 1 / 3 ) O({n^{1/3}}) elementary operations, where addition, subtraction, multiplication, division, or the extraction of a square root is considered as an elementary operation. A principal part is played by the use of a dissection of the continuum similar to the Farey dissection. This has been programmed for n ≦ 1.05 × 10 20 n \leqq 1.05 \times {10^{20}} on the CDC 6400.
Evidence graph
No public relationships recorded yet.
Integrity note: This page is a factual metadata record created by deterministic ingestion. It is not a claim that the work moves a mathematical frontier or has been independently verified.