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

25520Re: [PrimeNumbers] Re: Small prime divisors of very large numbers

Expand Messages
  • Maximilian F. Hasler
    Mar 23, 2014
      Dear all,
      I come back to this topic, looking for a working "pow_mod".
      This :
      {mypmod(b,n,p)=local(m=[p],f=0);
      while(n=n-1,m=concat(eulerphi(m[1]),m));
      for(p=n=1,#m,n=lift(Mod(b,m[p])^n);
      if(f=f+(n*log(b)>=log(m[p])),n=n+m[p]));n%m[#m];}

      yields:
      mypmod(2,3,5)
      = 2
      but 2^2^2 % 5 = 16 % 5 = 1.
      (and idem for 2^2^2^2 - of course.).

      David gave some other code, in
      https://groups.yahoo.com/neo/groups/primenumbers/conversations/topics/20526
      :
      "
      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.
      (...)
      {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}
      "
      Although this may work for prime m
      (at least, pmod([2,2,2],5) = Mod(1,5) as should),
      it gives:

      pmod([2,2,2],4)
      = Mod(1, 4)
      which is most certainly wrong.

      So, to put it short, has anyone a working pmod() in his "library" ?

      Thanks in advance!
      Maximilian


      --- In primenumbers@yahoogroups.com, "David Broadhurst"
      <d.broadhurst@...> wrote:

      > fail

      (...)

      I consider that his code should not be trusted.

      David
    • Show all 70 messages in this topic