Frobenius pszeudoprím
A számelméletben a Frobenius -pszeudoprím olyan pszeudoprím , amely megfelelt az 1996-os Jon Grantham 1996 -os háromlépcsős teszten a valószínű prímekhez való tartozásról . [1] [2]
A pszeudoprím Frobenius-számok egy adott polinomra vonatkoznak . Bizonyos típusú polinomok esetében a Frobenius-pszeudoprímek más típusú pszeudoprímekhez kapcsolódnak.
Példa
A pszeudoprím Frobenius-számok a polinomhoz viszonyítva a következő sorozatot alkotják:
4181, 5777, 6721, 10877, 13201, 15251, 34561, 51841, 64079, ... ( A212424 sorozat az OEIS -ben ).
Tulajdonságok
Bár az egyszeres Frobenius-teszt lassabb, mint a legtöbb más pszeudo-primalitási teszt egyszeri átadása, alacsonyabb a legrosszabb eset hiba valószínűsége [1] , amely csak a Miller-Rabin primalitásteszt hét sikeres teljesítésével érhető el .
Erős álegyszerű Frobenius
A pszeudoprímet erős Frobenius-pszeudoprímnek nevezzük , ha eleget tesz további korlátozásoknak. [3]
Lásd még
Linkek
- ↑ 1 2 Weisstein, Eric W. Frobenius pszeudoprime (angol) a Wolfram MathWorld weboldalán .
- ↑ John Grantham. Frobenius pseudoprimes (angol) // Számítási matematika : folyóirat. - 2001. - Vol. 70 , sz. 234 . - P. 873-891 . - doi : 10.1090/S0025-5718-00-01197-2 .
- ↑ Weisstein, Eric W. Strong Frobenius pszeudoprím a Wolfram MathWorld webhelyén .
- R. Crandall, C. B. Pomerance. Prímszámok : Számítási perspektíva . - 2. kiadás. - Springer, 2005. - P. 613. - ISBN 9780387252827 .
Külső linkek
- Szimmetrikus pszeudoprímek , MathPages.