50108 Str068
132 4. Klucze pu Mierne
Algorytm wyzniczanJl logarytmu dyskretnego oparty na obliczaniu In. drksu. Czytelnik może opuścić ten fragment teraz, lub też przejrzeć go tylko pobieżnie, i powrócić, by zapoznać się z nim dokładniej wtedy, kiedy dojdzie do podrozdziału 5.3, gdyż algorytm wyznaczania logarytmu dyskretnego w ciałach skończonych oparty na obliczaniu indeksu ma wiele wspólnego z mc* lodą rozkładu na czynniki, w której korzysta się z baz rozkładu.
Założymy tu, że q - p* jest dość wysoką potęgą małej liczby pierwszej p oraz że b jest generatorem grupy FJ. Algorytm oparty na obliczaniu indeksu znajduje dla każdego yeF* liczbę x (z przedziału od 0 do q — 1) taką, że ye*b*.
Niech f(X)e¥p[Ar] będzie dowolnym wielomianem nierozkładalnym stopnia n; wtedy ciało F, jest izomorficzne z pierścieniem reszt Fp[Af]//(Af). Każdy element aeFq = Fp[X]!f(X) może być zapisany (jednoznacznie) jako wielomian fl(Af)eFp[Ar] stopnia co najwyżej n — 1. W szczególności nasza podstawa b - b(X) jest takim wielomianem. „Stałymi" będą elementy ciała
F»cF’- , „„ „
Najpierw zauważmy, że b' = ó(,“1)/(p"1) jest generatorem grupy FJ
(por. ćwiczenie 17 w podrozdziale 2.1). Będziemy zatem umieli natychmiast obliczyć logarytmy dyskretne stałych, o podstawie ó, jeśli rozwiążemy problem logarytmu dyskretnego w grupie FJ (o podstawie b'). Ale założyliśmy, że liczba p jest mała, a więc tablica takich dyskretnych logarytmów może być łatwo utworzona. W szczególnie ważnym przypadku p = 2, jedyną niezerową stałą jest 1, której logarytmem dyskretnym o dowolnej podstawie jest 0. W dalszym ciągu będziemy zakładać, że umiemy łatwo znaleźć logarytm dyskretny stałej,
Do końca tego podrozdziału logarytm dyskretny a(X)e FJ o podstawie b(X) będziemy oznaczać przez ind (a(X)) (od słowa „indeks”). Podstawa b(X) będzie ustalona do końca rozumowania, więc nie będzie uwidoczniona w oznaczeniach.
Algorytm oparty na obliczaniu indeksu składa się z dwóch zasadniczych faz. Faza pierwsza to „obliczenie wstępne”, wykonywane niezależnie od elementu y(X) 6 FJ, którego logarytm dyskretny chcemy obliczyć. To obliczenie będzie wykonane tylko raz, a następnie jego wyniki będą wykorzystywane do obliczenia logarytmów dyskretnych różnych elementów o tej samej podstawie b{X). (Przypomnijmy tu, że podobne obliczenie wstępne było wykonywane w algorytmie SiWera-Pohliga-Hellmana i polegało na wyznaczeniu tablicy {r ,}.)
Najpierw wybieramy zbiór B c Ffl, który będzie naszą „bazą”. Zazwyczaj baza B składa się ze wszystkich unormowanych wielomianów nierozkła-dalnych nad ciałem Fp, stopnia nie większego niż m, gdzie liczba m<n jest dobrana w pewien optymalny sposób, tak by zbiór B miał odpowiednią wielkość h = |2?lt}, pośrednią między p = lFpj i q = pn - JFJ. Faza wstępna polega na obliczeniu logarytmów dyskretnych wszystkich a(X)eB i jest wykonywana w następujący sposób.
ł) Symbolem \A\ oznaczamy liczbę elementów zbioru A (przyp. Uum.).
Wybieramy losową liczbę / miedzy I i q ~ 2, a następnie obliczamy ygF,, tai. wyznaczamy wielomian c(/)6P;[I]f stopnia mniejszego niź n,
taki że
c(JT) = b(Xf fmod {(X)).
(Stosujemy tu algorytm iterowanego podnor/enia do kwadratu, za każdym razem redukując wynik modulo f(Xj). Wyłączamy przed nawias współczynnik c0 przy najwyższej potędze X w wielomianie c(X) i sprawdzamy, czy wielomian unormowany znajdujący się w nawiasie jest iloczynem wielomianów a(X)eB, lzn. czy wielomian c(X) może być zapisany w postaci
BS211
Jeden sposób sprawdzenia tego polega na przeglądaniu wszystkich wielomianów i dzieleniu c(X) przez a(X)*ru (gdzie aft jest wykładnikiem naj
wyższej potęgi a(X) dzielącej wielomian c(X) w pierścieniu Fp[X]). Jeśli po wszystkich takich dzieleniach przez potęgi wielomianów a(X)sB pozostanie tylko stała c0, to wielomian c(X) ma wymaganą postać, w przeciwnym razie powracamy do początku tego akapitu i wybieramy inną liczbę losową i. (Inny sposób - w niektórych przypadkach szybszy - sprawdzania, czy wielomian c(X) rozkłada się na iloczyn wielomianów a(X)sB, polega po prostu na rozłożeniu c(X) na czynniki za pomocą algorytmu faktoryzacji elementów pierścienia Fp[Z]. Opis dobrego algorytmu służącego do tego celu - opracowanego przez Berlekampa - znajduje się w drugim tomie książki Knutha, 4.6.2.)
Przypuśćmy teraz, że znaleźliśmy wielomian c(X) = b(X)1 (mod f(X)), mający żądany rozkład na czynniki. Porównując logarytmy dyskretne obu stron równości w poprzednim akapicie, otrzymujemy
ind(c(JQ) - jnd(c„) = ind(a(A')),
OtB
gdzie równość jest rozumiana jako kongruencja modulo q - 1 (gdyż logarytm dyskretny jest zdefiniowany jedynie modulo q - 1). Lewa strona równości jest znana, gdyż ind(c(20) = t i logarytmy dyskretne stałych mogą być łatwo obliczone. Współczynniki ac a po prawej stronie też są znane. Nie znamy tylko h wartości ind(fl(J0), dla a(X)eB, po prawej stronie.
Otrzymaliśmy więc równanie liniowe z h niewiadomymi w pierścieniu ZKq - 1)Z. Teraz przypuśćmy, że powtarzamy wybieranie losowych liczb i tak długo, aż otrzymamy dużą liczbę różnych wielomianów c(X), rozkładających się na iloczyn wielomianów a(X)sB. Z chwilą gdy otrzymamy h niezależnych kongruencji postaci
t - ind(c0) p £afifl ind(a(X)) (mod q - 1)
acB
Wyszukiwarka
Podobne podstrony:
skanuj0014 132 Marcel Mauss tak samo, jak można to stracić na wojnie1 2 czy wskutek błędu obrzędoweg
Uwaga 1.1. Z algorytmu Euklidesa wynika metoda wyznaczania x,y e Z. Istotnie, dla a, b 6 IN, a ^ b m
skanuj0023 (50) 132 6. Zagospodarowanie turystyczne trwałego budownictwa, położony poza obszarami za
IMGV76 (3) 132 WACŁAW BERENT — Brawo, Beethoven! — Beethoven! — krzyczano po
dzielenie pisemne 3 F 6 Algorytm dzielenia pisemnego przez liczby jednocyfrowe Oblicz. 0 Przeczytaj
Tematy prac dyplomowych (inż. i mgr) 1 Badania modelowe algorytmów sterowania ruchem modeli statków
wykłady z polskiej składni4 132 Zdania wyratające relację przyczynowo-skutkową wał, nie przyszedł n
P6080118 132 Andrza) Chodubakl nia kraju najczęściej dzieli się emigrację na: 1) ekonomiczną (zarobk
więcej podobnych podstron