Re: Small prime divisors of very large numbers

Expand Messages
• ... In line 50, use the modulus m3 = eulerphi(P-1). In line 40, use the modulus m4 = eulerphi(m3). In line 30, use the modulus m5 = eulerphi(m4). Below is a
Message 1 of 2 , Jul 1, 2009
Norman Luhn <nluhn@...> wrote:

> I get only 5 factors.

These lines were wrong:

>    30   S1=modpow(137,137,P-1)
>    40   S2=modpow(137,S1,P-1)
>    50   S3=modpow(137,S2,P-1)

In line 50, use the modulus m3 = eulerphi(P-1).
In line 40, use the modulus m4 = eulerphi(m3).
In line 30, use the modulus m5 = eulerphi(m4).

Below is a Pari-GP procedure "pmod(a,m)" to compute
a[1]^(a[2]^(a[3]^ ... ^(a[k-1]^a[k]) ... ) modulo m
where the modulus "m" need not be prime.
I shall use it to show that
3^6 * 11 * 13^2 * 277 * 1063 * 7459 * 93408839
divides
137^(137^(137^(137^(137^137)))) + 184

{pmod(a,m)=local(k,q,t);k=#a;q=[m];t=a[k];
for(j=2,k-1,q=concat(eulerphi(q[1]),q));
for(j=1,k-1,t=Mod(a[k-j],q[j])^lift(t));t}

m = 3^6 * 11 * 13^2 * 277 * 1063 * 7459 * 93408839;
print(pmod([137,137,137,137,137,137],m)+184)

Mod(0, 278027998329615967980261)

David
Your message has been successfully submitted and would be delivered to recipients shortly.