Potęgowanie modułowe

Należy sprawdzić treść tego artykułu matematycznego (Styczeń 2014).

Popraw to lub przedyskutuj rzeczy do sprawdzenia . Jeśli właśnie umieściłeś baner, wskaż punkty do sprawdzenia tutaj .

W matematyce , a dokładniej w modułowej arytmetyki The modułowy potęgowanie jest typu potęgowanie ( potęgowania ) wykonywane modulo liczba całkowita . Jest szczególnie wykorzystywany w informatyce , zwłaszcza w dziedzinie kryptologii .

Generalnie, modularne problemy potęgowania są wyrażane w postaci: mając podstawę b , wykładnik e i liczbę całkowitą m, chcemy obliczyć c tak, że:

c \ równoważnik b ^ {e} {\ pmod {m}}

Jeśli b , e i m są dodatnie lub zero i b < m , Istnieje unikalne rozwiązanie c takie, że . Na przykład, jeśli b = 5, e = 3 i m = 13, obliczenie c daje 8. $0 \ leq c <m$

Problemy potęgowania modułowego podobne do poprzedniego przykładu są uważane za łatwe do rozwiązania, mimo że ich liczby są ogromne. Wręcz przeciwnie, obliczenie dyskretnego logarytmu (znalezienie e z b , c i m ) jest trudne. To jednokierunkowe zachowanie funkcji sprawia, że potęgowanie modularne jest dobrym kandydatem do użycia w algorytmach kryptologicznych.

Prezentacja ogólna

Naiwne obliczenie wykładnika modularnego jest następujące: mnożymy e razy liczbę b przez samą liczbę b , a po uzyskaniu liczby całkowitej b e obliczamy jej resztę modulo m za pomocą algorytmu dzielenia Euklidesa . Ta metoda ma dwie wady:

z jednej strony liczbę mnożeń można łatwo zmniejszyć, stosując ogólną metodę szybkiego potęgowania : do wykonania będą tylko mnożenia log (e) .
z drugiej strony nie korzystamy z przemiennej struktury pierścienia dziedziny, w której pracujemy: liczb całkowitych modulo m . Jednak ta struktura pozwala na dokonywanie obliczeń bezpośrednio w tym pierścieniu, bez wcześniejszego przechodzenia przez liczby całkowite. Aby zrealizować ten pomysł, w praktyce konieczne jest, przy każdym nowym mnożeniu, obliczenie nowej reszty modulo m . Dodajemy więc nowe operacje (dla każdego mnożenia, dzielenie euklidesowe), ale czerpiemy również z faktu, że rozmiar danych do obsługi jest ograniczony przez m .

W dalszej części artykułu opisano te różne adaptacje i omówiono ich skuteczność w zależności w szczególności od wielkości danych.

Metoda bezpośrednia

Najbardziej bezpośrednią metodą obliczenia wykładnika modularnego jest obliczenie b e bezpośrednio, a następnie przyjęcie tej liczby modulo m . Spróbujmy obliczyć c , przy b = 4, e = 13 i m = 497:

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

Użyjmy kalkulatora, aby obliczyć 4 13 , otrzymamy wartość 67 108 864. Weźmy ten modulo 497, otrzymany wynik c to 445. Chociaż b ma tylko jedną cyfrę, a e dwa, wartość b e osiąga jedną długość 8 cyfr.

W silnej kryptologii b często ma co najmniej 256 cyfr binarnych (77 cyfr dziesiętnych). Weźmy b = 5 × 10 76 i e = 17, dwie doskonale rozsądne wartości. W tym przykładzie b ma 77 cyfr dziesiętnych, a e dwa, ale b e ma 1304 cyfry. Tego rodzaju obliczenia są możliwe na nowoczesnych komputerach, ale ogrom tego rodzaju liczby znacznie spowalnia szybkość obliczeń. Wraz ze wzrostem rozmiaru b i e w celu poprawy bezpieczeństwa szyfrowania, wartość b e staje się niemożliwa do zarządzania.

Czas wymagany do wykonania potęgowania zależy od środowiska operacyjnego i procesora. Obliczenie potęgi przez szereg mnożeń wymaga czasu O ( e ).

Metoda wykorzystująca mniej pamięci

Druga metoda obliczania potęgowania modularnego wymaga większej liczby operacji niż pierwsza metoda. Jednak ze względu na mniejsze zapotrzebowanie na pamięć operacje zajmują mniej czasu niż wcześniej. W rezultacie ten algorytm może być szybszy:

albo przez mniejszą wymianę między pamięcią podręczną (cache) a pamięcią,
lub używając mniej wymiany w przypadku pamięci wirtualnej .

Algorytm ten wykorzystuje fakt, że dla dwóch danych liczb całkowitych b i c z pierwszych relacji wynika, co następuje:

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

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

Poniższy algorytm:

Ustaw c = 1, e ' = 0.
Zwiększ e ' o 1.
Oblicz . $c \ equiv (b \ cdot c) \ {\ pmod {m}}$
Jeśli e ' < e , przejdź do kroku 2. W przeciwnym razie c zawiera poprawne rozwiązanie . $c \ równoważnik b ^ {e} {\ pmod {m}}$

Zauważ, że za każdym razem, gdy przechodzisz przez krok 3, równanie staje się prawdziwe. Kiedy krok 3 zostało przeprowadzone th czas, a następnie, c zawiera odpowiedź, która została poszukiwanych. $c \ equiv b ^ {{e '}} \ {\ pmod {m}}$

Wróćmy do przykładu b = 4, e = 13 i m = 497. Algorytm przechodzi przez krok 3 trzynaście razy:

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' = 6c = (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' = 9c = (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 .

Ostateczna odpowiedź dla c to 445, tak jak w pierwszej metodzie.

Podobnie jak pierwsza metoda, wymaga to czasu obliczeń w O ( e ). Ponieważ jednak liczby użyte w tych obliczeniach są mniejsze niż liczby użyte w obliczeniach pierwszego algorytmu, współczynnik stały tej metody jest zwykle mniejszy.

Najbardziej wydajna metoda

Trzecia metoda drastycznie zmniejsza zarówno liczbę operacji, jak i miejsce w pamięci niezbędne do wykonania potęgowania modularnego. Jest to połączenie poprzedniej metody i bardziej ogólnej zasady zwanej szybką potęgą (znaną również jako potęgowanie kwadratowe).

Przede wszystkim musimy zamienić wykładnik e na notację binarną , czyli piszemy:

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

W tym zapisie długość od E jest N bitów. a i może przyjąć wartość 0 lub 1 dla dowolnego i takiego, że 0 ≤ i < n - 1. Z definicji a n - 1 = 1.

Wartość b e można wtedy zapisać:

{\ displaystyle b ^ {e} = b ^ {\ po lewej (\ suma _ {i = 0} ^ {n-1} a_ {i} 2 ^ {i} \ po prawej)} = \ prod _ {i = 0 } ^ {n-1} \ po lewej (b ^ {2 ^ {i}} \ po prawej) ^ {a_ {i}}.}

Rozwiązaniem v jest zatem:

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

Taki algorytm można łatwo zaimplementować w języku programowania, który posiada przeciążenia operatorów i garbage collectory . Poniższy przykład jest w języku C# . Klasa Bignum reprezentuje dowolną dużą liczbę dodatnią. Zmienne wejściowe są podstawą dla podstawy ( b ), exp dla wykładnika ( e ) i m dla modułu.

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; }

Kod ten, oparty na jednej stronie 244 na Applied Cryptography przez Bruce Schneier , 2 th ed. ( ISBN 0471117099 ) wykorzystuje pętlę while do wykonania całej pracy wymaganej do obliczenia potęgowania modularnego.

Zauważ, że przy pierwszym wejściu do pętli zmienna podstawowa zawiera b . Następnie powtórzenie kwadratury w trzecim wierszu kodu zapewnia, że na końcu każdej pętli zmienna base jest równa , gdzie i jest liczbą iteracji pętli. (Co sprawia, że i jest następnym bitem do przetworzenia w wykładniku binarnym exp , najmniej znaczącym bitem, którym jest exp 0 ). $b ^ {{2 ^ {i}}} \ {\ pmod {m}}$

Pierwszy wiersz kodu po prostu wykonuje mnożenie w . Jeśli i wynosi zero, kod nie jest wykonywany, co jest równoznaczne z pomnożenia sumie o jeden. Jeśli z drugiej strony a i jest równe jeden, wynik jest po prostu mnożony przez zmienną bazową (zawierającą wartość pierwotnej bazy). $\ prod _ {{i = 0}} ^ {{n-1}} \ po lewej (b ^ {{2 ^ {i}}} \ po prawej) ^ {{a_ {i}}} \ {\ pmod {m }}$ $b ^ {{2 ^ {i}}} \ {\ pmod {m}}$

Na koniec przetestujmy na przykładzie b = 4, e = 13 i m = 497. Zauważ, że e jest równe 1101 w systemie binarnym. Ponieważ e ma długość czterech cyfr binarnych, pętla uruchomi się tylko cztery razy:

Przy pierwszym wejściu do pętli wartości zmiennych to: baza = 4, exp = 1101 (binarny) i wynik = 1. Ponieważ skrajny prawy bit exp to 1, wynik jest zastępowany przez (1 × 4) mod 497, tj . 4 . exp jest następnie obcinany po prawej stronie i staje się 110 (binarny), a podstawa do kwadratu to (4 × 4) mod 497, czyli 16.
Przy drugim wykonaniu pętli, skrajny prawy bit exp to 0, więc wynik nie ulega zmianie. exp jest następnie obcięty w prawo i staje się 11 (binarny), a podstawa jest do kwadratu (16 × 16) mod 497, czyli 256.
Przy trzecim wykonaniu pętli, skrajny prawy bit exp to 1. wynik zostaje zastąpiony przez (4 × 256) mod 497, czyli 30 . exp jest następnie obcięty w prawo i staje się 1, a podstawa jest do kwadratu (256 × 256) mod 497, tj. 429.
Przy czwartym wykonaniu pętli, skrajny prawy bit exp to 1. wynik zostaje zastąpiony przez (30 × 429) mod 497, czyli 445 . exp jest następnie obcinane po prawej stronie i staje się 0, a podstawa jest podnoszona do kwadratu tak, aby była równa (429 × 429) mod 497, czyli 151. (Zauważ, że to ostatnie mnożenie podstaw * jest systematycznie bezużyteczne, ponieważ pożądany wynik, tutaj 445 , jest już znany.)

Pętla się kończy, ponieważ exp wynosi zero i zwracany jest wynik 445 . Jest to zgodne z dwoma poprzednimi algorytmami.

Czas wykonania tego algorytmu wynosi O (log e ). Podczas pracy z dużymi wartościami e jest znacznie szybszy niż dwa poprzednie algorytmy.

Uwagi i referencje

(fr) Ten artykuł jest częściowo lub w całości zaczerpnięty z artykułu w angielskiej Wikipedii zatytułowanego „ Wykładnictwo modułowe ” ( patrz lista autorów ) . <img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">