Browse Groups

• ... Exercise 2: Show that the test loses 3 selfrides for x^2 = 3 mod n. Comment 2: Hence the happy gremlins, in this case. Exercise 3: Show that the test loses
Message 1 of 26 , Jan 18
View Source

> > loses (at least) one selfridge of potency for x^2 = 3 mod n.
> Thanks for the insight.

Exercise 2: Show that the test loses 3 selfrides for x^2 = 3 mod n.
Comment 2: Hence the happy gremlins, in this case.

Exercise 3: Show that the test loses 1 selfride for 2*x^2 = 5 mod n.
Comment 3: The gremlins were not able to fool it in this case.

David
• ... Exercise 4: Show that the test loses 2 selfridges for 2*x^2 = 5 mod n. David
Message 2 of 26 , Jan 18
View Source
> Exercise 3: Show that the test loses 1 selfridge for 2*x^2 = 5 mod n.

Exercise 4: Show that the test loses 2 selfridges for 2*x^2 = 5 mod n.

David
• ... Exercise 5: Show that the test loses 3 selfridges for 2*x^2 = 5 mod n, degenerating to a 1-selfridge Euler test, with base -15/16, plus a 2-selfridge Lucas
Message 3 of 26 , Jan 18
View Source

> Exercise 4: Show that the test loses 2 selfridges for 2*x^2 = 5 mod n.

Exercise 5: Show that the test loses 3 selfridges for 2*x^2 = 5 mod n,
degenerating to a 1-selfridge Euler test, with base -15/16, plus a
2-selfridge Lucas test with P = 2/5 and Q = 1, and thus costs the same as BPSW.

Comment: As in the case of BPSW, the gremlins cannot defraud this case.

David
• I failed to solve any of David s exercises... but I have done some shallow verification, n
Message 4 of 26 , Jan 19
View Source
I failed to solve any of David's exercises... but I have done some shallow verification, n<2.5*10^5, for yet another test:

{tst(n,x)=kronecker(x^2-4,n)==-1&&
gcd(x+1,n)==1&&
Mod(Mod(1,n)*(L+x+1),(L^2-x*L+1)*(L^2+x*L+1))^(n)==-L^3+(x^2-2)*L+x+1;}

It looks as though when "gcd(x+1,n)==1" is needed then n==5 (mod 6), and any of gcd(x-1,n), gcd(x,n), gcd(x^2-2,n) and gcd(x^3-3,n) greater than 1 is also a prime equal to 5 (mod 6) when "gcd(x+1,n)==1" is required,

Paul -- subject to gcd wriggles
• ... Further, it seems that if gcd(x+1,n) is needed then it is equal to 1 (mod 6) Paul
Message 5 of 26 , Jan 19
View Source
>
>
> I failed to solve any of David's exercises... but I have done some shallow verification, n<2.5*10^5, for yet another test:
>
> {tst(n,x)=kronecker(x^2-4,n)==-1&&
> gcd(x+1,n)==1&&
> Mod(Mod(1,n)*(L+x+1),(L^2-x*L+1)*(L^2+x*L+1))^(n)==-L^3+(x^2-2)*L+x+1;}
>
> It looks as though when "gcd(x+1,n)==1" is needed then n==5 (mod 6), and any of gcd(x-1,n), gcd(x,n), gcd(x^2-2,n) and gcd(x^3-3,n) greater than 1 is also a prime equal to 5 (mod 6) when "gcd(x+1,n)==1" is required,
>

Further, it seems that if "gcd(x+1,n)" is needed then it is equal to 1 (mod 6)

Paul
• ... These ancillary statements are mostly false, except that maybe when gcd(x+1,n) needs to be checked then gcd(x-1,n), gcd(x,n), gcd(x^2-2,n) and
Message 6 of 26 , Jan 19
View Source
>
>
>
> --- In primenumbers@yahoogroups.com, "paulunderwooduk" wrote:
> >
> >
> > I failed to solve any of David's exercises... but I have done some shallow verification, n<2.5*10^5, for yet another test:
> >
> > {tst(n,x)=kronecker(x^2-4,n)==-1&&
> > gcd(x+1,n)==1&&
> > Mod(Mod(1,n)*(L+x+1),(L^2-x*L+1)*(L^2+x*L+1))^(n)==-L^3+(x^2-2)*L+x+1;}
> >
> > It looks as though when "gcd(x+1,n)==1" is needed then n==5 (mod 6), and any of gcd(x-1,n), gcd(x,n), gcd(x^2-2,n) and gcd(x^3-3,n) greater than 1 is also a prime equal to 5 (mod 6) when "gcd(x+1,n)==1" is required,
> >
>
> Further, it seems that if "gcd(x+1,n)" is needed then it is equal to 1 (mod 6)
>

These ancillary statements are mostly false, except that maybe when "gcd(x+1,n)" needs to be checked then gcd(x-1,n), gcd(x,n), gcd(x^2-2,n) and gcd(x^3-3,n) are either 1 or prime,

Paul
• ... Please accept my apology for my previous statements about this composite test. I am actually running tests for: (mod n, L^2-x*L+1) and (mod n, L^2+x*L+1);
Message 7 of 26 , Jan 19
View Source

> > >
> > > {tst(n,x)=kronecker(x^2-4,n)==-1&&
> > > gcd(x+1,n)==1&&
> > > Mod(Mod(1,n)*(L+x+1),(L^2-x*L+1)*(L^2+x*L+1))^(n)==-L^3+(x^2-2)*L+x+1;}
> > >

(mod n, L^2-x*L+1) and (mod n, L^2+x*L+1); not the product of these. If the main test is passed then gcds with n of x-1, x, x+1, x^2-2 and x^2-3 are logged.

Now for some speculation about the results so far:

1) taking the mod with "the product" implies gcd(x,n)==1.

2) for "the product", gcds of n with x-1, x^2-2 and x^2-3 are either 1 or a prime congruent to 5 (mod 6) where "gcd(x+1,n)" is logged.

3) logged gcd(x+1,n) is not 1

4) the logged n are all congruent to 5 (mod 6).

Paul
• ... Here is another test, on the same theme, for which I cannot also easily find a fraud: {tst(n,x)=kronecker(x^2-4,n)==-1&& gcd(x^2-1,n)==1&&
Message 8 of 26 , Jan 21
View Source

>
> > > >
> > > > {tst(n,x)=kronecker(x^2-4,n)==-1&&
> > > > gcd(x+1,n)==1&&
> > > > Mod(Mod(1,n)*(L+x+1),(L^2-x*L+1)*(L^2+x*L+1))^(n)==-L^3+(x^2-2)*L+x+1;}
> > > >
>

Here is another test, on the same theme, for which I cannot also easily find a fraud:

{tst(n,x)=kronecker(x^2-4,n)==-1&&
gcd(x^2-1,n)==1&&
Mod(Mod(1,n)*(L+x^2-1),(L^2-x*L+1)*(L^2+x*L+1))^(n)==-L^3+(x^2-2)*L+x^2-1;}

Paul
• ... n=2953711;x=285843 is a near-counterexample that comes from me testing over the two quadratics that form the quartic. gcd(x,n)==95281 and
Message 9 of 26 , Jan 27
View Source

> Here is another test, on the same theme, for which I cannot also easily find a fraud:
>
> {tst(n,x)=kronecker(x^2-4,n)==-1&&
> gcd(x^2-1,n)==1&&
> Mod(Mod(1,n)*(L+x^2-1),(L^2-x*L+1)*(L^2+x*L+1))^(n)==-L^3+(x^2-2)*L+x^2-1;}
>

n=2953711;x=285843 is a near-counterexample that comes from me testing over the two quadratics that form the quartic. gcd(x,n)==95281 and gcd(x^2-2,n)==31,

Paul
• ... n=1934765;x=1219266 has gcd(x-1,n)==265. So 2) might be 1 or a product of primes each congruent 5 (mod 6) , but as greater n get tested I guess this rule
Message 10 of 26 , Jan 30
View Source
> --- In primenumbers@yahoogroups.com, "paulunderwooduk" wrote:
>
>
> > > >
> > > > {tst(n,x)=kronecker(x^2-4,n)==-1&&
> > > > gcd(x+1,n)==1&&
> > > > Mod(Mod(1,n)*(L+x+1),(L^2-x*L+1)*(L^2+x*L+1))^(n)==-L^3+(x^2-2)*L+x+1;}
> > > >
>
> (mod n, L^2-x*L+1) and (mod n, L^2+x*L+1); not the product of these. If the main test is passed then gcds with n of x-1, x, x+1, x^2-2 and x^2-3 are logged.
>
> Now for some speculation about the results so far:
>
> 1) taking the mod with "the product" implies gcd(x,n)==1.
>
> 2) for "the product", gcds of n with x-1, x^2-2 and x^2-3 are either 1 or a prime congruent to 5 (mod 6) where "gcd(x+1,n)" is logged.
>

n=1934765;x=1219266 has gcd(x-1,n)==265. So 2) might be "1 or a product of primes each congruent 5 (mod 6)", but as greater n get tested I guess this rule will break too...

> 3) logged gcd(x+1,n) is not 1
>
> 4) the logged n are all congruent to 5 (mod 6).
>

I have verified all n<1.95*10^6

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