--- In firstname.lastname@example.org
"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.
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;
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:
[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
[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.
print(q" in "t" seconds");break()))));}
9411892579 in 419 seconds
I computed all false witnesses with znorder(Mod(a,p)) = g:
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