- View Source--- In primenumbers@yahoogroups.com,

"bhelmes_1" <bhelmes@...> wrote:

> Please give a hint how you produce these impression

Reminders:

> 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;

{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 - View Source--- In primenumbers@yahoogroups.com,

"bhelmes_1" <bhelmes@...> wrote:

> 1. let a jacobi (a, p)=-1

[4] is meaningless, as it stands.

> 2. let a^(p-1)/2 = -1 mod p

> 3. a^6 =/= 1 mod p

> 4. (1+sqrt (a))^p = 1-sqrt (a)

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

The group of units (Z/nZ)* is /not/ cyclic

> there is a cyclic order ...

> 3....

> there is a cyclic order ...

if n has at least two distinct odd prime fators.

David