Modulaararitmeetika kell

Vali moodul n ja tehe. Vaata tulemust mooduljäägi kellal ning uuri liitmis-/korrutamistabeleid.

Näidisarvutus — Modulaararitmeetika kell

Avaldis	7 x 5 (mod 12)
Tulemus	11

Need on väärtused, mida kalkulaator lehe avamisel näitab. Muuda ülal mõnda sisendit, et need ümber arvutada.

Interaktiivse simulatsiooni laadimine...

Algarvuline moodul lubab jälle jagada

Modulaararitmmeetika tegeleb täisarvudega tsüklilise mooduli n all, kirjutatakse a ≡ b (mod n). See algebraline süsteem moodustab kommutatiivse ringi Z/nZ. Kui moodul p on algarv, muutub ring korpuseks, mis tähendab, et igal nullist erineval elemendil on olemas multiplikatiivne pöördelement.

Miks seda kellaaritmeetikaks nimetatakse

12-tunnisel kellal on 4 tundi pärast kella 11 hoopis 3, mitte 15 — arvud pöörduvad algusesse tagasi, kui nad ületavad 12. Just see ongi modulaararitmeetika: a ≡ b (mod n) tähendab, et a ja b annavad n-ga jagamisel sama jäägi. Seega 15 ≡ 3 (mod 12). Põhimõte on lihtne: modulaararitmeetika hoiab alles vaid jagamise jäägi, ja selle tööriista kell näitab, kuidas arvud ringi käivad.

Üheksaga jaguvuse reegel on peidetud modulaararitmeetika

Vana reegel „arv jagub 9-ga, kui tema numbrite summa jagub 9-ga“ on puhas modulaararitmeetika. Kuna 10 ≡ 1 (mod 9), on ka iga kümne aste ≡ 1, nii et arv on kongruentne oma numbrite summaga (mod 9). Sama tõsiasi on aluseks üheksaga kontrollimise võttele — sajanditevanusele viisile arvutusi käsitsi üle kontrollida.

MODULAARARITMEETIKA — MILLAL TOHIB JAGADA JA MILLAL MITTE?

Millise modulaararitmeetika juhtumiga on tegemist?

Mooduli n järgi arvutamine tähendab ainult jäägi alleshoidmist ning liitmine, lahutamine ja korrutamine peavad sellele vastu. Jagamine mitte. Kas mingi arvuga tohib jagada — kas tal on pöördarv — sõltub ainult sellest, kas tal on n-iga ühine tegur. Just seepärast käitub algarvuline moodul nii teisiti kui kordarvuline. Kumma juhtumiga on tegu, sõltub tehtest ja sellest, mis arv n on.

Liitmine — alati korralik, ükskõik milline n on 13 + 5 ≡ 6 (mod 12)

Algarvuline moodul — jagada tohib iga nullist erineva elemendiga φ(7) = 6 ⇒ gcd(a, 7) = 1 ∀a ≠ 0

Kordarvuline moodul — enamiku elementidega ei tohi jagada 2 × 3 ≡ 0, φ(6) = 2

Korduvad astmed — need käivad ringi ja Fermat ütleb, kus a^p−1 ≡ 1 (mod p)

Liitmine — alati korralik, ükskõik milline n on

Mida te teate: Ükskõik milline moodul. Liitmine, lahutamine ja korrutamine mooduli n järgi on alati määratud ja igal elemendil on liitmise vastand.

Mida kontrollida: 13 + 5 ≡ 6 (mod 12)

Näidisarvutus: 12-tunnine kell: 13 + 5 = 18 ja 18 mod 12 = 6. Viis tundi pärast kella ühte on kell kuus.

Ava see juhtum: kell mod 12

Liitmine — alati korralik, ükskõik milline n on. Liitmistabel mooduli 12 järgi: iga rida on eelmine ühe võrra nihutatuna ja iga väärtus esineb täpselt üks kord. Ükskõik milline moodul. Liitmine, lahutamine ja korrutamine mooduli n järgi on alati määratud ja igal elemendil on liitmise vastand. — Liitmistabel mooduli 12 järgi: iga rida on eelmine ühe võrra nihutatuna ja iga väärtus esineb täpselt üks kord.

Algarvuline moodul — jagada tohib iga nullist erineva elemendiga

Mida te teate: n on algarv. Siis ei jaga ükski nullist erinev element n-iga tegurit, seega on igaühel korrutamise pöördarv.

Mida kontrollida: φ(7) = 6 ⇒ gcd(a, 7) = 1 ∀a ≠ 0

Näidisarvutus: Mooduli 7 järgi: 3 × 4 = 12 ≡ 5. Kõik kuus nullist erinevat väärtust 1…6 on pööratavad, nii et korrutustabelis ei ole väljaspool esimest rida ühtki nulli.

Ava see juhtum: algarv mod 7

Algarvuline moodul — jagada tohib iga nullist erineva elemendiga. Korrutustabel mooduli 7 järgi: esimesest reast allpool ühtki nulli ja iga rida on 1 kuni 6 permutatsioon. n on algarv. Siis ei jaga ükski nullist erinev element n-iga tegurit, seega on igaühel korrutamise pöördarv. — Korrutustabel mooduli 7 järgi: esimesest reast allpool ühtki nulli ja iga rida on 1 kuni 6 permutatsioon.

Kordarvuline moodul — enamiku elementidega ei tohi jagada

Mida te teate: n on kordarv. Pöördarv on ainult n-iga ühistegurita väärtustel; ülejäänud on nullitegurid ja nendega jagamine on mõttetu.

Mida kontrollida: 2 × 3 ≡ 0, φ(6) = 2

Näidisarvutus: Mooduli 6 järgi: 2 × 4 = 8 ≡ 2. Ei 2 ega 4 ole pööratav, sest SÜT(2,6) = 2 ja SÜT(4,6) = 2. Ühikud on ainult 1 ja 5 — kaks kuuest.

Ava see juhtum: kordarv mod 6

Kordarvuline moodul — enamiku elementidega ei tohi jagada. Korrutustabel mooduli 6 järgi, nullidega üle pikitud, ja ainult kaks rida on permutatsioonid. n on kordarv. Pöördarv on ainult n-iga ühistegurita väärtustel; ülejäänud on nullitegurid ja nendega jagamine on mõttetu. — Korrutustabel mooduli 6 järgi, nullidega üle pikitud, ja ainult kaks rida on permutatsioonid.

Korduvad astmed — need käivad ringi ja Fermat ütleb, kus

Mida te teate: Astendamine mooduli n järgi. Algarvu p ja p-ga mittejaguva a puhul korduvad astendajad perioodiga, mis jagab p − 1.

Mida kontrollida: a^p−1 ≡ 1 (mod p)

Näidisarvutus: Mooduli 13 järgi: 7¹² ≡ 1. Fermat’ väike teoreem tagab selle iga alusega 1 kuni 12, ilma ühtki suurt astet välja arvutamata.

Ava see juhtum: Fermat' mod 13

Korduvad astmed — need käivad ringi ja Fermat ütleb, kus. Iga aluse astmed mooduli 13 järgi; astendaja 12 veerg naaseb iga ühiku puhul ühe juurde. Astendamine mooduli n järgi. Algarvu p ja p-ga mittejaguva a puhul korduvad astendajad perioodiga, mis jagab p − 1. — Iga aluse astmed mooduli 13 järgi; astendaja 12 veerg naaseb iga ühiku puhul ühe juurde.

Ülesanne täielikult lahendatud

7 12 mod 13 arvutamine täisruudustikul 5 sammu
Arvuta 7¹² mod 13 ilma arvu 7¹² kordagi välja kirjutamata. See on tehe a^k parameetritega n = 13, a = 7 ja k = 12 ning võrgustik on avaldise a^k mod 13 täielik tabel.

Ava see ülesanne tööriistas
1. 7¹² on 13 841 287 201 — üksteist numbrit vastuse jaoks, mis peab tulema vahemikus 0 kuni 12. Taandamine säilib korrutamisel: korrutise jääk sõltub üksnes selle tegurite jääkidest, seega võid taandada pärast iga sammu, mitte alles lõpus.
  
  $7^{12}=13\,841\,287\,201,\qquad xy\bmod n=\big((x\bmod n)(y\bmod n)\big)\bmod n$
2. Fermati väike teoreem määrab vastuse enne igasugust arvutamist. Algarvu p ja sellise arvu a korral, mida p ei jaota, kehtib a^p−1 ≡ 1; siin on p = 13 ja k on täpselt p − 1, mistõttu tulemus on 1 ning kõik alljärgnev on teoreemi kontrollimine, mitte vastuse otsimine.
  
  $p=13\ \text{prime},\ \ 13\nmid7\quad\Longrightarrow\quad 7^{12}=7^{\,p-1}\equiv1\pmod{13}$
3. Ruutu võtmine kahekordistab astendajat, seega kolm ruutu võtmist viivad arvuni 7⁸. Igal real tehakse taandamine enne järgmise algust, mispärast ükski arv kogu arvutuses ei ületa arvu 100.
  
  $7^{2}=49\equiv10,\qquad 7^{4}\equiv10^{2}=100\equiv9,\qquad 7^{8}\equiv9^{2}=81\equiv3\pmod{13}$
4. 12 on 8 + 4 ning mõlemad need astmed arvutati teel ülespoole, seega viib veel üks korrutamine arvutuse lõpule. Kokku neli korrutamist, võrreldes üheteistkümnega, mida vajaks kaheteistkümne seitsme korrutamine vasakult paremale — ning kokkuhoid kasvab koos astendajaga, mitte mooduliga.
  
  $12=1100_{2}=8+4\quad\Longrightarrow\quad 7^{12}\equiv7^{8}\cdot7^{4}\equiv3\times9=27\equiv1\pmod{13}$
5. Arvu 7 järk ehk vähim k, mille korral 7^k ≡ 1, peab jagama arvu 12, seega on see üks arvudest 1, 2, 3, 4, 6 ja 12. Viie pärisjagaja kontrollimine välistab neist igaühe, seega on järk täpselt 12.
  
  $7^{1}\equiv7,\ 7^{2}\equiv10,\ 7^{3}\equiv5,\ 7^{4}\equiv9,\ 7^{6}\equiv12\quad\Longrightarrow\quad \operatorname{ord}_{13}(7)=12$
Vastus

Kolm ruutu võtmist ja lõpetav korrutamine taastavad veatult tööriista rea väärtusele a = 7: 10 kohal k = 2, 9 kohal k = 4, 3 kohal k = 8 ja 1 kohal k = 12, kus Fermat' kohaselt see pidi olema. Kuna järk on 12, mitte selle pärisjagaja — järgu test nõudis tulemust 12 kohal k = 6, mis ei ole 1 —, on see rida arvude 1 kuni 12 permutatsioon, läbides iga mittenullise jäägi täpselt ühe korra, mis teeb arvust 7 algjuure mooduli 13 järgi. Nüüd loe rida teises suunas: kui on antud 11, leia k. Selleks ei ole ruutimis-korrutamisalgoritmi, vaid üksnes otsing, ning see asümmeetria kerge edasisuuna ja raske tagasisuuna vahel on kogu Diffie–Hellmani võtmevahetuse alus. Algoritm skaleerub viisil, mida tabel ei suuda: 2048-bitine astendaja nõuab maksimaalselt umbes 4 000 mooduliga korrutamist, samal ajal kui selle nimetatud astme väljakirjutamine nõuaks umbes 2,7 × 10⁶¹⁶ numbrit.

$\operatorname{ord}_{13}(7)=12\quad\Longrightarrow\quad \{7^{k}\bmod 13\}_{k=1}^{12}=\{1,2,\ldots,12\}$

Õpitee

Kui kaks asja jõuavad sama väärtuseni

Allikad (1)

The congruence sign this tool prints, and the book that introduced it: C. F. Gauss, Disquisitiones arithmeticae. Leipzig, 1801 — Section I defines a ≡ b (mod n); Section II is where a prime modulus starts behaving like a field. Digitised by the Smithsonian Libraries.

7 Raven Roomi meeskond · Kontrollitud avaldatud allikate põhjal. Parandused on teretulnud.