Frobenius pseudoprim
În teoria numerelor, un pseudoprim Frobenius este un pseudoprim care a trecut testul în trei etape din 1996 Jon Grantham 1996 de apartenență la numere prime probabile . [1] [2]
Numerele pseudoprime Frobenius sunt definite în raport cu un polinom dat . Pentru anumite tipuri de polinoame, pseudoprimele Frobenius sunt legate de alte tipuri de pseudoprime.
Exemplu
Numerele pseudoprime Frobenius în raport cu polinomul formează șirul:
4181, 5777, 6721, 10877, 13201, 15251, 34561, 51841, 64079, ... (secvența A212424 în OEIS ).
Proprietăți
Deși testul Frobenius cu o singură trecere este mai lent decât trecerea unică a majorității celorlalte teste de pseudo-primalitate, are o probabilitate mai mică de eroare în cazul cel mai rău caz , [1] , care poate fi obținută numai cu șapte treceri ale testului de primalitate Miller-Rabin .
Frobenius pseudosimplu puternic
Un pseudoprim se numește pseudoprim puternic Frobenius dacă satisface restricții suplimentare. [3]
Vezi și
Link -uri
- ↑ 1 2 Weisstein, Eric W. Frobenius pseudoprime (engleză) pe site-ul Wolfram MathWorld .
- ↑ John Grantham. Frobenius pseudoprimes (engleză) // Matematica calculului : jurnal. - 2001. - Vol. 70 , nr. 234 . - P. 873-891 . - doi : 10.1090/S0025-5718-00-01197-2 .
- ↑ Weisstein, Eric W. Strong Frobenius pseudoprime pe site- ul Wolfram MathWorld .
- R. Crandall, C. B. Pomerance. Numerele prime: o perspectivă computațională . - Ed. a II-a.. - Springer, 2005. - P. 613. - ISBN 9780387252827 .
Link- uri externe
- Pseudoprime simetrice , MathPages.