Loading ...
Sorry, an error occurred while loading the content.
 

Re: Small prime divisors of very large numbers

Expand Messages
  • David Broadhurst
    ... 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
      --- In primenumbers@yahoogroups.com,
      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.