| 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
|