)
Neka je [inlmath]n[/inlmath] prirodan broj veći od dva. Neka je [inlmath]r[/inlmath] najmanji neparan prost broj takav da [inlmath]r\not\mid n[/inlmath] i [inlmath]n^2\not\equiv1\pmod r[/inlmath]. Neka je [inlmath]T_n(x)[/inlmath] Čebiševljev polinom prvog reda, tada je [inlmath]n[/inlmath] prost broj ako i samo ako je [inlmath]T_n(x)\equiv x^n\pmod{x^r-1,\,n}[/inlmath].
Test možete isprobati ovde (Conjecture 5).
Test je verifikovan za sve [inlmath]n<10^{10}[/inlmath]. Vreme izvršenja algoritma u najgorem slučaju je [inlmath]\Theta\left(\log^3n\right)[/inlmath].
PARI/GP program (imenujte skriptu: Test.gp):
- Kôd: Obeleži sve
xmat(r,n) = {[2*x, -1; 1, 0]*Mod(1,x^r-1)*Mod(1,n);}
smallestr(n)={if(n==1 || n%2==0, return(0));forprime(r = 3,oo,my(u=n%r);if (u==0 && r < n, return(0));if (u!=0 && u!=1 && u!=r-1, return(r)));}
myisprime(n)={my(r = smallestr(n));if (r == 0, return(n == 2));my(xp = xmat(r,n)^n*[x,1]~);xp[2] == Mod(x*Mod(1,n),x^r-1)^n;}
Test(n)={if(myisprime(n),print("Prime!"),print("Composite!"))}
