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

Re: "wriggly" pseudoprime puzzle

Expand Messages
  • djbroadhurst
    ... Reminders: 1. p is an odd positive integer 2. a is an integer with kronecker(a,p) = -1 3. a^((p-1)/2) = -1 mod p 4. gcd(a^6-1,p) = 1 5. Mod(1+x,x^2-a)^p =
    Message 1 of 50 , Sep 5, 2010
    View Source
    • 0 Attachment
      --- In primenumbers@yahoogroups.com,
      "bhelmes_1" <bhelmes@...> wrote:

      > Please give a hint how you produce these impression
      > rate, some mathematical background would be very nice,
      > perhaps also for others.

      Reminders:

      1. p is an odd positive integer
      2. a is an integer with kronecker(a,p) = -1
      3. a^((p-1)/2) = -1 mod p
      4. gcd(a^6-1,p) = 1
      5. Mod(1+x,x^2-a)^p = 1-x mod p

      Puzzle: Find a pseudoprime, p,
      with a false witness, a,
      that fools (1), (2), (3), (5) and has
      znorder(Mod(a,p)) > 3414.

      Here is a notable solution with order greater than 3 billion:

      p = 555826983297468634137017311219;
      a = 3536132317921422012435;
      {if(kronecker(a,p)==-1&&Mod(a,p)^((p-1)/2)==-1&&
      Mod(Mod(1,p)*(1+x),x^2-a)^p==1-x,
      print("false witness with order "znorder(Mod(a,p))));}

      false witness with order 3137297526

      Comment: This false witness is one of over 600 million,
      found at a cost of under 13 microseconds per perjury. Let

      q = 9411892579; g = (q-1)/3; r = 2*g*(q+1)+1; p = q*r;

      Let m = 27^n, with gcd(n,g) = 1 and (1-m)^(2*g) = 1 mod q.
      Let a be an integer with a = m mod q and a^2 = a - 1 mod r.

      Theorem: The order of Mod(a,p) is g and the pair (p,a)
      satisfies conditions (1), (2), (3) and (5).

      Proof: First I check that q and r are prime and that
      3 is a primitive root of q:

      print([isprime(q),isprime(r),znorder(Mod(3,q))==q-1]);

      [1, 1, 1]

      Since n is coprime to g = (q-1)/3 = 0 mod 6, we have
      gcd(n,q-1) = 1 and hence 3^n is also a primitive root of q.
      Since a = (3^n)^3 mod q, we have znorder(Mod(a,q)) = g.
      Since a^2 = a - 1 mod r, we have znorder(Mod(a,r)) = 6.
      Since 6|g, we have znorder(Mod(a,p)) = lcm(g,6) = g, as claimed.

      Since q = 7 mod 12, (Z/Zq)* has no element of order 12.
      Mod(a,q) has an order divisible by 6 and hence is not a square.
      Since r = 1 mod 12, (Z/Zr)* has 4 elements of order 12.
      Mod(a,r) has order 6 and hence is a square. Since p = q*r,
      kronecker(a,p) = -1, as claimed in (2).

      Since r = 1 mod g and a^g = 1 mod q, we have
      a^(p-1) = a^(r-1) mod q = a^g mod q = 1 mod q and hence
      a^((p-1)/2) = -1 mod q, because kronecker(a,q) = -1.
      Since p = 7 mod 12 and a^6 = 1 mod r, we have
      a^((p-1)/2) = a^3 mod r = -1 mod r. Since p = q*r,
      a^((p-1)/2) = -1 mod p, as claimed in (3).

      Let y = Mod(1+x,x^2-a) and z = Mod(1-x,x^2-a). Then
      y^p = z^r mod q, since p = q*r and y^q = z mod q. Thus
      y^p = z^(2*g*(q+1)+1) mod q. Since z^q = y mod q,
      we have z^(q+1) = y*z mod q = 1-a mod q = 1-m mod q. Thus
      y^p = (1-m)^(2*g)*z mod q = z mod q. Now I perform the test

      s=polrootsmod(x^4-x^2+1,r);print(vector(4,k,(1+s[k])^q==1-s[k]));

      [1, 1, 1, 1]

      which establishes that y^q = z mod r. Since y^r = y mod r, we
      have y^p = z mod r, in addition to y^p = z mod q, above. Thus
      Mod(1+x,x^2-a)^p = 1-x mod p, as claimed in (5). So we are done.

      Comments: As previously advertised, my gremlin-trap (4) detects
      that p is composite, since gcd(a^6-1,p) = r.

      There are many other ways of solving the puzzle, but this one
      is notable for the rate at which it generates false witnesses.

      Here is the procedure that I used to find the seed, q.

      {m=10^10;default(primelimit,m);forprime(q=1,m,
      if(q%36==19,r=2*(q^2-1)/3+1;if(ispseudoprime(r),
      s=(sqrt(Mod(-1,r))+sqrt(Mod(3,r)))/2;
      if((1+s)^q==1-s,t=round(gettime/10^3);
      print(q" in "t" seconds");break()))));}

      9411892579 in 419 seconds

      I computed all false witnesses with znorder(Mod(a,p)) = g:

      {a=p;b=(1+sqrt(Mod(-3,r)))/2;h=2*g;
      m=Mod(1,q);M=10^6;N=0;T=0;gettime;
      for(n=1,g,m*=27;if(gcd(n,g)==1&&(1-m)^h==1,N+=2;
      a=min(a,min(lift(chinese(m,b)),lift(chinese(m,1-b))));
      if(N%M==0,T+=gettime;print(N" at "round(N/T)" kHz"))));
      T+=gettime;t=round(T/60000);print(N" in "t" minutes");
      print(a" is the smallest with order "g);}

      1000000 at 87 kHz
      ...
      606000000 at 84 kHz
      606357600 in 120 minutes
      3536132317921422012435 is the smallest with order 3137297526

      The number of perjuries was 2*eulerphi(g)/3 + 2400 = 606357600
      and the total time was 7 + 120 minutes, which amounts to merely
      13 microseconds per perjury, thanks to my Chinese gremlins.

      David Broadhurst, 6 September 2010
    • djbroadhurst
      ... [4] is meaningless, as it stands. You should write a double mod: 4. (1+x)^p = 1-x mod(x^2-a,p) ... There is no reason whatsoever to believe that [1] to [4]
      Message 50 of 50 , Sep 29, 2011
      View Source
      • 0 Attachment
        --- In primenumbers@yahoogroups.com,
        "bhelmes_1" <bhelmes@...> wrote:

        > 1. let a jacobi (a, p)=-1
        > 2. let a^(p-1)/2 = -1 mod p
        > 3. a^6 =/= 1 mod p
        > 4. (1+sqrt (a))^p = 1-sqrt (a)

        [4] is meaningless, as it stands.
        You should write a double mod:

        4. (1+x)^p = 1-x mod(x^2-a,p)

        > 1. Is it possible that there are other exceptions

        There is no reason whatsoever to believe that
        [1] to [4] establish that p is prime. Morevoer,
        some folk believe that, for every epsilon > 0,
        the number of pseudoprimes less than x may
        exceed x^(1-epsilon), for /sufficiently/ large x.

        > 2....
        > there is a cyclic order ...

        > 3....
        > there is a cyclic order ...

        The group of units (Z/nZ)* is /not/ cyclic
        if n has at least two distinct odd prime fators.

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