Hoppa yfir í efnið

Stærðfræði dulritunar

Í síðasta kafla skoðuðum við klassískar dulritunaraðferðir sem notast við tilfærslur og mynstur á einföldum stafrófum. Það var góð leið til að kynnast grunnhugmyndum dulritunar, en nútímadulritun er þó allt annars eðlis og felur í sér töluverða stærðfræði.

Við ætlum því að kynna til leiks nokkur stærðfræðileg verkfæri sem mun bregða fyrir þegar við köfum dýpra. Markmiðið er að veita smá yfirsýn yfir helstu stærðfræðilegu hugtök sem notast er við í dulritun.

Leifareikningur

Byrjum á því að rifja upp hefðbundna deilingu. Tökum sem dæmi

\[ \frac{17}{5} = 3 \frac{2}{5}. \]

Niðurstaða deilingarinnar er að \(5\) gengur þrisvar sinnum upp í \(17\), þ.e. kvótinn er \(3\), og afgangurinn er \(2\).

Þegar kemur að leifareikningi (e. modular arithmetic) einbeitum við okkur að afgangnum, eða leifinni eins og hann er stundum kallaður, en hunsum kvótann.

Í leifareikningi notum við ritháttinn

\[ 17 \bmod 5 = 2 \]

til að tákna að leifin sé \(2\) þegar \(17\) er deilt með \(5\) og lesum \(17\) mátað við (e. modulo) \(5\) er \(2\).

Sýnidæmi

Reiknum \(29 \bmod 7\).

  1. Byrjum á því að finna stærsta margfeldi af 7 sem við komumst upp í án þess að fara yfir \(29\). Það er \(4 \cdot 7 = 28\).
  2. Við finnum þá hversu mikið vantar upp á til að við náum \(29\), þ.e. \(29 - 28 = 1\).
  3. Eftir stendur \(1\) og því er \(29 \bmod 7 = 1\).

Stundum ritum við

\[ 29 = 4 \cdot 7 + 1 \]

en þá sjáum við bæði kvótann og leifina.

Í Python og flestum öðrum forritunarmálum er prósentumerkið % notað sem leifareikningsvirkinn.

>>> 29 % 7
1
>>> 17 % 5
2

Æfing

Finndu eftirfarandi.

  1. \(23 \bmod 6\)
  2. \(100 \bmod 9\)
  3. \(48 \bmod 12\)
  4. \(7 \bmod 10\)
Lausn

Hér erum við að finna afganginn við deilingu:

  1. \(23 \bmod 6 = 5\), af því að \(23 = 3 \cdot 6 + 5\).
  2. \(100 \bmod 9 = 1\), af því að \(100 = 11 \cdot 9 + 1\).
  3. \(48 \bmod 12 = 0\), af því að 48 er deilanleg með 12, þ.e. \(48 = 4 \cdot 12\).
  4. \(7 \bmod 10 = 7\). Talan 10 gengur 0 sinnum upp í 7, þ.e. \(7 = 0 \cdot 10 + 7\). Góð regla er að ef talan vinstra megin er minni en talan hægra megin (deilirinn), þá er leifin alltaf bara talan sjálf.

Við getum sannreynt þessi svör í Python:

>>> [23 % 6, 100 % 9, 48 % 12, 7 % 10]
[5, 1, 0, 7]

Samleifa tölur

Tölurnar \(5\) og \(17\) eru vissulega ólíkar, en ef við mátum þessar tölur við \(12\) fáum við sömu niðurstöðu, þ.e.

\[ \begin{aligned} 5 \bmod 12 &= 5, \\ 17 \bmod 12 &= 5. \end{aligned} \]

Þar sem leifarnar eru þær sömu, segjum við í leifareikningi að \(5\) og \(17\) séu samleifa mátað við (e. congruent modulo) \(12\). Það þýðir einfaldlega að frá sjónarhóli tölunnar \(12\) lúta \(5\) og \(17\) sömu reglum.

Við notum \(\equiv\) (þrjú strik) til að tákna jafngildi, þ.e.

\[ a \equiv b \pmod n \]

sem við lesum sem \(a\) er sammáta (eða jafngilt) \(b\) modulo \(n\).

Staðhæfinguna hér að ofan getum við því táknað sem

\[ 17 \equiv 5 \pmod{12}. \]

Gagnleg leið til að hugsa um þetta er að tvær tölur eru sammáta ef munurinn á þeim gengur upp í töluna sem mátað er við. Við sjáum, til dæmis, að

\[ 17 - 5 = 12 \]

sem er einmitt deilanleg með 12.

Sýnidæmi

Reiknum

\[ (17 + 29) \bmod 12. \]

Við getum byrjað á því að leggja tölurnar fyrst saman og máta svo við \(12\), og fáum þá

\[ \begin{aligned} 17 + 29 &= 46, \\ 46 \bmod 12 &= 10 \end{aligned} \]

þar sem \(3 \cdot 12 = 36\) og \(46 - 36 = 10\).

Ef við prófum að máta \(17\) og \(29\) fyrst við \(12\) og leggja þær niðurstöður saman, fáum við

\[ \begin{aligned} 17 \bmod 12 &= 5, \\ 29 \bmod 12 &= 5, \\ 5 + 5 &= 10, \end{aligned} \]

sem kemur heim og saman við fyrri niðurstöðuna.

Skoðum annað dæmi sem felur í sér margfeldi,

\[ (17 \cdot 29) \bmod 12. \]

Ef við margföldum fyrst fáum við

\[ \begin{aligned} 17 \cdot 29 &= 493, \\ 493 \bmod 12 &= 1, \end{aligned} \]

en ef við mátum fyrst við \(12\) og margföldum svo endum við með

\[ \begin{aligned} 17 \bmod 12 &= 5, \\ 29 \bmod 12 &= 5, \\ 5 \cdot 5 &= 25, \\ 25 \bmod 12 &= 1. \end{aligned} \]

Aftur fáum við sömu niðurstöðu, en með seinni aðferðinni vinnum við með smærri tölur!

Margfeldi og deiling

Þá er rétt að spyrja sig, er það tilviljun að hægt var að reikna leifar áður en samlagning og margföldun átti sér stað í sýnidæminu? Nei, þessir eiginleikar leifareiknings gilda almennt og eru einmitt það sem gerir hann svo gagnlegan.

Reiknireglur leifa

Ef \(a \equiv b \pmod n\), \(a_1 \equiv b_1 \pmod n\) og \(a_2 \equiv b_2 \pmod n\), og \(k\) er heiltala, gilda eftirfarandi reglur

\[ \begin{equation} a + k \equiv b + k \pmod n \end{equation} \]
\[ \begin{equation} k a \equiv k b \pmod n \end{equation} \]
\[ \begin{equation} a_1 + a_2 \equiv b_1 + b_2 \pmod n \end{equation} \]
\[ \begin{equation} a_1 a_2 \equiv b_1 b_2 \pmod n \end{equation} \]
\[ \begin{equation} a^k \equiv b^k \pmod n \end{equation} \]

Þessar reglur sýna okkur að eiginleikar leifareiknings varðveitast hvort sem tölur eru lagðar eða margfaldaðar við leifarnar, leifar lagðar saman eða margfaldaðar, og einnig hafðar í hvaða veldi sem er.

Æfing

Nýttu þér tæknina sem við vorum að læra og reiknaðu eftirfarandi án þess að margfalda stórar tölur beint (þ.e. taktu leifarnar fyrst):

  1. \((38 + 27) \bmod 10\)
  2. \((38 \cdot 27) \bmod 10\)
  3. \((123 + 456) \bmod 7\)
  4. \((123 \cdot 456) \bmod 7\)
  5. \(120^{99} \bmod 7\)
Lausn

Mundu, lykillinn er að minnka tölurnar fyrst með því að finna leif þeirra.

  1. \(38 \bmod 10 = 8\) og \(27 \bmod 10 = 7\). Við leggjum saman leifarnar og fáum \(8 + 7 = 15\). Loks tökum við leifina aftur af útkomunni og fáum þá \(15 \bmod 10 = 5\).
  2. Með sömu leifum og að ofan getum við margfaldað \(8 \cdot 7 = 56\). Leifin verður þá \(56 \bmod 10 = 6\).
  3. Hér er mátað við 7. \(123 \bmod 7 = 4\), því \(17 \cdot 7 = 119\) og \(456 \bmod 7 = 1\), því \(65 \cdot 7 = 455\). Þá getum við einfaldlega lagt leifarnar saman: \(4 + 1 = 5\).
  4. Og aftur notum við leifarnar úr fyrra dæmi, en margföldum þær í staðinn og fáum \(4 \cdot 1 = 4\).
  5. Við höfum að \(120 \bmod 7 = 1\), því \(17 \cdot 7 = 119\) og leifin því \(1^{99} = 1\).

Þessar reglur eru ómissandi í dulritun. Þær gera tölvum kleift að vinna með gríðarlega stórar tölur, því hægt er að halda öllum niðurstöðum í skefjum með leifum.

Frumtölur og þáttun

Flestir hafa örugglega heyrt um frumtölur, en þær eru einn af hornsteinum nútímadulritunar. Frumtala (e. prime number) er heiltala, stærri en 1, sem er aðeins deilanleg með \(1\) og sjálfri sér.

Fyrstu frumtölurnar eru

\[ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, \ldots \]

Tökum \(7\) sem dæmi. Það er engin tala sem gengur upp í hana, þ.e. hún er ekki deilanleg með neinni tölu, nema \(1\) og \(7\). Aftur á móti er 12 ekki frumtala, því við henni má deila með \(2\), \(3\), \(4\) og \(6\). Við köllum tölur sem eru ekki frumtölur samsettar (e. composite number).

Allar jákvæðar heiltölur stærri en 1 eru í raun byggðar úr frumtölum. Við getum tekið hvaða samsetta tölu sem er og skrifað hana sem margfeldi frumtalna. Þetta ferli kallast frumþáttun (e. prime factorization).

Sýnidæmi

Prófum að frumþátta töluna 84. Þægilegt er að byrja á minnstu mögulegu frumtölunni (sem er 2) og athuga hvort hún gangi upp.

Talan 84 er slétt, þannig að 2 gengur upp í hana, og við höfum

\[ 84 = 2 \cdot 42. \]

Talan 42 er líka slétt, þannig að við deilum aftur með 2 og fáum

\[ 42 = 2 \cdot 21. \]

Talan 2 gengur ekki upp í 21, en við vitum að 3 gengur upp í hana, og við fáum því

\[ 21 = 3 \cdot 7. \]

Nú sitjum við uppi með 7, sem við vitum að er frumtala. Ferlinu er því lokið!

Við getum nú sett þetta allt saman og fáum þá að frumþáttun 84 er

\[ 84 = 2 \cdot 2 \cdot 3 \cdot 7. \]

Ef sama frumtalan er endurtekin, er hún oftast sett fram sem veldi

\[ 84 = 2^2 \cdot 3 \cdot 7. \]

Ástæðan fyrir því að frumþáttun er mikilvæg í dulritun er sú að það er mjög auðvelt fyrir tölvur að margfalda tvær stórar frumtölur saman, en það er mjög erfitt, þ.e. tekur langan tíma, að taka stóra tölu og reyna að finna út hvaða tvær frumtölur voru margfaldaðar saman til að búa hana til. Við munum sjá þetta í verki þegar við skoðum RSA-dulritunina.

Æfing

Nú er röðin komin að þér.

  1. Skoðaðu tölurnar \(17\), \(21\), \(23\) og \(27\). Hverjar þeirra eru frumtölur?
  2. Frumþáttaðu töluna \(60\).
Lausn

  1. Skoðum hverja tölu fyrir sig.

    • \(17\) er frumtala, því ekkert annað en 1 og 17 gengur upp í hana.
    • \(21\) er ekki frumtala, því \(3 \cdot 7 = 21\).
    • \(23\) er frumtala.
    • \(27\) er ekki frumtala, því \(3 \cdot 9 = 27\).

  2. Brjótum 60 niður skref fyrir skref. 60 er slétt, svo við byrjum á 2 og fáum

    \[ 60 = 2 \cdot 30. \]

    30 er líka slétt svo við deilum aftur með tveimur og fáum

    \[ 30 = 2 \cdot 15. \]

    15 er ekki slétt, en er deilanleg með 3, sem gefur okkur

    \[ 15 = 3 \cdot 5. \]

    Fimm er frumtala, svo við erum komin á endastöð. Frumþáttunin er því

    \[ 60 = 2 \cdot 2 \cdot 3 \cdot 5 = 2^2 \cdot 3 \cdot 5. \]

Stærsti sameiginlegi deilirinn

Margir muna eflaust eftir því að hafa þurft að fullstytta brot á borð við

\[ \frac{180}{420} = \frac{3}{7} \]

Brot telst fullstytt ef teljarinn og nefnarinn hafa enga sameiginlega þætti, þ.e.a.s. að það sé ekki til nein tala sem gengur upp í bæði teljarann og nefnarann. Til að fullstytta brot, þurfum við því að finna stærstu tölu sem gengur upp í teljarann og nefnarann, \(60\) í dæminu hér að ofan, og stytta brotið um hana.

Þessa tölu, þ.e. stærsta tala sem gengur upp í tvær tölur, köllum við stærsta sameiginlega deilinn (eða stærsta samdeilinn) (e. greatest common divisor, oft stytt í GCD).

Tökum tölurnar 18 og 24 sem dæmi. Allar tölur sem ganga upp í 18 (þ.e. deilar 18) eru

\[ 1, 2, 3, 6, 9, 18. \]

Allar tölur sem ganga upp í 24 eru

\[ 1, 2, 3, 4, 6, 8, 12, 24. \]

Ef við berum listana saman sjáum við að stærsta talan sem er á báðum listum er 6. Stærsti samdeilir þeirra er því 6, sem við táknum með

\[ \gcd(18, 24) = 6. \]

Reiknirit Evklíðs

Það er einfalt að finna \(\gcd\) þegar tölurnar eru litlar og hægt er að skrifa upp alla mögulega deila, eins og við gerðum hér að ofan. En hvað ef tölurnar eru rosalega stórar?

Gríski stærðfræðingurinn Evklíð (um 300 árum f.Kr.) uppgötvaði aðferð til að finna stærsta samdeili sem notast við leifareikning. Reiknirit Evklíðs virkar þannig að við deilum stærri tölunni með minni tölunni, finnum leifina, og endurtökum svo leikinn. Leifin verður alltaf nýr deilir og gamli deilirinn verður talan sem verið er að deila í. Við höldum þessu áfram þar til leifin verður 0. Síðasta leifin (sem var ekki núll) er stærsti sameiginlegi deilirinn!

Sýnidæmi

Notum reiknirit Evklíðs til að finna \(\gcd(252, 105)\).

  1. Skref: Deilum 252 með 105. Talan 105 gengur 2 sinnum í 252 (það gerir 210), svo leifin er 42.

    \[ 252 = (2 \cdot 105) + 42 \]

  2. Skref: Tökum nú 105 (gamla deilirinn) og deilum með 42 (gömlu leifinni). Talan 42 gengur 2 sinnum í 105 (það gerir 84), svo leifin er 21.

    \[ 105 = (2 \cdot 42) + 21 \]

  3. Skref: Tökum nú 42 og deilum með 21. Talan 21 gengur nákvæmlega 2 sinnum upp í 42 (það gerir 42), svo leifin er 0!

    \[ 42 = (2 \cdot 21) + 0 \]

Um leið og leifin er orðin 0 stoppum við. Síðasta leifin sem var ekki núll var 21. Reiknirit Evklíðs gefur okkur því að

\[ \gcd(252, 105) = 21. \]

Python býður upp á fallið gcd í math safninu til að finna stærsta samdeili.

from math import gcd

>>> gcd(252, 105)
21

Æfing

Prófaðu að nota reiknirit Evklíðs til að leysa eftirfarandi verkefni.

  1. \(\gcd(48, 18)\)
  2. \(\gcd(101, 23)\)
  3. \(\gcd(84, 30)\)
Lausn

  1. Finnum \(\gcd(48, 18)\):

    \[ \begin{aligned} 48 &= (2 \cdot 18) + 12, && \text{leifin er } 12, \\ 18 &= (1 \cdot 12) + 6, && \text{leifin er } 6, \\ 12 &= (2 \cdot 6) + 0, && \text{leifin er } 0. \end{aligned} \]

    Síðasta leifin sem var ekki núll var 6, svo \(\gcd(48, 18) = 6\).

  2. Finnum \(\gcd(101, 23)\):

    \[ \begin{aligned} 101 &= (4 \cdot 23) + 9, && \text{leifin er } 9, \\ 23 &= (2 \cdot 9) + 5, && \text{leifin er } 5, \\ 9 &= (1 \cdot 5) + 4, && \text{leifin er } 4, \\ 5 &= (1 \cdot 4) + 1, && \text{leifin er } 1, \\ 4 &= (4 \cdot 1) + 0, && \text{leifin er } 0. \end{aligned} \]

    Hér var síðasta leifin (áður en hún varð núll) 1. Það þýðir að \(\gcd(101, 23) = 1\).

  3. Finnum \(\gcd(84, 30)\):

    \[ \begin{aligned} 84 &= (2 \cdot 30) + 24, && \text{leifin er } 24, \\ 30 &= (1 \cdot 24) + 6, && \text{leifin er } 6, \\ 24 &= (4 \cdot 6) + 0, && \text{leifin er } 0. \end{aligned} \]

    Því er \(\gcd(84, 30) = 6\).

Þegar \(\gcd(a, n) = 1\), þýðir það einfaldlega að tölurnar tvær eiga engan sameiginlegan deili annan en \(1\). Það þýðir ekki að báðar tölurnar séu endilega frumtölur (t.d. er \(\gcd(8,9) = 1\), þar sem hvorug er frumtala), heldur aðeins að þær deila engum frumþáttum. Tölur sem uppfylla þetta skilyrði eru sagðar vera ósamþátta (e. coprime eða mutually prime).

Margföldunarandhverfur

Allar ræðar tölur, nema 0, eiga sér svokallaða margföldunarandhverfu (e. multiplicative inverse). Margföldunarandhverfa tölunnar \(a\) er talan \(x\) sem uppfyllir það að \(a x = 1\).

Í heimi ræðra talna er einfalt að finna þær, en margföldunarandhverfa \(a\) er einfaldlega \(\frac{1}{a}\), stundum táknuð með \(a^{-1}\). Þannig er, til dæmis, \(\frac{1}{3}\) margföldunarandhverfa \(3\).

Í leifareikningi getum við einnig skilgreint margföldunarandhverfur, en á aðeins annan hátt. Þar segjum við að margföldunarandhverfa tölunnar \(a\) (modulo \(n\)) sé heiltala \(x\) sem uppfyllir

\[ a x \equiv 1 \pmod n. \]

Með öðrum orðum þá er margföldunarandhverfa \(a\) sú tala \(x\) sem, ef margfölduð við \(a\) gefur okkur 1, eftir að hún er mátuð við \(n\). Þetta má einnig orða sem: með hverju þarf ég að margfalda \(a\) til þess að afgangurinn af þeirri margföldun verði nákvæmlega 1 þegar ég deili með \(n\)?

Í leifareikningi vinnum við þó eingöngu með heiltölur, en ekki brot, svo sömu lögmál gilda ekki hér og með ræðu tölurnar. Til að finna margföldunarandhverfur þurfum við því að prófa okkur áfram.

Sýnidæmi

Prófum að finna margföldunarandhverfu 3 mátað við 7. Við erum semsagt að leita að einhverri tölu, köllum hana \(x\), svo að þegar við reiknum \((3 \cdot x) \bmod 7\) fáum við 1.

Þar sem við erum að máta við 7 getum við prófað allar tölurnar frá 1 upp í 6 og séð hvort einhver þeirra gefi okkur 1:

\[ \begin{aligned} x = 1:\quad &3 \cdot 1 = 3, &&3 \bmod 7 = 3, \\ x = 2:\quad &3 \cdot 2 = 6, &&6 \bmod 7 = 6, \\ x = 3:\quad &3 \cdot 3 = 9, &&9 \bmod 7 = 2, \\ x = 4:\quad &3 \cdot 4 = 12, &&12 \bmod 7 = 5, \\ x = 5:\quad &3 \cdot 5 = 15, &&15 \bmod 7 = 1. \end{aligned} \]

Við sjáum hér að þegar við margföldum 3 með 5 fáum við 15, sem hefur leifina 1 þegar deilt er með 7. Talan 5 er því margföldunarandhverfa 3.

Þetta getum við táknað með

\[ 3^{-1} \equiv 5 \pmod 7 \]

Athugum þó að það er alls ekki víst að slík andhverfa sé alltaf til. Tökum töluna 6 mátaða við 12 sem dæmi. Getum við fundið margföldunarandhverfu 6? Prófum að margfalda hana við 1, 2, 3, o.s.frv.

\[ \begin{aligned} 6 \cdot 1 &= 6 \equiv 6 \pmod{12}, \\ 6 \cdot 2 &= 12 \equiv 0 \pmod{12}, \\ 6 \cdot 3 &= 18 \equiv 6 \pmod{12}, \\ 6 \cdot 4 &= 24 \equiv 0 \pmod{12}. \end{aligned} \]

Eins og sést munum við aldrei fá 1, þar sem niðurstaðan er ýmist 0 eða 6. Í þessu tilfelli er því engin margföldunarandhverfa til.

Hvernig getum við þá vitað hvort andhverfa er til eða ekki, án þess að þurfa að prófa okkur áfram?

Margföldunarandhverfur

Heiltalan \(a\) á sér margföldunarandhverfu, mátað við \(n\), ef og aðeins ef \(\gcd(a,n) = 1\).

Við þurfum því aðeins að finna stærsta samdeili til að ákvarða hvort margföldunarandhverfa sé til eða ekki.

Æfing

  1. Finndu margföldunarandhverfu 5 mátað við 12.
  2. Á 8 margföldunarandhverfu mátað við 15? Ef svo er, finndu hana.
  3. Á 6 margföldunarandhverfu mátað við 15?
Lausn

  1. Við erum að leita að \(x\) svo að \((5 \cdot x) \bmod 12 = 1\). Við prófum okkur áfram:

    \[ \begin{aligned} 5 \cdot 1 &= 5, \\ 5 \cdot 2 &= 10, \\ 5 \cdot 3 &= 15, &15 \bmod 12 &= 3, \\ 5 \cdot 4 &= 20, &20 \bmod 12 &= 8, \\ 5 \cdot 5 &= 25, &25 \bmod 12 &= 1. \end{aligned} \]

    Margföldunarandhverfa \(5\) mátað við \(12\) er því talan sjálf, \(5\).

  2. Fyrst finnum við stærsta samdeili. Tölurnar sem ganga upp í 8 eru (1, 2, 4, 8) en tölurnar sem ganga upp í 15 eru (1, 3, 5, 15). Eini sameiginlegi deilirinn er 1. Því er \(\gcd(8, 15) = 1\) og margföldunarandhverfa því til. Við byrjum að prófa og sjáum að

    \[ 8 \cdot 2 = 16 \quad\text{og}\quad 16 \bmod 15 = 1. \]

    Andhverfan er því \(2\).

  3. Við sjáum að 3 gengur bæði upp í 6 og upp í 15, svo \(\gcd(6, 15) = 3 \neq 1\). Margföldunarandhverfan er því ekki til.

Veldareikningur með leifum

Nútíma dulritunaraðferðir notast oft við gríðarlega stór veldi, mátuð við minni tölur, þ.e. \(a^k \bmod n\), þar sem \(a\) og \(k\) eru stórar tölur. Ef við viljum byrja á að reikna \(a^k\) og finna svo leifina, þurfum við að vinna með mjög stórar tölur sem taka mikið minni, þrátt fyrir að við vitum að svarið getur aldrei verið hærra en \(n\).

Þegar þessi veldi eru reiknuð er því notast við veldaregluna (5), í reiknireglu leifa, þ.e. ef \(a \equiv b \pmod n\), og \(k\) er heiltala, gildir

\[ a^k \equiv b^k \pmod n. \]

Þessi regla, í bland við reiknirit sem kallast veldareikningur með leifum (e. modular exponentiation), vinnur oft eftir aðferð sem kallast að drottna og deila (e. divide-and-conquer). Við ætlum ekki að kafa djúpt í þessa aðferð hér, en sýnum hana með dæmi.

Sýnidæmi

Finnum \(2^{10} \bmod 7\).

Hugmyndin er að nota vísisreglur veldareiknings, sem gefur okkur að \((x^a)^b = x^{ab}\).

Fyrst reiknum við \(2^2 = 4\). Talan 4 er minni en 7, svo \(2^2 \bmod 7 = 4\).

Næst reiknum við \(2^4 = (2^2)^2\), þ.e. \(2^2\) margfaldað við sjálft sig og fáum þá

\[ 2^4 = (2^2)^2 \equiv 4^2 = 16 \equiv 2 \pmod 7. \]

Næst reiknum við \(2^8\), sem er \(2^4\) í öðru veldi

\[ 2^8 \equiv 2^2 = 4 \pmod 7. \]

Nú getum við ekki hafið \(2^8\) aftur í annað veldi, því þá höfum við \(2^{16}\) sem er stærri en talan sem við erum að leita að. En við munum að hefðbundnar veldareglur gefa okkur

\[ 2^{10} = 2^{8+2} = 2^8 \cdot 2^2. \]

Við höfum, nú þegar, fundið báðar þessar stærðir og getum því notað margföldunarregluna í reiknireglum leifa og fáum þá

\[ 2^{10} = 2^8 \cdot 2^2 \equiv 4 \cdot 4 = 16 \equiv 2 \pmod 7. \]

Því er \(2^{10} \bmod 7 = 2\).

Með þessu dæmi sjáum við að leifareglurnar gæta þess að tölurnar sem við vinnum með verði ekki of stórar, á meðan reikniritið sér til þess að við þurfum aðeins að beita fjórum margföldunum til að finna \(2^{10}\), í stað níu, þ.e. \(2 \cdot 2 \cdot 2 \cdots 2\), 10 sinnum.

Python býður upp á skilvirka leið fyrir veldareikninga með leifum. Innbyggða fallið pow tekur þrjár færibreytur: veldisstofninn (töluna), veldið og leifina.

>>> pow(2, 10, 7)
2

Af hverju skiptir þetta máli í dulritun?

Af hverju skipta leifar, margföldunarandhverfur og frumtölur eiginlega máli í verndun upplýsinga?

Ástæðan er sú að öll þessi tól sem við höfum verið að safna eru undirstaðan í því að búa til það sem kallað er einátta fall (e. one-way function). Dulritun snýst í grunninn um að búa til kerfi þar sem mjög „auðvelt“ er að reikna í aðra áttina (að dulrita og læsa gögnum), en „stjarnfræðilega erfitt“ (helst nánast ómögulegt), að reikna í hina áttina (að dulráða), nema maður sé með upplýsingar sem einfalda reikningana, þ.e. leynda lykilinn.

Verkefni

Hér má finna öll verkefnin úr efni þessa kafla.

Opna verkefni