ttw@lanl-a.UUCP (03/08/84)
N = (factor 1) * (factor 2) N = 11111111111111111111111111111111111111111111111111111111111111111111111 factor 1 = 241573142393627673576957439049 factor 2 = 45994811347886846310221728895223034301839 The above factorization of 71 ones was obtained on March 8,1984 by Tony Warnock of Cray Research, Inc., using a Cray X-MP located at Los Alamos National Laboratory. The problem took 9.5 hrs using a single CPU. The code was written by Diane Holdridge and Jim Davis of Sandia National Laboratory in Albuquerque and Tony Warnock of Cray Reasearch, Inc. The code used the Quadratic Sieve method of Carl Pomerance.
pmontgom@sdcrdcf.UUCP (Peter Montgomery) (03/12/84)
As previously announced, 10**71-1 = 9 * p * q where
p = 241573142393627673576957439049
q = 45994811347886846310221728895223034301839
have 30 and 41 digits respectively.
Neither factor could readily be found by the p-1 or p+1 methods
(which work only if p-1 or p+1 has only prime factors), since
p-1 = 8 * 71 * 6553 * 64902308585044285054087
p+1 = 2 * 27 * 25 * 19 * 29 * 359 * 111613907 * 8104953397181
q-1 = 2 * 27 * 13 * 71 * 79 * 212881 * 9299909 * 5900253744024168150829
q+1 = 16 * 5 * 1459 * 2239 * 29917 * 66740494766237 * 88145877611537
Whereas the factorization of (10**71-1)/9 was done by Quadratic Sieve,
all four above factorizations were obtained by trial division, by Monte
Carlo (also known as Pollard Rho), or by p-1. For example,
88145877611537-1 = 16 * 17 * 37 * 757 * 2143 * 5399.
--
Peter Montgomery
{bli,blix,bmcg,burdvax,cbosgd,csun,hplabs,hughes,ihnp4,ihnss,
netvax,orstcs,parallax,randvax,sdccsu3,sdcnet,sdcsvax,slant45,
trw-unix,ucla-s,ucla-vax}!sdcrdcf!pmontgompeters@cubsvax.UUCP (03/14/84)
Is this result interesting for any reason other than
as a computational *tour de force*? (I'm not knocking it...
I'm just curious.)
{philabs,cmcl2!rocky2}!cubsvax!peters Peter S. Shenkin
Dept of Biol. Sci.; Columbia Univ.; New York, N. Y. 10027; 212-280-5517paul@uiucuxc.UUCP (03/21/84)
#R:lanl-a:-311700:uiucuxc:27700001:000:463
uiucuxc!paul Mar 20 17:16:00 1984
A hardware implementation of the Quadratic Sieve, tuning the algorithm,
and/or moving it to a faster machine could eventually factor the keys
used in the RSA public key crypto-system. I believe the number factored
has been on a "most-wanted" list for several years.
Paul Pomes
uucp: {decvax,ihnp4,pur-ee,ucbvax}!uiucdcs!uiucuxc!paul
US Mail: Paul Pomes, University of Illinois
1304 W Springfield, Urbana, IL 61801
Phone: 217-333-6262