bs@faron.UUCP (Robert D. Silverman) (02/19/86)
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 Silvermanapak@oddjob.UUCP (Adrian Kent) (02/21/86)
In article <479@faron.UUCP> bs@faron.UUCP (Robert D. Silverman) writes: >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. [ ...factorisation follows ...] >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 > [......] > 149 >(10) 3 + 1 = 4.C71 > >Bob Silverman This is fascinating. Is it possible to explain where these composite numbers come from? Were/are they bound to have few large factors, or has that been established by trial and error? Are they all extremely simple base n (for some small n) for number-theoretic, computational or sociological reasons? (i.e. are they known to be likely to have few large factors, or are they much easier to work with, or are they just the sort of numbers people are likely to look at?) And is there a committee somewhere which decides the 'most wanted' list? :-) Adrian Kent
bs@faron.UUCP (Robert D. Silverman) (02/23/86)
> In article <479@faron.UUCP> bs@faron.UUCP (Robert D. Silverman) writes: > >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. [ ...factorisation follows ...] > >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 > > > [......] > > 149 > >(10) 3 + 1 = 4.C71 > > > >Bob Silverman > This is fascinating. Is it possible to explain where these composite > numbers come from? Were/are they bound to have few large factors, or has that > been established by trial and error? Are they all extremely simple base n > (for some small n) for number-theoretic, computational or sociological > reasons? (i.e. are they known to be likely to have few large factors, or are > they much easier to work with, or are they just the sort of numbers people are > likely to look at?) And is there a committee somewhere which decides the > 'most wanted' list? :-) > Adrian Kent They come from the 'Cunningham Project'. This is a project started at the turn of the century by Allen Cunningham, an English military officer with an interest in number theory. The project is attempting to factor b^n + 1 and b^n - 1 for bases b = 2, 3, 5, 6, 7, 10, 11, and 12, and various n which depend upon the base b. The American Mathematical Society has published a book on the project entitled 'Factorizations of b^n +/- 1 for b = 2, 3...12 up to high powers'. It is volume 22 in the 'Contemporary Mathematics' series. The most wanted list is kept by mathematicians on the project. Usually John Selfridge, who is editor of Math Reviews decides which numbers go on the list when one is knocked off. By the way, I have already finished (2) on the list, Someone in Germany did (10) and I am currently working on (3). Various investigators have attacked these numbers using a variety of methods. It is a virtual certainty that none have any factors under 20 digits. Anyone who is seeking more info should feel free to write me. Bob Silverman { ihnp4, allegra ... } linus!faron!bs