[Search for users]
[Overall Top Noters]
[List of all Conferences]
[Download this site]
| Title: | Mathematics at DEC |
|
| Moderator: | RUSURE::EDP |
|
| Created: | Mon Feb 03 1986 |
| Last Modified: | Fri Jun 06 1997 |
| Last Successful Update: | Fri Jun 06 1997 |
| Number of topics: | 2083 |
| Total number of notes: | 14613 |
492.0. "factoring" by LATOUR::JMUNZER () Fri May 23 1986 17:15
Massachusetts mathematician - Sets factoring record
The 31-year-old Robert D. Silverman at The Mitre Corp. successfully factored
a number that is 81 digits long. The number:
948,568,795,032,094,272,909,893,509,191,171,341,133,987,714,380,927,500,611,
236,528,192,824,358,010,355,713 - represents an amount more than the estimated
number of atoms in the entire universe. Silverman said mathematicians have
worked on the number, considered one of the world's most wanted numbers to be
factored, without success since the turn of the century.
But the Chelmsford man, using a series of eight computers, solved the
puzzling problem in less than two weeks. As some may recall from high school
algebra, factoring means breaking a number down into its smallest
multiplicands. For example, three and seven are the only factors of 21.
The factors of Silverman's number are three and
424,255,915,796,187,428,893,811 and
745,280,352,191,786,358,209,397,071,708,329,198,285,057,832,384,965,565,161.
Three was easy to determine, the other two were previously unknown. Silverman
attributes his success to a new system for factoring numbers. But he said his
method is not good enough to factor the biggest number on the most-wanted list,
a numeral that has 148 digits. "My method will not do it," he said. "It would
take centuries." The University of Chicago graduate said he has dabbled with
the giant number and will continue trying to break its mystery. Silverman's
accomplishment broke the previous record set in 1984 when a team of
mathematicians at Sandia National Laboratories in Albuquerque, N.M., factored
a 71-digit number. Mitre is an engineering and consulting company that works
for the Pentagon and private corporations in the fields of national defense,
transportation, space and the environment.
{AP News Wires, 16-May-86, 14:56}
| T.R | Title | User | Personal
Name | Date | Lines |
|---|
| 492.1 | "most wanted" list | TAV02::NITSAN | Nitsan Duvdevani, Digital Israel | Mon May 26 1986 07:39 | 7 |
|
What's the up-to-date status of the "most wanted
for factorization" list ?
Meybe we can keep track of it in this note ?
Nitsan
|
| 492.2 | more info on factoring | NACHO::MCMENEMY | Michael G. McMenemy | Mon May 26 1986 23:17 | 104 |
| From: ASHBY::USENET "USENET Newsgroup Distributor 24-May-1986 2146" 24-MAY-1986 22:21
To: @[.net.math]NEWS.DIS
Subj: USENET net.math newsgroup articles
Newsgroups: net.math
Path: decwrl!decvax!bellcore!ulysses!allegra!princeton!caip!lll-crg!seismo!mcvax!zuring!dik
Subject: New factorization record
Posted: 21 May 86 23:47:10 GMT
Organization: CWI, Amsterdam
Posted: Wed May 21 19:47:10 1986
Apparently-To: rnews@mcvax
NEW FACTORIZATION RECORD ON SUPERCOMPUTERS
------------------------------------------
Herman J.J. te Riele, W.M. Lioen and Dik T. Winter
A new factorization record on supercomputers has been settled on May 13,
1986 at the Center for Mathematics and Computer Science (CWI) at Amsterdam.
The number factorized is the 72-digit composite number
10^72 - 10^36 + 1 =
999999999999999999999999999999999999000000000000000000000000000000000001 =
1726290008991504500177463302688697 *
579276943498154282123686999881829009033
These two factors are 34-, resp. 39-digit prime numbers.
The factorized number is one from a list of 20 "more wanted" factorizations
given in a recent update of the book (sometimes called the factor bible):
'Factorizations of b^n +- 1', by John Brillhart, D.H. Lehmer, J.L. Selfridge,
Bryant Tuckerman and S.S Wagstaff, Jr (AMS Contemporary Mathematics Series,
vol. 22, 1983).
Interest in factorization and primality testing has increased dramatically
since the discovery, in 1978, by Rivest, Shamir and Adleman, that the
difficulty of breaking certain cryptographic codes depends on the
difficulty of factorization ([3]).
The method used is the multiple polynomial variant of Peter Montgomery
of the quadratic sieve method of Carl Pomerance as described in a recent
paper by Pomerance, J.W. Smith and R. Tuler ([2]).
The computer used is the 1-pipe CDC CYBER 205 of SARA at Amsterdam (SARA
is the Academic Computer Centre Amsterdam).
The total time used was about 4.3 hours CPU-time. Control Data Benelux has
kindly provided the computer time for this (and other) factorizations.
The method was implemented on the CYBER 205 by a team consisting of
Herman J.J. te Riele, Walter M. Lioen and Dik T. Winter from the Depart-
ment of Numerical Mathematics of the CWI. Advisory help was provided by
J. Schlichting of Control Data.
The previous record for supercomputers was held by J.A. Davis and D.B. Holdridge
from Sandia Labs (USA) who (in 1984) factorized the number (10^71-1)/9
(consisting of 71 1's) on a CRAY X/MP-24 of the Los Alamos Lab (USA)
in 9.5 hours CPU-time, using a variant of the quadratic sieve method
found by Davis ([1]).
This CRAY X/MP is about twice as fast as the CYBER 205 and has four
million words of central memory (the CYBER 205 has one million words).
In the heart of the quadratic sieve algorithm, the data to be
handled are stored in non-contiguous memory locations. This is an
handicap on the CYBER 205.
All this illustrates the power of the Montgomery-variant of Pomerance's
quadratic sieve.
It should be emphasized that larger difficult numbers have been
factorized already by Robert Silverman, who did not use supercomputers,
but VAX and SUN - computers. His records are: a 81-digit composite number
using a total of 1260 hours on 8 SUN-3/75 computers running in parallel,
and a 75-digit composite number using 235 hours on a VAX/8650 and about
40 hours on a VAX/780. He also used the MP-QS method.
A few more details of our algorithm for the initiate:
factor base bound: 130000
number of primes in the factor base: 6071
length of sieving interval: 6*(2^16 - 1)
# of completely factorized w's: 2672
# of incompletely factorized w's: 24747
bound on the large primes allowed in incomplete w's: 30*130000
# of large prime equalities in the incompletely factorized w's: 3401
Gauss elimination time (on a 6073*6072 linear system): 21 sec.
References
----------
1. J.A. DAVIS, D.B. HOLDRIDGE, G.J. SIMMONS(1985). Status report on
factoring (at the Sandia National Laboratories). pp.183-215 in:
T. BETH, N. COT, I. INGEMARSSON (editors). Advances in Cryptology,
Proceedings of EUROCRYPT 84. Springer, Berlin etc.
2. C. POMERANCE, J.W. SMITH, R. TULER(1986). A Pipe-Line Architecture
for Factoring Large Integers with the Quadratic Sieve Algorithm.
Preprint.
3. R. RIVEST, A. SHAMIR, L. ADLEMAN(1978). A method for obtaining digital
signatures and public-key cryptosystems. Comm. ACM 21, 120-126.
--
dik t. winter, cwi, amsterdam, nederland
UUCP: {seismo,decvax,philabs,okstate,garfield}!mcvax!dik
or: [email protected]
ARPA: dik%[email protected]
|
| 492.3 | Current Most Wanted List | CLT::GILBERT | Juggler of Noterdom | Fri May 30 1986 20:49 | 61 |
| From: ASHBY::USENET "USENET Newsgroup Distributor 25-May-1986 2229" 25-MAY-1986 22:31
To: @[.net.math]NEWS.DIS
Subj: USENET net.math newsgroup articles
Newsgroups: net.math,net.crypt
Path: decwrl!pyramid!pesnta!hplabs!hao!seismo!ut-sally!utah-cs!utah-gr!pwa-b!philabs!linus!faron!bs
Subject: Factoring: Most Wanted List
Posted: 23 May 86 02:03:42 GMT
Organization: The MITRE Coporation, Bedford, MA
Xref: decwrl net.math:2996 net.crypt:749
While I continue the process of factoring numbers on the current 'WANTED'
lists I encountered a very rare and unusual event: A very large number
which factored as the product of two VERY nearly equal primes. The
factorization was that of a 77 digit cofactor of 6^106 + 1. This number
has the trivial algebraic factor 37, and a small primitive factor 26713.
The remain cofactor, however, factors as:
175436926004647658810244613736479118917 *
175787157418305877173455355755546870641
A very pretty result.
It not only is unusual for a number this size to factor into two primes
of equal length but also it is even more unusual that the first 3 digits
are the same. Note that this is not an artificially constructed RSA key.
Bob Silverman
P.S. For those interested the current numbers left on the 'MOST WANTED'
list are: (Cxx indicates a composite number of xx digits)
512
1. 2 + 1 = 2424833.C148
128
2. 5 + 1 = 2.257.C87
128
3. 7 + 1 = 2.257.769.197231873.C95
4. finished
5. finished
6. finished
94
7. 10 + 1 = 101.45121.C88
97
8. 10 - 1 = 3.3.12004721.C89
97
9. 10 + 1 = 11.C96
10. finished
Is anyone out there bold enough to try these?????
We are waiting for John Selfridge to draw up a new list.
|