HesapHanem

Reiknivél fyrir Miller-Rabin frumtöluprófun

Sláðu inn ónæga heiltölu til að prófa frumtölueiginleika með Miller-Rabin.

Hvernig á að nota

  1. Sláðu inn gildin þín í reitina hér að ofan.
  2. Ýttu á Reikna til að sjá niðurstöðuna samstundis.
  3. Notaðu Deila hnappinn til að afrita tengil á niðurstöðuna þína.

Um þessa reiknivél

Miller-Rabin prófið kannar hvort tala er frumtala með því að rita n − 1 sem 2ˢ·d þar sem d er oddatala og prófa síðan hvort vitnisgrunnur a uppfylli aᵈ ≡ 1 (mod n) eða a^(2ʳ·d) ≡ −1 (mod n) fyrir einhvert r < s. Eitt vitni gefur aðeins líkindaniðurstöðu, en með því að prófa gagnvart litlu, sönnuðu mengi fastra vitnisgrunna (til dæmis 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37) verður prófið nákvæmt (ákvarðandi) fyrir sérhverja heiltölu undir um það bil 3,18 × 10²³ — langt umfram það sem flest forrit þurfa nokkurn tíma.

Dulritunarfræðingar og hugbúnaðarframleiðendur nota einmitt þessa gerð prófs þegar búin eru til stór frumtöluframbjóðendur fyrir RSA- eða Diffie-Hellman-lykla, og nemendur í tölvunarfræði nota það til að sjá, á raunverulegum tölum, hvers vegna Miller-Rabin skalast svo miklu betur en prófun með deilingu þegar athugað er hvort stór heiltala sé frumtala.

Var þetta gagnlegt?

Þú getur valið allt að 3 viðbrögð.

Athugasemdir

  • Vertu fyrst/ur til að skrifa athugasemd.

Vinsælar reiknivélar

Lánareiknivél

Mánaðarleg greiðsla, heildarvextir og heildarafborgunaráætlun.

Prósentureiknivél

Prósentubreyting, prósenta af gildi og hlutfallsútreikningar.

Afsláttarreiknivél

Reiknið lokaverð, sparnað og afsláttarupphæð.

BMI reiknivél

Líkamsþyngdarstuðull út frá hæð og þyngd (metrakerfi eða imperial).

Aldursreiknivél

Reiknaðu nákvæman aldur þinn í árum, mánuðum og dögum frá fæðingardegi.

Vaxtavaxtareiknivél

Reiknaðu lokaupphæð og áunna vexti með vaxtavöxtum.

Allar reiknivélar