[sci.math.symbolic] help needed to factor an integer

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)