Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!ll-xn!adelie!axiom!linus!bs
From: bs@linus.UUCP (Robert D. Silverman)
Newsgroups: sci.math.symbolic
Subject: Re: help needed to factor an integer
Message-ID: <390@linus.UUCP>
Date: Tue, 11-Nov-86 06:40:35 EST
Article-I.D.: linus.390
Posted: Tue Nov 11 06:40:35 1986
Date-Received: Wed, 12-Nov-86 04:57:06 EST
References: <664@watmum.UUCP>
Distribution: net
Organization: The MITRE Corporation, Bedford, MA
Lines: 42

> 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