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

Re: Small prime divisors of very large numbers [new puzzle]

Expand Messages
  • David Broadhurst
    ... With b = 3581, n = 8001, the 28436-digit prime p = 2*b^n + 1: http://primes.utm.edu/primes/page.php?id=5735 found by René Dohmen in March 2000, neatly
    Message 1 of 70 , Jul 7, 2009
    • 0 Attachment
      --- In primenumbers@yahoogroups.com,
      "David Broadhurst" <d.broadhurst@...> wrote:

      > Puzzle: Find a triplet [b, n, p] such that:
      > 1) b is a prime base greater than 1033,
      > 2) n is an integer exponent greater than b,
      > 3) p is a prime modulus greater than b^n,
      > 4) the order of b modulo p is precisely b^n.

      With b = 3581, n = 8001, the 28436-digit prime p = 2*b^n + 1:
      http://primes.utm.edu/primes/page.php?id=5735
      found by René Dohmen in March 2000, neatly solves the puzzle.

      Lemma: If b = 1 mod 4 is prime and p = 2*b^n + 1 is prime,
      then the order of b modulo p is a divisor of b^n.

      Proof: Both b and p are coprime to 3. Hence b = 5 mod 12 and
      n is odd. Since -2*b^n = 1 mod p and p = 11 mod 24 = 3 mod 8,
      we obtain kronecker(b,p) = kronecker(-2,p) = 1, from which it
      follows that b^(b^n) = b^((p-1)/2) = 1 mod p.

      Method: To solve the puzzle we are obliged to investigate the
      possibility that the order is less than b^n. This can be done
      in a Pocklington test of the primality of p, with factored
      part F = b^n dividing p-1, by choosing the witness a = b in

      {Pock(a,b,n)=local(p,t);if(b%12==5&&isprime(b),p=2*b^n+1;
      t=Mod(a,p)^((p-1)/b);if(t^b==1&&gcd(t-1,p)==1,"Prime","?"))}

      Examples: With b = 89 and n = 93, Pock(3,b,n) returns "Prime"
      and Pock(b,b,n) returns "?", since gcd(t-1,p) = p. Hence the
      order of Mod(b,p) is less than b^n. To prove that it is
      b^(n-1) = 89^92, one may compute gcd(t^(1/b)-1,p) = 1.

      With b = 3581 and n = 8001, Pock(b,b,n) returns "Prime".
      By Pocklington's theorem, we have proven the primality of
      p = 2*3581^8001 + 1. By using the witness a = b, we have
      also shown that the order of Mod(b,p) is b^n, since the
      Lemma proves that the order is a divisor of b^n and
      Pock(b,b,n) found that b^((p-1)/b) - 1 is coprime to p.

      Comment: I was unable to find an entry in the Prime Pages
      that provides a solution with n > b > 3581. There is an
      interesting reason for this. The archivable case
      http://primes.utm.edu/top20/page.php?id=37
      puts a premium on prime bases with b = 11 mod 12, for which
      a prime p = 2*b^n + 1 = 23 mod 24 = 7 mod 8 is certain to
      divide a cyclotomic number Phi(b^m,2) with m not exceeding n.
      http://primes.utm.edu/primes/page.php?id=69908
      shows that Ingo Büchel and Wilfrid Keller obtained m = n - 1
      in the 97498-digit case with b = 107, n = 48043. At large b,
      one might expect to obtain m < n in about 1/b of the cases.

      David Broadhurst
    • 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 5:29 PM
      • 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.