Modulaire machtsverheffing - Modular exponentiation

Modulaire machtsverheffing is een type machtsverheffing uitgevoerd over een modulus . Het is nuttig in de informatica , vooral op het gebied van cryptografie met openbare sleutels .

De werking van modulaire machtsverheffing berekent de rest wanneer een geheel getal b (de basis) verheven tot de e macht (de exponent), b ^e , wordt gemoduleerd over een positief geheel getal m (de modulus). In symbolen, gegeven grondtal b , exponent e en modulus m , is de modulaire machtsverheffing c : c = b ^e mod m . Uit de definitie van c volgt dat 0 ≤ c < m .

Bijvoorbeeld, gegeven b = 5 , e = 3 en m = 13 , is de oplossing c = 8 de rest van het moduleren van 5 ³ = 125 over 13 .

Modulaire machtsverheffing kan worden uitgevoerd met een negatieve exponent e door de modulaire multiplicatieve inverse d van b modulo m te vinden met behulp van het uitgebreide Euclidische algoritme . Dat is:

c = b ^e mod m = d ^{- e} mod m , waarbij e <0 en b ⋅ d ≡ 1 (mod m ) .

Modulaire machtsverheffing vergelijkbaar met degene die hierboven is beschreven, wordt als gemakkelijk te berekenen beschouwd, zelfs als de betrokken gehele getallen enorm zijn. Aan de andere kant wordt aangenomen dat het berekenen van de modulaire discrete logaritme - dat wil zeggen, de taak om de exponent e te vinden als b , c en m gegeven wordt - moeilijk is. Dit eenrichtingsfunctiegedrag maakt modulaire machtsverheffing een kandidaat voor gebruik in cryptografische algoritmen.

Directe methode

De meest directe methode om een ​​modulaire exponent te berekenen is om b ^e direct te berekenen en vervolgens dit getal modulo m te nemen . Overweeg om c te berekenen , gegeven b = 4 , e = 13 en m = 497 :

c ≡ 4 ¹³ (mod 497)

Je zou een rekenmachine kunnen gebruiken om 4 ¹³ te berekenen ; dit komt uit op 67.108.864. Als we deze waarde modulo 497 nemen, wordt het antwoord c bepaald op 445.

Merk op dat b slechts één cijfer lang is en dat e slechts twee cijfers lang is, maar de waarde b ^e is 8 cijfers lang.

Bij sterke cryptografie is b vaak minimaal 1024 bits . Beschouw b = 5 × 10 ⁷⁶ en e = 17 , die beide volkomen redelijke waarden zijn. In dit voorbeeld is b 77 cijfers lang en e 2 cijfers lang, maar de waarde b ^e is 1.304 decimale cijfers lang. Dergelijke berekeningen zijn mogelijk op moderne computers, maar door de enorme omvang van dergelijke getallen neemt de snelheid van berekeningen aanzienlijk af. Naarmate b en e nog verder toenemen om een ​​betere beveiliging te bieden, wordt de waarde b ^e onpraktisch.

De tijd die nodig is om de machtsverheffing uit te voeren, is afhankelijk van de besturingsomgeving en de processor. De hierboven beschreven methode vereist O ( e ) vermenigvuldigingen om te voltooien.

Geheugenefficiënte methode

Om de aantallen kleiner te houden, zijn extra modulaire reductiebewerkingen nodig, maar de kleinere omvang maakt elke bewerking sneller, waardoor in het algemeen tijd (en geheugen) wordt bespaard.

Dit algoritme maakt gebruik van de identiteit

( A ⋅ b ) mod m = [( a mod m ) ⋅ ( b mod m )] mod m

Het gewijzigde algoritme is:

1. Stel c = 1 in , e′ = 0 .
2. Verhoog e′ met 1.
3. Stel c = (b c) mod m in .
4. Als e′ < e , ga dan naar stap 2. Anders bevat c de juiste oplossing voor c ≡ b ^e (mod m ) .

Merk op dat in elke doorgang door stap 3, de vergelijking c ≡ b ^{e '} (mod m ) geldt. Als stap 3 e keer is uitgevoerd , dan bevat c het gezochte antwoord. Kortom, dit algoritme telt in principe up e ' door degenen die tot e' bereikt e , het doen van een vermenigvuldigen met b en een modulo operatie elke keer voegt een (te zorgen dat de resultaten blijven klein).

Het voorbeeld b = 4 , e = 13 en m = 497 wordt opnieuw gepresenteerd. Het algoritme doorloopt stap 3 dertien keer:

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

Het uiteindelijke antwoord voor c is dus 445, net als bij de eerste methode.

Net als de eerste methode vereist dit O( e ) vermenigvuldigingen om te voltooien. Omdat de getallen die in deze berekeningen worden gebruikt echter veel kleiner zijn dan de getallen die in de berekeningen van het eerste algoritme zijn gebruikt, neemt de rekentijd bij deze methode met een factor van ten minste O( e ) af .

In pseudocode kan deze methode op de volgende manier worden uitgevoerd:

function modular_pow(base, exponent, modulus) is
    if modulus = 1 then
        return 0
    c := 1
    for e_prime = 0 to exponent-1 do
        c := (c * base) mod modulus
    return c

Binaire methode van rechts naar links

Een derde methode vermindert drastisch het aantal bewerkingen om modulaire machtsverheffing uit te voeren, terwijl dezelfde geheugenvoetafdruk behouden blijft als bij de vorige methode. Het is een combinatie van de vorige methode en een meer algemeen principe genaamd machtsverheffing door kwadrateren (ook bekend als binaire machtsverheffing ).

Ten eerste is het vereist dat de exponent e wordt omgezet in binaire notatie . Dat wil zeggen, e kan worden geschreven als:

${\displaystyle e=\sum _{i=0}^{n-1}a_{i}2^{i}}$

In dergelijke notatie, de lengte van e is n bits. a _i kan de waarde 0 of 1 aannemen voor elke i zodanig dat 0 ≤ i < n . Per definitie is een _{n − 1} = 1 .

De waarde b ^e kan dan worden geschreven als:

${\displaystyle b^{e}=b^{\left(\sum _{i=0}^{n-1}a_{i}2^{i}\right)}=\prod _{i=0 }^{n-1}b^{a_{i}2^{i}}}$

De oplossing c is dus:

${\displaystyle c\equiv \prod _{i=0}^{n-1}b^{a_{i}2^{i}}{\pmod {m}}}$

Pseudocode

Het volgende is een voorbeeld in pseudocode op basis van Applied Cryptography door Bruce Schneier . De invoer basis , exponent en modulus komen overeen met b , e en m in de bovenstaande vergelijkingen.

function modular_pow(base, exponent, modulus) is
    if modulus = 1 then
        return 0
    Assert :: (modulus - 1) * (modulus - 1) does not overflow base
    result := 1
    base := base mod modulus
    while exponent > 0 do
        if (exponent mod 2 == 1) then
            result := (result * base) mod modulus
        exponent := exponent >> 1
        base := (base * base) mod modulus
    return result

Merk op dat wanneer de lus voor de eerste keer wordt betreden, de codevariabele basis gelijk is aan b . De herhaalde kwadratuur in de derde regel code zorgt er echter voor dat bij de voltooiing van elke lus de variabele basis gelijk is aan b ^{2 i} mod m , waarbij i het aantal keren is dat de lus is herhaald. (Dit maakt i het volgende werkende bit van de binaire exponent , waarbij het minst significante bit exponent _{0 is} ).

De eerste regel code voert eenvoudigweg de vermenigvuldiging uit in . Als een${\displaystyle \prod _{i=0}^{n-1}b^{a_{i}2^{i}}{\pmod {m}}}$nul is, wordt er geen code uitgevoerd omdat dit het lopende totaal met één vermenigvuldigt. Als eenin plaats daarvan één is, wordt de variabele basis (met de waarde b ^{2 i} mod m van de oorspronkelijke basis) eenvoudigweg vermenigvuldigd.

In dit voorbeeld wordt het grondtal b verheven tot de exponent e = 13 . De exponent is 1101 in binair getal. Er zijn vier binaire cijfers, dus de lus wordt vier keer uitgevoerd, met de waarden a ₀ = 1, a ₁ = 0, a ₂ = 1 en a ₃ = 1 .

Initialiseer eerst het resultaat op 1 en behoud de waarde van b in de variabele x : ${\displaystyle R}$

${\displaystyle R\leftarrow 1\,(=b^{0}){\text{ and }}x\leftarrow b}$.

Stap 1) bit 1 is 1, dus stel in ; ${\displaystyle R\leftarrow R\cdot x{\text{ }}(=b^{1})}$

instellen .${\displaystyle x\leftarrow x^{2}{\text{ }}(=b^{2})}$

Stap 2) bit 2 is 0, dus reset R niet ;

instellen .${\displaystyle x\linkerpijl x^{2}{\text{ }}(=b^{4})}$

Stap 3) bit 3 is 1, dus stel in ; ${\displaystyle R\linkerpijl R\cdot x{\text{ }}(=b^{5})}$

instellen .${\displaystyle x\leftarrow x^{2}{\text{ }}(=b^{8})}$

Stap 4) bit 4 is 1, dus stel in ; ${\displaystyle R\leftarrow R\cdot x{\text{ }}(=b^{13})}$

Dit is de laatste stap, dus we hoeven x niet vierkant te maken .

We zijn klaar: R is nu . ${\displaystyle b^{13}}$

Hier is de bovenstaande berekening, waarbij we b = 4 berekenen tot de macht e = 13 , uitgevoerd modulo 497.

Initialiseren:

${\displaystyle R\linkerpijl 1\,(=b^{0})}$ en .${\displaystyle x\pijl naar links b=4}$

Stap 1) bit 1 is 1, dus stel in ; ${\displaystyle R\leftarrow R\cdot 4\equiv 4{\pmod {497}}}$

instellen .${\displaystyle x\leftarrow x^{2}{\text{ }}(=b^{2})\equiv 4^{2}\equiv 16{\pmod {497}}}$

Stap 2) bit 2 is 0, dus reset R niet ;

instellen .${\displaystyle x\leftarrow x^{2}{\text{ }}(=b^{4})\equiv 16^{2}\equiv 256{\pmod {497}}}$

Stap 3) bit 3 is 1, dus stel in ; ${\displaystyle R\leftarrow R\cdot x{\text{ }}(=b^{5})\equiv 4\cdot 256\equiv 30{\pmod {497}}}$

instellen .${\displaystyle x\leftarrow x^{2}{\text{ }}(=b^{8})\equiv 256^{2}\equiv 429{\pmod {497}}}$

Stap 4) bit 4 is 1, dus stel in ;${\displaystyle R\leftarrow R\cdot x{\text{ }}(=b^{13})\equiv 30\cdot 429\equiv 445{\pmod {497}}}$

We zijn klaar: R is nu , hetzelfde resultaat verkregen in de vorige algoritmen. ${\displaystyle 4^{13}\equiv 445{\pmod {497}}}$

De looptijd van dit algoritme is O(log exponent ) . Wanneer u met grote waarden van exponent werkt , biedt dit een aanzienlijk snelheidsvoordeel ten opzichte van de vorige twee algoritmen, waarvan de tijd O( exponent ) is . Als de exponent bijvoorbeeld 2 ²⁰ = 1048576 was, zou dit algoritme 20 stappen hebben in plaats van 1048576 stappen.

Implementatie in Lua

function modPow(b, e, m)
  if m == 1 then
    return 0
  else
    local r = 1
    b = b % m
    while e > 0 do
      if e % 2 == 1 then
        r = (r*b) % m
      end
      b = (b*b) % m
      e = e >> 1     --use 'e = math.floor(e / 2)' on Lua 5.2 or older
    end
    return r
  end
end

Binaire methode van links naar rechts

We kunnen de bits van de exponent ook in de volgorde van links naar rechts gebruiken. In de praktijk zouden we gewoonlijk het resultaat modulo wat modulus m willen hebben . In dat geval zouden we elk vermenigvuldigingsresultaat (mod m ) verminderen voordat we verder gaan. Voor de eenvoud is de modulusberekening hier weggelaten. Dit voorbeeld laat zien hoe u kunt berekenen met behulp van binaire machtsverheffing van links naar rechts. De exponent is 1101 in binair; er zijn 4 bits, dus er zijn 4 iteraties. ${\displaystyle b^{13}}$

Initialiseer het resultaat naar 1: . ${\displaystyle r\leftarrow 1\,(=b^{0})}$

Stap 1) ; bit 1 = 1, dus bereken ;${\displaystyle r\leftarrow r^{2}\,(=b^{0})}$${\displaystyle r\leftarrow r\cdot b\,(=b^{1})}$

Stap 2) ; bit 2 = 1, dus bereken ;${\displaystyle r\leftarrow r^{2}\,(=b^{2})}$${\displaystyle r\leftarrow r\cdot b\,(=b^{3})}$

Stap 3) ; bit 3 = 0, dus we zijn klaar met deze stap;${\displaystyle r\leftarrow r^{2}\,(=b^{6})}$

Stap 4) ; bit 4 = 1, dus bereken .${\displaystyle r\leftarrow r^{2}\,(=b^{12})}$${\displaystyle r\linkerpijl r\cdot b\,(=b^{13})}$

Minimale vermenigvuldigingen

In de kunst van computerprogrammering , Vol. 2, Seminumerical Algorithms , pagina 463, merkt Donald Knuth op dat, in tegenstelling tot sommige beweringen, deze methode niet altijd het minimaal mogelijke aantal vermenigvuldigingen oplevert. Het kleinste tegenvoorbeeld is voor een macht van 15, wanneer de binaire methode zes vermenigvuldigingen nodig heeft. Vorm in plaats daarvan x ³ in twee vermenigvuldigingen, dan x ⁶ door x ^{3 te} kwadrateren , dan x ¹² door x ^{6 te} kwadrateren , en tenslotte x ¹⁵ door x ¹² en x ^{3 te} vermenigvuldigen , waardoor het gewenste resultaat wordt bereikt met slechts vijf vermenigvuldigingen. Er volgen echter vele pagina's waarin wordt beschreven hoe dergelijke reeksen in het algemeen kunnen worden opgesteld.

generalisaties

matrices

De m -de duur van elke constante-recursieve sequentie (bijvoorbeeld Fibonacci getallen of Perrin nummers ) waarbij elke term een lineaire functie van k voorgaande voorwaarden kunnen efficiënt worden berekend modulo n door het berekenen van A ^m mod n , waarbij A de overeenkomstige k × k begeleidende matrix . De bovenstaande methoden passen zich gemakkelijk aan deze toepassing aan. Dit kan bijvoorbeeld worden gebruikt voor priemtesten van grote getallen n .

Pseudocode

Een recursief algoritme voor ModExp(A, b, c)= A ^b mod c , waarbij A een vierkante matrix is.

function Matrix_ModExp(Matrix A, int b, int c) is
    if b == 0 then
        return I  // The identity matrix
    if (b mod 2 == 1) then
        return (A * Matrix_ModExp(A, b - 1, c)) mod c
    Matrix D := Matrix_ModExp(A, b / 2, c)
    return (D * D) mod c

Eindige cyclische groepen

Diffie-Hellman sleuteluitwisseling maakt gebruik van machtsverheffen in eindige cyclische groepen. De bovenstaande methoden voor modulaire matrixexpontiatie strekken zich duidelijk uit tot deze context. De modulaire matrixvermenigvuldiging C ≡ AB (mod n ) wordt gewoon overal vervangen door de groepsvermenigvuldiging c = ab .

Omkeerbare en kwantum modulaire machtsverheffing

In kwantumcomputing verschijnt modulaire machtsverheffing als het knelpunt van het algoritme van Shor , waar het moet worden berekend door een circuit dat bestaat uit omkeerbare poorten , die verder kunnen worden opgesplitst in kwantumpoorten die geschikt zijn voor een specifiek fysiek apparaat. Bovendien is het in het algoritme van Shor mogelijk om de basis en de modulus van machtsverheffing bij elke oproep te kennen, wat verschillende circuitoptimalisaties mogelijk maakt.

Software-implementaties

Omdat modulaire machtsverheffing een belangrijke operatie is in de informatica, en er efficiënte algoritmen zijn (zie hierboven) die veel sneller zijn dan alleen exponentiëren en vervolgens de rest nemen, hebben veel programmeertalen en bibliotheken met willekeurige precisie integere bibliotheken een speciale functie om modulaire machtsverheffing uit te voeren :

• De ingebouwde pow()(exponentiatie) functie [1] van Python neemt een optioneel derde argument, de modulus
• .NET Framework 's BigIntegerklasse heeft een ModPow()methode om modulaire machtsverheffing uit te voeren
• Java 's java.math.BigIntegerklasse heeft een modPow()methode om modulaire machtsverheffing uit te voeren
• MATLAB 's powermodfunctie van Symbolic Math Toolbox
• Wolfram Language heeft de PowerMod- functie
• De Math::BigIntmodule van Perl heeft een bmodpow()methode [2] om modulaire machtsverheffing uit te voeren
• Raku heeft een ingebouwde routine expmod.
• Go 's big.Intsoort bevat een Exp()(machtsverheffing) methode [3] waarvan de derde parameter, indien niet-nul, is de modulus
• De BC Math-bibliotheek van PHP heeft een bcpowmod()functie [4] om modulaire machtsverheffing uit te voeren
• De GNU Multiple Precision Arithmetic Library (GMP)-bibliotheek bevat een mpz_powm()functie [5] om modulaire machtsverheffing uit te voeren
• Aangepaste functie @PowerMod()voor FileMaker Pro (met voorbeeld van 1024-bits RSA- codering)
• Ruby 's opensslpakket heeft de OpenSSL::BN#mod_expmethode [6] om modulaire machtsverheffing uit te voeren.
• De HP Prime Calculator heeft de functie CAS.powmod() [7] om modulaire machtsverheffing uit te voeren. Voor a^b mod c mag a niet groter zijn dan 1 EE 12. Dit is de maximale precisie van de meeste HP rekenmachines, inclusief de Prime.

Zie ook

• Montgomery-reductie , voor het berekenen van de rest wanneer de modulus erg groot is.
• Kochanski-vermenigvuldiging , serialiseerbare methode voor het berekenen van de rest wanneer de modulus erg groot is
• Barrett-reductie , algoritme voor het berekenen van de rest wanneer de modulus erg groot is.

Referenties

Externe links

• Schneier, Bruce (1996). Toegepaste cryptografie: protocollen, algoritmen en broncode in C, tweede editie (2e ed.). Willy. ISBN 978-0-471-11709-4.
• Paul Garrett, Fast Modular Exponentiation Java Applet
• Gordon, Daniel M. (1998). "Een overzicht van Fast Exponentiation Methods" (PDF) . Dagboek van algoritmen . Elsevier BV. 27 (1): 129-146. doi : 10.1006/jagm.1997.0913 . ISSN  0196-6774 .