Browse Groups

• ... 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
"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.

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.

• ... [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
"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.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.