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

Re: Small prime divisors of very large numbers

Expand Messages
  • richard_in_reading
    ... I m still working on the why . I suspect it has something to do with how quickly iterates of eulerphi for a prime hit a power of 2. The phenomenon doesn t
    Message 1 of 70 , Jul 1, 2009
    • 0 Attachment
      --- In primenumbers@yahoogroups.com, "David Broadhurst" <d.broadhurst@...> wrote:

      > Like Richard, I find this result to be "strange indeed".
      >
      > Can anyone tell Richard and me why we should not be surprised?

      I'm still working on the "why". I suspect it has something to do with how quickly iterates of eulerphi for a prime hit a power of 2. The phenomenon doesn't seem to be rare though.

      For David's example the numbers were 137 and 73.
      I use 139 and 15 selected by trying a few numbers until lots of small factors showed up at higher iterations.

      139+15 has factors 2, 7, 11
      139^139+15 has factors 2, 7, 19, 8689, 60293
      139^139^139+15 has factors 2, 7, 19, 67, 983, 1723, 66841
      139^139^139^139+15 has factors 2, 7, 19, 67, 1723, 66841
      139^139^139^139^139+15 has factors 2, 7, 19, 67, 1723, 66841
      139^^6+15 has factors 2, 7, 19, 67, 1723, 66841
      139^^7+15 has factors 2, 7, 19, 67, 1723, 66841
      139^^8+15 has factors 2, 7, 19, 67, 1723, 66841
      139^^9+15 has factors 2, 7, 19, 67, 1723, 66841
      etc

      So some primes pop in for an interation and go again and some come in and stick around.
      7 keeps showing up as 139 % 7 = -1 and 15 % 7 = 1
      19 keeps showing up as eulerphi(eulerphi(19))=6 and 139 % 6 = 1
      67 keeps showing up as eulerphi(eulerphi(67))=20 and 139 % 20 =-1
      I can't quite make sense of 1723 and I've run out of time.

      Richard Heylen
    • Maximilian F. Hasler
      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));
      Message 70 of 70 , Mar 23, 2014
      • 0 Attachment
        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
      Your message has been successfully submitted and would be delivered to recipients shortly.