Sorry, an error occurred while loading the content.

## Re: "wriggly" pseudoprime puzzle

Expand Messages
• ... 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
"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
• ... [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
"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.