| <<< VMSZOO::FOLKD$:[NOTES$LIBRARY]FACTOR.NOTE;1 >>>
-< Factoring Notes File >-
================================================================================
Note 15.16 Factor Results 16 of 16
COOKIE::DEVINE "Bob Devine, CXN" 46 lines 15-NOV-1991 13:55
-< first 40 digit factor with ecm >-
--------------------------------------------------------------------------------
From: [email protected] (Arjen Lenstra)
Newsgroups: news.admin,sci.crypt
Subject: Factoring: new elliptic curve record
Summary: first 40 digit factor with ecm
Date: 28 Oct 91 16:39:04 GMT
Organization: Bellcore, Morristown NJ
Using the elliptic curve methode we found that
9672778567495250911624097345072472518224447709518333734291493291045133587\
5400082728125979 (89 digits)
equals
1232079689567662686148201863995544247703 (40 digits)
* 78507734924917342278622201969372653526213641483293 (50 digits).
As far as we know this is the first time that a 40-digit factor has been
found with the elliptic curve method. The previous largest primes discovered
with the elliptic curve method have 38 digits (this occurred three times).
The 89-digit number above is a factor of the 114-digit 11279th partition
number.
The factorization was found after a 18.5 hour run on a 16K MasPar. We ran
1408 curves in parallel, with first stage limit 10^6; the factor was found at
p=1208269 in the second stage.
For information on the elliptic curve method, see the Chapter `Algorithms
in Number Theory' in the Handbook of Theoretical Computer Science, Elsevier,
Amsterdam, 1990, or see Carl Pomerance's survey on Factoring in the AMS
short course lecture notes on Cryptology and Computational Number Theory, 1990.
The 16K MasPar is a massively parallel SIMD machine, consisting of 128x128
processing elements of approximately 0.2 MIPS each. For our elliptic curve
implementation we partitioned each row of 128 processors in 11 blocks of 11
consecutive processors (and 7 idle processors; the number of blocks per row,
and the block size depend on the size of n, the number being factored). This
gives a total of 128*11=1408 useful blocks. A block can carry out one
multiplication mod n in approximately 0.003 seconds, using a parallelized
(systolic) implementation of the so-called `Montgomery multiplication.' Each
block processes its own elliptic curve, independent of but simultaneous with
the other blocks. The factor search is done at regular intervals: the product
modulo n of all candidates is computed on the processor array, and the (much
faster) frontend does a single greatest common divisor computation.
Arjen K. Lenstra, Brandon Dixon
Bellcore
|