Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site faron.UUCP
Path: utzoo!linus!faron!bs
From: bs@faron.UUCP (Robert D. Silverman)
Newsgroups: net.math
Subject: New Factorization Record!!!
Message-ID: <479@faron.UUCP>
Date: Wed, 19-Feb-86 08:53:09 EST
Article-I.D.: faron.479
Posted: Wed Feb 19 08:53:09 1986
Date-Received: Thu, 20-Feb-86 00:04:27 EST
Distribution: net
Organization: The MITRE Coporation, Bedford, MA
Lines: 99

A new factoring record has just been set: I have factored a 75 digit cofactor
 
    128
of 6   + 1 using an enhanced version of Carl Pomerance's Quadratic Sieve
Algorithm. For more information about the algorithm see "The Multiple
Polynomial Quadratic Sieve", forthcoming in 'Mathematics of Computation'
or write me and I'll send a pre-print.
 
 128
6   + 1 had several known small factors and a large composite cofactor of 75
digits: (indicated by the C75)

 128
6   + 1 = 257.763649.50307329.3191106049.C75
 
The final factorization is:

C75 = p22.p25.p29

p22 = 2339340566463317436161
p25 = 2983028405608735541756929
p29 = 18247770097021321924017185281

It was achieved via the following constructed two quadratic congruences:

A = 36697033087866895787902372987102995224438487812216744752455132297302464556
Q = 104751124185950271704324028624325211493136142060427597966271586760506406201
 
A^2 MOD C75 = 33608819099998127794297859172805958867780092740635998676720755890186663825
Q^2 MOD C75 = 33608819099998127794297859172805958867780092740635998676720755890186663825
 
A + Q = 141448157273817167492226401611428206717574629872644342718726719057808870757
A GCD computation yields: 18247770097021321924017185281
A - Q = 68054091098083375916421655637222216268697654248210853213816454463203941645
A GCD computation yields: 6978319360152906049680045864993711701736909569
 
 
And
 
A = 51357644647139204313407001400387669990561118654713340415717400044802941099
Q = 124246497227830068508302374117041121916231348837222813624175525550081602669
A^2 MOD C75 = 127173665218864292579301171262177713766152094030815764925760663191132106409
Q^2 MOD C75 = 127173665218864292579301171262177713766152094030815764925760663191132106409
A + Q = 175604141874969272821709375517428791906792467491936154039892925594884543768
A GCD computation yields: 42687748835458244200805852305768070980096626346241
A - Q = 72888852580690864194895372716653451925670230182509473208458125505278661570
A GCD computation yields: 2983028405608735541756929
 
The factorization was done via a parallel implementation of the Quadratic
Sieve algorithm running simultaneously on a VAX/8650 and a VAX/780. The
VAX/8650 did about 85% of the work in 235 hours. 
 

Larger numbers than this have actually been factored but the algorithms
which were used dependended upon being lucky for their success. Also,
those numbers were all the product of a relatively small number and a
very large one. This is the largest number ever split into two large
prime factors by a deterministic algorithm.

For the ambitious among you I present a list of the numbers currently
on the '10 MOST WANTED' list to be factored: (Cxx means a composite number 
of xx digits)


     512
(1) 2   + 1 = 2424833.C148

     227   114
(2) 2   - 2   + 1 = 5.C68

      73
(3) 10  + 1 = 293.C70

     128
(4) 5   + 1 = 2.257.C87

     128
(5) 6   + 1 = SEE ABOVE
 
     128
(6) 7   + 1 = 2.257.769.197231873.C95

     272
(7) 2   + 1 = 5441.65537.C74

      83
(8) 10  - 1 = 3367147378267.C70

      97
(9) 10  - 1 = 12004721.C89

      149
(10) 3   + 1 = 4.C71

I hope to do (2) (3) and (8) above fairly soon. None of the above have any 
small factors as  determined by the Elliptic Curve algorithm and Pollard P-1.
 

Bob Silverman