Modulaarinen eksponentio

Tämän matematiikkaartikkelin sisältö on tarkistettava (Tammikuu 2014).

Paranna sitä tai keskustele tarkistettavista asioista . Jos olet juuri kiinnittänyt bannerin, ilmoita tarkistettavat kohdat täällä .

On matematiikka , tarkemmin sanoen modulaarinen aritmetiikka , modulaarinen potenssiin korotuksen on eräänlainen eksponentiaation ( potenssiinkorotusta ) suoritetaan modulo kokonaisluku . Sitä käytetään erityisesti tietojenkäsittelytieteessä , erityisesti salauksen alalla .

Yleensä modulaariset eksponenttiongelmat ilmaistaan seuraavassa muodossa: kun otetaan huomioon perusta b , eksponentti e ja kokonaisluku m, haluamme laskea c siten, että:

c \ equiv b ^ {e} {\ pmod {m}}

Jos b , e ja m ovat positiivisia tai nolla ja b < m , On olemassa ainutlaatuinen ratkaisu c , joka . Esimerkiksi, jos b = 5, e = 3 ja m = 13, c: n laskeminen antaa 8. $0 \ leq c <m$

Edellisen esimerkin kaltaisia modulaarisia eksponentointiongelmia pidetään helposti ratkaistavissa, vaikka mukana olevat lukumäärät ovat valtavat. Päinvastoin, lasketaan diskreetin logaritmin (löytää e päässä b , c ja m ) on tunnustettu vaikeaksi. Tämä yksisuuntainen toimintakäyttäytyminen tekee modulaarisesta eksponentiosta hyvän ehdokkaan käytettäväksi salauksen algoritmeissa .

Yleinen esitys

Naiivi laskeminen modulaarinen eksponentiaalinen on seuraava: me moninkertaisesti e kertaa enemmän b itse, ja kun kokonaisluku b e on saatu, laskemme sen loppuosa modulo m kautta jakoyhtälö algoritmi . Tämä menetelmä kärsii kahdesta puutteesta:

toisaalta kertolaskujen määrää voidaan helposti vähentää yleisen nopean eksponention menetelmällä : suoritettavina on vain log (e) -kertoja.
toisaalta emme hyödynnä toimialueen kommutatiivista rengasrakennetta : kokonaislukuja modulo m . Tämän rakenteen avulla laskelmat voidaan kuitenkin tehdä suoraan tässä renkaassa käymättä kokonaislukuja etukäteen läpi. Toteuttaakseen tämän idean, on välttämätöntä käytännössä jokaisen uuden kertominen suoritetaan, lasketaan uusi jakojäännös modulo m . Lisäämme siten uusia operaatioita (jokaiselle kertolaskulle Euklidisen jako), mutta hyötymme myös siitä, että käsiteltävän datan kokoa rajoittaa m .

Artikkelin loppuosassa kuvataan näitä erilaisia mukautuksia ja käsitellään niiden tehokkuutta erityisesti tietojen koosta riippuen.

Suora menetelmä

Suorin tapa laskea modulaarinen eksponentti on laskea b e suoraan ja ottaa sitten tämä luku modulo m . Yritetään laskea c , jossa b = 4, e = 13 ja m = 497:

{\ displaystyle c \ equiv 4 ^ {13} \ {\ pmod {497}}.}

Lasketaan laskimella 4 13 laskin, jolloin saadaan arvo 67 108 864. Ota tämä moduuli 497, saatu tulos c on 445. Vaikka b: llä on vain yksi numero ja e kaksi, arvo b e saavuttaa yhden 8 numeroa.

Vahvassa kryptologiassa b: llä on usein vähintään 256 binäärilukua (77 desimaalilukua). Otetaan b = 5 × 10 76 ja e = 17, kaksi täysin kohtuullista arvoa. Tässä esimerkissä b on 77 desimaalia ja E kaksi, mutta b e on 1304 numeroa. Tällaiset laskelmat ovat mahdollisia nykyaikaisilla tietokoneilla, mutta tällaisen luvun valtavuus hidastaa huomattavasti laskentanopeutta. Kun b: n ja e: n koko kasvaa salauksen turvallisuuden parantamiseksi, b e: n arvoa ei voida hallita.

Eksponentoinnin suorittamiseen tarvittava aika riippuu käyttöympäristöstä ja prosessorista. Eksponention laskeminen kerrannaissarjalla vaatii ajan O ( e ).

Menetelmä käyttää vähemmän muistia

Toinen menetelmä modulaarisen eksponention laskemiseksi vaatii enemmän toimintoja kuin ensimmäinen menetelmä. Pienemmästä muistivaatimuksesta johtuen toiminnot vievät vähemmän aikaa kuin aikaisemmin. Tämän seurauksena tämä algoritmi voi olla nopeampi:

joko vaihtamalla välimuistia (välimuisti) ja muistia vähemmän ,
tai käyttämällä vähemmän vaihtamista virtuaalimuistin tapauksessa .

Tämä algoritmi käyttää sitä tosiasiaa, että kahdelle annetulle kokonaisluvulle b ja c ensimmäiset relaatiot tarkoittavat seuraavaa:

b ^ {{\ prime}} \ equiv b \ {\ pmod {m}} \ {{\ rm {et}}} \ c ^ {{\ prime}} \ equiv c \ {\ pmod {m}}

b ^ {{\ prime}} c ^ {{\ prime}} \ equiv bc \ {\ pmod {m}}

Seuraava algoritmi:

Aseta c = 1, e ' = 0.
Lisää e ' 1: llä.
Laske . $c \ equiv (b \ cdot c) \ {\ pmod {m}}$
Jos e ' < e , siirry vaiheeseen 2. Muussa tapauksessa c sisältää oikean ratkaisun . $c \ equiv b ^ {e} {\ pmod {m}}$

Huomaa, että aina kun käydään läpi vaihe 3, yhtälöstä tulee totta. Kun vaihe 3 on suoritettu nnen kerran, sitten c sisältää vastauksen, joka on haettu. $c \ equiv b ^ {{e '}} \ {\ pmod {m}}$

Palatkaamme takaisin esimerkkiin b = 4, e = 13 ja m = 497. Algoritmi käy läpi vaiheen 3 13 kertaa:

e ' = 1.c = (4 x 1) (mod 497) = 4 (mod 497) = 4 .
e ' = 2.c = (4 x 4) (mod 497) = 16 (mod 497) = 16 .
e ' = 3.c = (4 x 16) (mod 497) = 64 (mod 497) = 64 .
e ' = 4 c = (4 x 64) (mod 497) = 256 (mod 497) = 256 .
e ' = 5 c = (4 x 256) (mod 497) = 1024 (mod 497) = 30 .
e ' = 6 c = (4 x 30) (mod 497) = 120 (mod 497) = 120 .
e ' = 7. c = (4 x 120) (mod 497) = 480 (mod 497) = 480 .
e ' = 8. c = (4 x 480) (mod 497) = 1920 (mod 497) = 429 .
e ' = 9 c = (4 x 429) (mod 497) = 1716 (mod 497) = 225 .
e ' = 10. c = (4 x 225) (mod 497) = 900 (mod 497) = 403 .
e ' = 11. c = (4 x 403) (mod 497) = 1612 (mod 497) = 121 .
e ' = 12. c = (4 x 121) (mod 497) = 484 (mod 497) = 484 .
e ' = 13. c = (4 x 484) (mod 497) = 1936 (mod 497) = 445 .

Lopullinen vastaus C on siis 445, kuten ensimmäisessä menetelmässä.

Ensimmäisen menetelmän tavoin tämä vaatii laskennan ajan O ( e ): ssä. Koska näissä laskelmissa käytetyt luvut ovat pienempiä kuin ensimmäisen algoritmin laskelmissa käytetyt numerot, tämän menetelmän vakiotekijä on yleensä pienempi.

Tehokkain menetelmä

Kolmas menetelmä vähentää dramaattisesti sekä operaatioiden määrää että muistitilaa, joka tarvitaan modulaarisen eksponention suorittamiseen. Se on yhdistelmä edellisestä menetelmästä ja yleisemmästä periaatteesta, jota kutsutaan nopeaksi (tunnetaan myös nimellä neliösuuntainen eksponentointi).

Ensinnäkin meidän täytyy muuntaa eksponentin e osaksi binary merkintätapa , eli kirjoitetaan:

{\ displaystyle e = \ summa _ {i = 0} ^ {n-1} a_ {i} 2 ^ {i}.}

Tässä merkintätavassa pituus on e on n bittiä. a i voi ottaa arvon 0 tai 1 mille tahansa i: lle siten, että 0 ≤ i < n - 1. Määritelmän mukaan a n - 1 = 1.

Arvo b e voidaan sitten kirjoittaa:

{\ displaystyle b ^ {e} = b ^ {\ vasen (\ summa _ {i = 0} ^ {n-1} a_ {i} 2 ^ {i} \ oikea)} = \ prod _ {i = 0 } ^ {n-1} \ vasen (b ^ {2 ^ {i}} \ oikea) ^ {a_ {i}}.}

Ratkaisu v on siis:

{\ displaystyle c \ equiv \ prod _ {i = 0} ^ {n-1} \ vasen (b ^ {2 ^ {i}} \ oikea) ^ {a_ {i}} \ {\ pmod {m}} .}

Tällainen algoritmi voidaan helposti toteuttaa ohjelmointikielellä, jolla on käyttäjän ylikuormituksia ja roskien keräilijöitä . Seuraava esimerkki on C #: ssä . Bignum- luokka edustaa mielivaltaista suurta positiivista lukua. Tulomuuttujat ovat perusta varten pohjan ( b ), exp eksponentti ( e ), ja m moduulin.

Bignum modpow(Bignum base, Bignum exp, Bignum m) { Bignum result = 1; while (exp > 0) { if ((exp & 1) > 0) result = (result * base)b% m; exp >>= 1; base = (base * base)*% m; } return result; }

Tämä koodi, joka perustuu yhteen sivulla 244 Applied Cryptography mukaan Bruce Schneier , 2 th ed. ( ISBN 0471117099 ) , käyttää while-silmukkaa tekemään kaikki modulaarisen eksponention laskemiseen tarvittavat työt.

Huomaa, että ensimmäisen kerran annat silmukkaselaimeen, pohja muuttuja sisältää b . Sitten toistuva neliöinti koodin kolmannella rivillä varmistaa, että jokaisen silmukan lopussa muuttujapohja on sama , missä i on silmukan iteraatioiden määrä. (Mikä tekee i: stä seuraavan bitin, joka käsitellään binäärisessä eksponentissa exp , vähiten merkitsevä bitti, joka on exp 0 ). $b ^ {{2 ^ {i}}} \ {\ pmod {m}}$

Ensimmäinen koodirivi suorittaa yksinkertaisesti kertomisen . Jos a i on nolla, koodia ei suoriteta, mikä vastaa kokonaismäärän kertomista yhdellä. Jos toisaalta i on yhtä suuri kuin yksi, tulos on yksinkertaisesti kerrotaan emäs muuttuja (sisältää arvon alkuperäisen emäs). $\ prod _ {{i = 0}} ^ {{n-1}} \ vasen (b ^ {{2 ^ {i}}} \ oikea) ^ {{a_ {i}}} \ {\ pmod {m }}$ $b ^ {{2 ^ {i}}} \ {\ pmod {m}}$

Testataan lopuksi esimerkillä b = 4, e = 13 ja m = 497. Huomaa, että e on binaarisesti yhtä suuri kuin 1101. Koska e on neljä binäärilukua pitkä, silmukka toimii vain neljä kertaa:

Kun syötät silmukan ensimmäistä kertaa, muuttujien arvot ovat: base = 4, exp = 1101 (binääri) ja tulos = 1. Koska exp: n oikeanpuoleisin bitti on 1, tulos korvataan (1 × 4) mod 497, ts. 4 . exp on sitten katkaistu oikealla ja tulee 110 (binaari), ja pohja potenssiin olla (4 x 4) mod 497, eli 16.
Silmukan toisessa suorituksessa exp: n oikeanpuoleisin bitti on 0, joten tulosta ei muuteta. exp on sitten oikeanpuoleinen katkaistu ja siitä tulee 11 (binaarinen), ja pohja on neliömetri (16 × 16) mod 497, ts. 256.
Silmukan kolmannessa suorituksessa exp: n oikeanpuoleisin bitti on 1. Tulos korvataan moduulilla (4 × 256) mod 497, ts. 30 . exp on sitten oikeanpuoleinen katkaistu ja siitä tulee 1, ja pohja neliöitetään (256 × 256) modiksi 497, ts. 429.
Silmukan neljännessä suorituksessa exp: n oikeanpuoleisin bitti on 1. Tulos korvataan (30 × 429) modilla 497, ts. 445 . exp katkaistaan sitten oikealta ja siitä tulee 0, ja perusta neliöidään yhtä suureksi kuin (429 × 429) mod 497, toisin sanoen 151. (Huomaa, että tämä viimeinen emäs * emäskerroin on järjestelmällisesti hyödytön halutun tuloksen jälkeen, täällä 445 , on jo tiedossa.)

Silmukka päättyy sitten, koska exp on nolla, ja tulos 445 palautetaan. Tämä on sopusoinnussa kahden edellisen algoritmin kanssa.

Tämän algoritmin suoritusaika on O (log e ). Kun työskentelet suurten e- arvojen kanssa , se on paljon nopeampi kuin edelliset kaksi algoritmia.

Huomautuksia ja viitteitä

(fr) Tämä artikkeli on osittain tai kokonaan otettu englanninkielisestä Wikipedia- artikkelista " Modulaarinen eksponentio " ( katso luettelo kirjoittajista ) . <img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">