Testați editarea fermei
Multe teste de simplitate se bazează pe teorema mică a lui Fermat: dacă prime nu este un divizor de număr, atunci
Testul lui Fermat pentru simplitatea numărului pe bază este procedura:
- dacă baza și modulul sunt satisfăcute, atunci acesta poate fi un număr prime
- dacă, atunci - compozit unic.
Testul lui Miller Editați
Îmbunătățirea testului Ferma se bazează pe afirmația că pentru una simplă care satisface condiția
,
unul dintre cele două
, .
Orice număr impar este reprezentat în formular
unde este un număr impar. atunci
.
În primul rând, vom calcula și succesiv pătrat:
.
Pentru această condiție
,
este necesar să se îndeplinească una dintre cele două condiții
.
Dacă una dintre condiții este îndeplinită, atunci pentru acest test se întoarce "posibil simplu"; dacă nu, atunci "compozit unic".
Probabilitatea de testare a lui Miller-Rabin Edit
Testul probabilistic Miller-Rabin se bazează pe alegerea numerelor pseudo-aleatoare și verificarea prin testul lui Miller. Dacă testul este trecut pentru toate numerele, atunci se numește pseudo-simplu, iar probabilitatea ca numărul să nu fie simplu are estimarea
Dacă pentru un anumit număr testul nu este trecut, atunci numărul este compus.
Utilizarea extensiei AdBlock a fost detectată.
Trimiteți-le prietenilor: