Eksponentieringsmodul

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 30. oktober 2016; checks kræver 16 redigeringer .

Eksponentiering modulo - en af operationerne på naturlige tal - eksponentiering - udført modulo . Det finder anvendelse i datalogi , især inden for kryptografi med offentlige nøgler .

Eksponentieringsmodulo er beregningen af resten af divisionen af et naturligt tal a (basis), hævet til potensen n ( eksponent ), med et naturligt tal m (modul). Udpeget:

$c\equiv a^{n}{\pmod {m))$

For eksempel, hvis vi får a = 5, n = 3 og m = 13, så er løsningen c = 8 resten af divisionen med 13. $5^{3}$

Hvis a , n og m er ikke-negative og a < m , så eksisterer der en unik løsning c med 0 ⩽ c < m .

Eksponentieringsmodulo kan også udføres med en negativ eksponent n. For at gøre dette skal du finde tallet d , det reciproke af tallet a modulo m . Dette er nemt at gøre med Euklids algoritme . På denne måde

c\equiv a^{n}\equiv d^{\left|n\right|}{\pmod {m))

, hvor n < 0 og

a\cdot d\equiv 1{\pmod {m))

Eksponentierende modulo er ret nemt, selv med store inputværdier. Men beregningen af den diskrete logaritme , det vil sige at finde eksponenten n for givet a , c og m , er meget vanskeligere. Denne envejsadfærd af funktionen gør den til en kandidat til brug i kryptografiske algoritmer.

Den simple metode

Den nemmeste måde at eksponentiere modulo på er at beregne tallet direkte og derefter finde resten, når det tal divideres med m . Beregn c , hvis a = 4, n = 13 og m = 497: ${\displaystyle a^{n))$

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

Du kan bruge en lommeregner til at beregne 4 13 , vi får 67.108.864. Nu tager vi dette tal modulo 497 og får 445.

a er kun et tegn langt, n er kun to tegn langt, og værdien af et n er 8 tegn langt.

I kryptografi har a ofte 256 bit (77 decimalcifre). Overvej a = 5 × 10 76 og n = 17, som begge har ret reelle værdier. I dette eksempel er a 77 tegn langt, og n er 2 tegn langt, men resultatet af eksponentieringen er 1304 tegn langt. Sådanne beregninger er mulige på moderne computere, men hastigheden til at beregne sådanne tal er langsom. Værdierne af a og n øges for at opnå et højere sikkerhedsniveau, hvilket gør værdien af et n uhåndterlig.

Den tid, det tager at eksponentiere, afhænger af operativsystemet og processoren. Den ovenfor beskrevne måde kræver O ( n) multiplikationer.

Hukommelseseffektiv metode

Denne metode kræver flere operationer end den forrige. Men da der kræves mindre hukommelse, og operationer tager mindre tid, er algoritmen meget hurtigere.

Denne algoritme er baseret på det faktum, at givet a og b , er følgende 2 ligninger ækvivalente:

c\equiv (a\cdot b){\pmod {m}}

c\equiv (a\cdot (b\ ({\mbox{mod}}\ m))){\pmod {m}}

Algoritmen er følgende:

Lad c = 1, n′ = 0.
Lad os øge n′ med 1.
Installer . $c\equiv (b\cdot c){\pmod {m}}$
Hvis n′ < n, gå tilbage til trin 2. Ellers indeholder c det rigtige svar . $c\equiv b^{n}{\pmod {m))$

Hver gang i trin 3 er udtrykket sandt. Efter at trin 3 er blevet udført n gange, indeholder c den ønskede værdi. Algoritmen er således afhængig af at tælle n', indtil n' når n , når c (fra forrige iteration af sløjfen) ganges med b modulo m i den aktuelle iteration af sløjfen (for at sikre, at resultatet er lille). $c\equiv b^{n'}{\pmod {m))$

For eksempel er b = 4, n = 13 og m = 497. Algoritmen gennemgår trin 3 tretten gange.

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

Det endelige svar c er 445, ligesom i den første metode.

Ligesom den første metode kræver det O( n) multiplikationer at fuldføre. Men da tallene brugt i disse beregninger er meget mindre, reduceres udførelsestiden for denne algoritme.

I pseudokode ser det sådan ud:

funktion modulær_pow(base, indeks_n, modul) c := 1 for index_n_prime = 1 til index_n c := (c * base) mod modul retur c

Algoritme for hurtig eksponentieringsmodulo

Anvendelse af den hurtige eksponentieringsalgoritme for 595 703 (mod 991 ):

Vi har n = 703 =(1010111111) 2 = 2 0 +2 1 +2 2 +2 3 +2 4 +2 5 + 2 7 +2 9 .

595 703 = ((((((((595 2 ) 2 *595) 2 ) 2 * 595) 2 *595) 2 * 595) 2 *595) 2 *595) 2 *595

= (((((((238 2 *595) 2 ) 2 * 595) 2 *595) 2 * 595) 2 *595) 2 *595) 2 *595

= ((((((261 2 ) 2 * 595) 2 * 595) 2 * 595) 2 * 595) 2 * 595) 2 * 595

= (((((733 2 * 595) 2 *595) 2 * 595) 2 *595) 2 *595) 2 *595

= (((((167*595) 2 *595) 2 *595) 2 *595) 2 *595) 2 *595

= ((((265 2 *595) 2 * 595) 2 *595) 2 *595) 2 *595

= (((342 2 * 595) 2 *595) 2 *595) 2 *595

= ((605 2 *595) 2 *595) 2 *595

= (733 2 *595) 2 *595

= (167*595) 2 *595

= 265 2 * 595

= 342 .

Højre-til-venstre-skema

En anden mulighed er et højre-til-venstre-layout. Det kan repræsenteres af følgende formel:

$d=a^{n}=$

$=a^{{\sum _{{i=0}}^{k}m_{i}*2^{i}}}=$

$=a^{{m_{0}}}*a^{{2m_{1}}}*a^{{2^{2}*m_{2}}}*...*a^{{2^ {k}*m_{k}}}=$

$=a^{{m_{0}}}*(a^{2})^{{m_{1}}}*(a^{{2^{2}}})^{{m_{2}} }*...*(a^{{2^{k}}})^{{m_{k}}}=$

$=\prod _{{i=0}}^{k}{(a^{{2^{{i}}}})^{{m_{i}}}}$

Eksempel . Ved at bruge et simpelt binært højre-til-venstre-eksponentieringsskema, lad os beregne værdien 175 235 mod 257 .

Lad os repræsentere tallet 235 i binær form:

235 10 = 11101011 2 .

1 . d := 1 * 175 mod 257 = 175,

t:= 175 2 mod 257 = 42;

2 . d := 175 * 42 mod 257 = 154,

t:= 422 mod 257 = 222;

3 . t:= 222 2 mod 257 = 197;

4 . d := 154 * 197 mod 257 = 12,

t:= 197 2 mod 257 = 2;

5 . t:= 22 mod 257 = 4;

6 . d := 12 * 4 mod 257 = 48,

t:= 42 mod 257 = 16;

7 . d := 48 * 16 mod 257 = 254,

t:= 162 mod 257 = 256;

8 . d := 254 * 256 mod 257 = 3,

9 . → d = 3. Det tog 7 kvadrater og 6 gange.

Matricer

Fibonacci-tal modulo n kan effektivt findes ved at beregne Am (mod n) for en given m og en given matrix A . De anførte metoder kan nemt anvendes i denne algoritme. Dette giver en god primalitetstest for store tal n (500 bit).

Pseudokode

Tilbagevendende algoritme for ModExp(A, b, c) = A b (mod c), hvor A er en kvadratisk matrix.

matrix ModExp(matrix A, int b, int c) { if (b == 0) returnerer I; // Identitetsmatrix if (b % 2 == 1) return (A * ModExp(A, b-1, c)) % c; matrix D = ModExp(A, b/2, c); returnere (D * D) % c; }

Finitet af cykliske grupper

Diffie-Hellman nøgleudveksling bruger eksponentiering i endelige cykliske grupper. Ovenstående metode til at hæve en matrix til en potens strækker sig fuldstændigt til cykliske grupper. Matrix multiplikation modulo C = AB (mod n) erstattes blot af gruppemultiplikation c = ab .

Omvendt og kvanteeksponentieringsmodulo

I kvanteberegning er eksponentieringsmodulo en del af Shors algoritme . I denne algoritme kan du også finde ud af basen og eksponenten med hvert kald, hvilket tillader forskellige ændringer af kredsløbet [3] .

I programmeringssprog

Eksponentieringsmodulo er en vigtig operation inden for datalogi, og der er effektive algoritmer (se ovenfor), der er meget hurtigere end blot at eksponentere og derefter tage resten. Der er biblioteker i programmeringssprog, der indeholder en speciel funktion til eksponentieringsmodulo:

Python har en indbygget pow() funktion [4]
.NET Framework indeholder en BigInteger -klasse, der inkluderer ModPow() [5]
Java indeholder klassen java.math.BigInteger , som inkluderer modPow() [6]
Perl indeholder Math::BigInt- modulet, som inkluderer bmodpow()- metoden [7]
Go indeholder typen big.Int , som inkluderer Exp() metoden [8]
PHP indeholder BC Math-biblioteket, som inkluderer bcpowmod()- funktionen [9]
GNU Multi-Precision Library (GMP) bibliotek indeholder funktionen mpz_powm() [10]

Se også

Montgomerys algoritme til at beregne resten, når modulet er meget stort.
Hurtig eksponentieringsalgoritme til at fremskynde beregninger.
Algoritmer til hurtig eksponentieringsmodulo

Noter

↑ Teoretiske minimums- og digitale signaturalgoritmer, 2010 , s. 56-57.
↑ Schneier 1996 , s. 244.
↑ Igor L. Markov, Mehdi Saeedi, "Constant-Optimized Quantum Circuits for Modular Multiplication and Exponentiation", Quantum Information and Computation, Vol. 12, nr. 5&6, s. 0361-0394, 2012. http://arxiv.org/abs/1202.6614
↑ Indbyggede funktioner: officiel side . Dato for adgang: 28. december 2014. Arkiveret fra originalen 1. januar 2015.
↑ BigInteger.ModPow Metode : officielt websted . Dato for adgang: 24. december 2014. Arkiveret fra originalen 28. december 2014.
↑ Klasse BigInteger: officiel side . Dato for adgang: 28. december 2014. Arkiveret fra originalen 31. december 2014.
↑ Math::BigInt: officiel side . Hentet 24. december 2014. Arkiveret fra originalen 5. juni 2020.
↑ Stor pakke : officiel side . Dato for adgang: 28. december 2014. Arkiveret fra originalen 2. januar 2015.
↑ bcpowmod: officiel side . Dato for adgang: 28. december 2014. Arkiveret fra originalen 28. december 2014.
↑ Eksponentielle funktioner: officielt websted . Dato for adgang: 28. december 2014. Arkiveret fra originalen 28. december 2014.

Litteratur

Moldovy NA Teoretiske minimums- og digitale signaturalgoritmer. - Sankt Petersborg. : BVH-Petersburg: Boghuset "LIBROKOM", 2010. - 304 s. - ISBN 978-5-9775-0585-7 .
Schneier, Bruce. Anvendt kryptografi: protokoller, algoritmer og kildekode i C, anden udgave. — 2. - Wiley, 1996. - ISBN 978-0-471-11709-4 .
Valitskas AI Resumé af forelæsninger om disciplin: Elementer af abstrakt og computeralgebra. // Tobolsk , TSPI im. D. I. Mendeleev , 2004 .
Gabidulin E. M., Kshevetsky A. S., Kolybelnikov A. I., Vladimirov S. M. Informationssikkerhed (Tutorial): Exponentiation modulo (s. 253) // MIPT , 2014.