Frobenius pseudoprime
I talteorin är ett Frobenius pseudoprimtal ett pseudoprimtal som har klarat 1996 Jon Grantham 1996 trestegstestet för att tillhöra troliga primtal . [1] [2]
Pseudoprimtal Frobenius definieras med avseende på ett givet polynom . För vissa typer av polynom är Frobenius pseudoprimer relaterade till andra typer av pseudoprimer.
Exempel
Pseudoprimtal Frobenius med avseende på polynomet bildar sekvensen:
4181, 5777, 6721, 10877, 13201, 15251, 34561, 51841, 64079, ... (sekvens A212424 i OEIS ).
Egenskaper
Även om Frobenius-testet för singelpass är långsammare än singelpasset för de flesta andra pseudoprimalitetstester, har det en lägre värsta fallfelsannolikhet [ 1] , som endast kan erhållas med sju genomgångar av Miller-Rabins primatitetsteste .
Stark pseudoenkel Frobenius
En pseudoprime kallas en stark Frobenius pseudoprime om den uppfyller ytterligare begränsningar. [3]
Se även
Länkar
- ↑ 1 2 Weisstein, Eric W. Frobenius pseudoprime (engelska) på Wolfram MathWorld- webbplatsen .
- ↑ John Grantham. Frobenius pseudoprimes (engelska) // Mathematics of Computation : journal. - 2001. - Vol. 70 , nej. 234 . - s. 873-891 . - doi : 10.1090/S0025-5718-00-01197-2 .
- ↑ Weisstein, Eric W. Strong Frobenius pseudoprime på Wolfram MathWorld- webbplatsen .
- R. Crandall, C. B. Pomerance. Prime Numbers: A Computational Perspective . - 2nd ed.. - Springer, 2005. - P. 613. - ISBN 9780387252827 .
Externa länkar
- Symmetriska pseudoprimer, MathPages.