mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Miscellaneous Math (https://www.mersenneforum.org/forumdisplay.php?f=56)
-   -   Strengthening Damg ̊ard and Frandsen, and Khashin (https://www.mersenneforum.org/showthread.php?t=27649)

 paulunderwood 2022-03-11 15:54

Strengthening Damg ̊ard and Frandsen, and Khashin

Strengthening Damg ̊ard and Frandsen, and Khashin

I propose the test:

{tst(n,c)=
Mod(c,n)!=-1&&
kronecker(c,n)==-1&&
Mod(c,n)^((n-1)/2)==-1&&
Mod(Mod(x+1,n),x^2-c)^(n+1)==1-c;}

The Frobenius part's squaring during left-right binary exponentiation can be computed in 2 Selfridges for small c [2:2.2]:

(s*x+t)^2 == 2*s*t*x + (t+c*s)*(t+s) - (c+1)*s*t, where s and t are intermediate values.

Multiplication by the base x+1 is:

(s*x+t)*(x+1) = (t+s)*x + c*s+t.

Therefore the test is 1+2 Selfridges and has no known counterexamples so far... Do any of the authors mention the addition of the Euler PRP test?

 An Extended Quadratic Frobenius Primality Test with Average Case Error Estimates & Ivan Bjerre Damg ̊ard Gudmund Skovbjerg Frandsen, [url]https://eprint.iacr.org/2001/102.pdf[/url]

 Counterexamples for Frobenius primality test, Sergey Khashin, [url]https://arxiv.org/pdf/1307.7920.pdf[/url]

Edit: In order to prevent cyclotomic polynomials I add Mod(c,n)!=-3 and Mod(c,n)!=-1/3, the latter where gcd(3,n)==1

However a counterexample is [n, c]=[79786523, 2982522].

 All times are UTC. The time now is 08:09.