| 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 |
From: ROLL::USENET "USENET Newsgroup Distributor" 9-MAR-1984 22:07
To: HARE::STAN
Subj: USENET net.math newsgroup articles
Newsgroups: net.crypt,net.math
Path: decwrl!decvax!harpo!eagle!mhuxl!houxm!hogpc!houti!ariel!vax135!floyd!cmcl2!lanl-a!ttw
Subject: factors of seventy-one ones
Posted: Thu Mar 8 12:20:59 1984
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.
| T.R | Title | User | Personal Name | Date | Lines |
|---|---|---|---|---|---|
| 49.1 | HARE::STAN | Tue Mar 13 1984 22:49 | 33 | ||
Newsgroups: net.crypt,net.math
Path: decwrl!decvax!mcnc!unc!ulysses!mhuxl!ihnp4!zehntel!hplabs!sdcrdcf!pmontgom
Subject: Re: factors of seventy-one ones
Posted: Sun Mar 11 14:29:41 1984
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
[[[I think he meant to say "only small prime factors" - STAN.]]]
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!pmontgom
| |||||