Kvadratisk Frobenius-test

Det kvadratiska Frobenius-testet ( QFT ) är ett probabilistiskt primalitetstest för att avgöra om ett tal är ett troligt primtal . Den är uppkallad efter Ferdinand Georg Frobenius . Testet använder begreppen kvadratiska polynom och Frobenius automorfism . Det bör inte förväxlas med det mer allmänna Frobenius-testet som använder ett kvadratiskt polynom – QFT begränsar de tillåtna polynomen baserat på inmatningen och har även andra villkor som måste uppfyllas. En komposit som klarar detta test är en Frobenius-pseudoprime , men det omvända är inte nödvändigtvis sant.

Begrepp

Granthams uttalade mål när algoritmen utvecklades var att tillhandahålla ett test att primtal alltid skulle klara och kompositer skulle klara med en sannolikhet på mindre än 1/7710.

Testet utökades senare av Damgård och Frandsen till ett test som kallas utökat kvadratiskt Frobenius-test (EQFT).

Algoritm

Låt n vara ett positivt heltal så att n är udda, $\left({\frac {b^{2}+4c}{n}}\right)=- 1$ och ${\displaystyle \left({\frac {-c}{n}}\right)=1} ,$ där $\left({\frac {x }{n}}\right)$ anger Jacobi-symbolen . Set $B=50000$ . Då fungerar en QFT på n med parametrar ( b , c ) enligt följande:

(1) Testa om ett av primtalen är mindre än eller lika med det lägre av de två värdena $B$ och ${\sqrt {n}}$ delar n . Om ja, sluta då n är sammansatt.

(2) Testa om ${\sqrt {n}}\in \mathbb {Z}$ . Om ja, sluta då n är sammansatt.

(3) Beräkna $x^{n+1 \over 2}\,{\bmod {\,}}{\big (}n ,x^{2}-bx-c)$ . Om ${\displaystyle x^{n+1 \over 2}\notin \mathbb {Z} {\big /}n\mathbb {Z} } stoppa då$ eftersom n är sammansatt.

(4) Beräkna $x^{n+1}\,{\bmod {\,}}{\big (}n,x^{ 2}-bx-c)$ . Om $x^{n+1}\not \equiv -c$ sluta då eftersom n är sammansatt.

(5) Låt $n^{2}-1=2^{r}s$ med s udda. Om $x^{s}\not \equiv 1{\bmod {\,}}{\big (}n,x^{2} -bx-c)$ , och $x^{2^{j}s}\not \equiv -1{\bmod { \,}}{\big (}n,x^{2}-bx-c)$ för alla $0\leq j\leq r-2$ , stoppa sedan eftersom n är sammansatt .

Om QFT inte stannar i steg (1)–(5), är n ett troligt primtal.

(Beteckningen $A\equiv B{\bmod {\,}}(n,\,f(x))$ betyder att ${\displaystyle AB=H(x)\cdot n+K(x)\cdot f(x)} ,$ där H och K är polynom.)

Se även

• Heltal modulo n
• Multiplikativ grupp av heltal modulo n