From: Robert Harley <harley@corton.inria.fr>
Subject: Re: Factoring numbers too big to represent on a computer?
Date: 12 Sep 1999 15:44:49 +0200
Newsgroups: sci.crypt,sci.math
Keywords: primes dividing 10^(10^100) + 1

"Stush" <stush@nb.net> writes:
> How would one go about finding factors of a number too big to represent on a
> computer?
> 
> For example 5^d -1 where d is > 10^50.

You should start by doing an algebraic factorisation into the product
of PHI_n(5) where PHI_n is the n-th cyclotomic polynomial and n
divides d.  Sometimes you can also use Aurifeuille's factors:

  5^(2h)+3*5^h+1 -/+ 5^k*(5^h+1) divide 5^(5h)-1, where h = 2k-1.

Finally, a theorem of Legendre tells you to look for prime factors in
some arithmetic progressions, basically 1 mod d or 1 mod 2d if you're
careful.  You can then use sieving along these progressions to
eliminate obvious composites.

I did this years ago for googolplex+1 and found these prime factors:

316912650057057350374175801344000001 
155409907106060194289411023528840396801 
1467607904432329964944690923937202176001 
11438565962996913740067907829760000000001 
495176015714152109959649689600000000000001 
7399415202816574979127045311692800000000001 
9823157208340761024963422324575436800000001 
493333612765059415097397477376000000000000000000001 
8019958276735747672058735099904000000000000000000001 
8301034833169298227200000000000000000000000000000000000000001 
325123864299130847232000000000000000000000000000000000000000001 
35343349155678178508800000000000000000000000000000000000000000000000001
156941061512238345486336000000000000000000000000000000000000000000000001
370791604769783808000000000000000000000000000000000000000000000000000000000000001

Bye,
  Rob.