mbmonagan@watmum.UUCP (Michael B. Monagan) (11/06/86)
Andrew Granville and I have been working on the First case of Fermat's Last Theorm. Specifically, we are attempting to show that p p p x + y = z there does not exist positive integers x,y and z and a p prime less than 4*10^15 which does not divide x y z, which satisfy the above equation. Part of the proof involves showing that for each prime p dividing integers g[n], p^2 does not divide 2^p - 2. Thus the integers g[n] require factorization. Several of the g[n] are well over 100 digits in length. We have been successful in factoring all but one of these integers using a number of algorithms, including Lenstra's elliptic curve algorithm. However, we are stuck on the 68 digit number below g[34] := 45342330653448983777029327888871061430657597465656786489926540403841; We would very much appreciate any help with factoring this integer.
bs@linus.UUCP (Robert D. Silverman) (11/11/86)
> Andrew Granville and I have been working on the First case of > Fermat's Last Theorm. Specifically, we are attempting to show that > > p p p > x + y = z > > there does not exist positive integers x,y and z and a p prime less than > 4*10^15 which does not divide x y z, which satisfy the above equation. > Part of the proof involves showing that for each prime p dividing > integers g[n], p^2 does not divide 2^p - 2. Thus the integers g[n] > require factorization. Several of the g[n] are well over 100 digits > in length. We have been successful in factoring all but one of these > integers using a number of algorithms, including Lenstra's elliptic > curve algorithm. However, we are stuck on the 68 digit number below > > g[34] := 45342330653448983777029327888871061430657597465656786489926540403841; > > We would very much appreciate any help with factoring this integer. Requested factorization of g[34]: g[34] = p29.p40 p29 = 25153389723864745855749759089 p40 = 1802633010946815056882715618666253700369 Here's the program output showing the factorization: We attempt to factor: 45342330653448983777029327888871061430657597465656786489926540403841 A = 16999184996616252940785689213782620809935150619741922763993048636504 Q = 18041029990771985798524015528315863414776882336628368666057719388677 A^2 MOD N = 18185999599188720912697770109322753456946802098031996053428289818750 Q^2 MOD N = 18185999599188720912697770109322753456946802098031996053428289818750 A + Q = 35040214987388238739309704742098484224712032956370291430050768025181 A GCD computation yields: 1802633010946815056882715618666253700369 A - Q = 1041844994155732857738326314533242604841731716886445902064670752173 A GCD computation yields: 25153389723864745855749759089 Robert Silverman
herman@mcvax.uucp (Herman te Riele) (11/12/86)
Here is the prime factorization of the c68 of Monagan and Granville: 45342330653448983777029327888871061430657597465656786489926540403841 (c68) = 25153389723864745855749759089 (p29) * 1802633010946815056882715618666253700369 (p40) It was found with help of the Multiple Polynomial version of the Quadratic Sieve of Pomerance, which has been implemented by H. te Riele, W. Lioen and D. Winter on the CDC Cyber 205 of the Academic Computing Centre Amsterdam. Primality of the p29 and the p40 was proved with help of the Adleman-Rumeley- Cohen-Lenstra method. The total amount of computing time spent was about 1.5 CPU-hours. Centre for Mathematics and Computer Science Kruislaan 413 1098 SJ Amsterdam The Netherlands herman te riele, cwi, amsterdam, nederland UUCP : {seismo,decvax,philabs,okstate,garfield}!mcvax!herman or : herman@mcvax.uucp INTERNET : herman%mcvax.uucp@seismo.css.gov BITNET/EARN: herman@mcvax (do NOT use its alias, hamcwi6) -- herman te riele, cwi, amsterdam, nederland UUCP : {seismo,decvax,philabs,okstate,garfield}!mcvax!herman or : herman@mcvax.uucp INTERNET : herman%mcvax.uucp@seismo.css.gov BITNET/EARN: herman@mcvax (do NOT use its alias, hamcwi6)