2022-03-11, 15:54 | #1 |
Sep 2002
Database er0rr
3^{4}·53 Posts |
Strengthening Damg ̊ard and Frandsen, and Khashin
Strengthening Damg ̊ard and Frandsen[1], and Khashin[2]
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? [1] An Extended Quadratic Frobenius Primality Test with Average Case Error Estimates & Ivan Bjerre Damg ̊ard Gudmund Skovbjerg Frandsen, https://eprint.iacr.org/2001/102.pdf [2] Counterexamples for Frobenius primality test, Sergey Khashin, https://arxiv.org/pdf/1307.7920.pdf 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]. Last fiddled with by paulunderwood on 2022-03-11 at 20:29 |
Thread Tools | |
Similar Threads | ||||
Thread | Thread Starter | Forum | Replies | Last Post |
Strengthening the Baillie-PSW primality test | paulunderwood | Computer Science & Computational Number Theory | 9 | 2020-06-30 19:28 |