Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Algorytm obliczania logarytmu dyskretnego szybszy niż redukcja Pohliga-Hellmana
449 views
Skip to first unread message
osobliwy nick
Oct 24, 2015, 12:52:57 PM10/24/15
to
Mniej więcej 2 lata temu toczyłem tu kilka dyskusji o algorytmach znajdowania liczb pierwszych oraz obliczania logarytmu dyskretnego. Dotyczyły one algorytmu, który wówczas sformułowałem oraz aktualnego stanu wiedzy w zakresie niniejszej tematyki. Na zakończenie doprecyzowałem wtedy ten algorytm i porzuciłem temat.
Dziś wróciłem do tamtych notatek i chcę Wam przedstawić jeszcze raz pewien algorytm umożliwiający obliczanie logarytmu dyskretnego przy podstawie 2, tj. znalezienie dla pewnej (nieparzystej) liczby g takiego najmniejszego n, że g dzieli 2^n-1 bez reszty. Jeżeli II_(i) (p_i^(e_i)) jest faktoryzacją liczby g algorytm ma złożoność:
O[sum_(i) (p_i*log(p_i) + exp((ln(p_i-1)*ln ln(p_i-1))^0,5))]
przy zastosowaniu metody sita kwadratowego do faktoryzacji liczb p_i-1 (złożoność obliczeniowa faktoryzacji liczby n metodą sita kwadratowego wynosi exp((ln(n)*ln ln(n))^0,5). Jeżeli zastosujemy inną metodę np. GNFS, obliczanie (faktoryzacja) składnika p_i-1 będzie wymagało innej złożoności (ponadto niekiedy będzie możliwa faktoryzacja liczb mniejszych niż p_i-1, gdyż czas stopu d - zdefiniowany w dalszej części niekiedy będzie mniejszy aniżeli p_i-1). Algorytm najlepiej działa dla liczb gładkich i wydaje się być wydajniejszy niż redukcja Pohliga-Hellmana (jeżeli dobrze oszacowałem jego złożoność obliczeniową).
Algorytm:
Zdefiniujmy ciąg określony rekurencyjnie dla liczby x=1 oraz wybranej nieparzystej liczby g (dla której obliczymy logarytm dyskretny):
- 0,5*x + g/2 -->> jeżeli x jest nieparzyste
- 0,5*x -->> jeżeli x jest parzyste
Otrzymujemy w ten sposób ciąg liczb, którego iterowanie rozpoczynamy zawsze od liczby 1. Ponadto ciąg zawsze się zapętla i po pewnej liczbie iteracji znów osiąga 1 (podaję to twierdzenie jak i cały algorytm bez dowodu). Oznaczmy liczbę tych iteracji jako d (d to inaczej czas stopu funkcji, zaprzestajemy obliczeń, gdy ciąg osiągnie znów liczbę 1). Czas stopu nigdy nie jest większy niż g-1 oraz prawdopodobnie da się udowodnić, iż jest on zawsze mniejszy lub równy wartości tocjent obliczonej z g (tocjent z liczby g jest zawsze jakąś wielokrotnością czasu stopu d). Przykład:
Niech g = 5. Mamy zatem funkcję:
- 0,5*x + 5/2 -->> jeżeli x jest nieparzyste
- 0,5*x -->> jeżeli x jest parzyste
Zaczynamy obliczenia od x=1.
1
0,5*1 + 2,5 = 3
0,5*3 + 2,5 = 4
4/2 = 2
2/2 = 1
Kończymy obliczenia uzyskawszy ciąg 1, 3, 4, 2, 1. Zajęło nam to d=4 iteracje. W każdym przypadku funkcja zwróci taką najmniejszą możliwą wartość d, że g będzie dzieliło 2^d-1 bez reszty (w tym przypadku 5 dzieli 2^4-1). Ilość iteracji będzie się różnić dla różnych liczb i to właśnie wyznaczanie tej ilośći iteracji dla liczb g, gładkich jest zasadniczym przedmiotem niniejszej pracy.
W ogólnym przypadku liczba gładka p_1^(e_1)*p_2^(e_2)*...*p_n^(e_n) ma czas stopu:
p_1^(e_1-1)*p_2^(e_2-1)*...*p_n^(e_n-1)*x
przy czym x to czas stopu liczby p_1*p_2*...*p_n pozbawiony czynników w potęgach występujących w p_1^(e_1-1)*p_2^(e_2-1)*...*p_n^(e_n-1) (o ile takie wystąpią). Ponadto dowolna złożona liczba p_1*p_2*...*p_n ma czas stopu będący iloczynem najwyższych potęg różnych czynników które występują w czasach stopów liczb p_1, p_2, ..., p_n.
Uwaga: jedynym wyjątkiem od powyższej reguły wydają się być liczby pierwsze Wieferich.
Weźmy liczbę g=13*17. Obliczamy dwa ciągi:
- 0,5*x + 13/2 -->> jeżeli x jest nieparzyste
- 0,5*x -->> jeżeli x jest parzyste
oraz
- 0,5*x + 17/2 -->> jeżeli x jest nieparzyste
- 0,5*x -->> jeżeli x jest parzyste
Liczba 13 ma d=12=4*3 (po takim czasie osiąga liczbę 1, uwaga: w przypadku większych liczb rozbicie czasu stopu na czynniki pierwsze będzie wymagało zastosowania algorytmu sita kwadratowego lub GNFS), a liczba 17 ma d=8. Najwyższa potęga dwójki w tych czasach to 8, a trójki to 3. Liczba 13*17 ma zatem czas stopu wynoszący 3*8=24. Uwaga: ten sam wynik uzyskamy obliczając funkcję:
- 0,5*x + (13*17)/2 -->> jeżeli x jest nieparzyste
- 0,5*x -->> jeżeli x jest parzyste
ale nie na tym nam zależy, gdyż chcemy redukować problem.
To tyle jeżeli chodzi o sam opis algorytmu. Wszystkie twierdzenia sformułowane na potrzeby niniejszego algorytmu podaję bez dowodów, nie posiadam także na tę chwilę formalnych dowodów wspierających wiarygodność niniejszego algorytmu. Z uwagi na fakt, iż powyższe definicje mogą okazać się niejasne poniżej podaję przykłady działania algorytmu.
Weźmy liczbę 3*5*7*11*13*17*19. By znaleźć takie najmniejsze n, że 3*5*7*11*13*17*19 dzieli 2^n-1 bez reszty możemy obliczyć funkcję:
- 0,5*x + (3*5*7*11*13*17*19)/2 -->> jeżeli x jest nieparzyste
- 0,5*x -->> jeżeli x jest parzyste
ale to zbyt złożone obliczeniowo. Obliczamy zatem (zawsze rozpoczynamy interacje od x=1):
- 0,5*x + 3/2 -->> jeżeli x jest nieparzyste
- 0,5*x -->> jeżeli x jest parzyste
Otrzymujemy:
1
0,5*1+1,5=2
0,5*2=1
d wynosi zatem 2. Następnie obliczamy ciąg:
- 0,5*x + 5/2 -->> jeżeli x jest nieparzyste
- 0,5*x -->> jeżeli x jest parzyste
który został policzony w poprzednim przykładzie. Obliczamy także czasy stopów dla kolejnych liczb stanowiących czynniki 3*5*7*11*13*17*19. Otrzymujemy, że:
- 3 ma d=2
- 5 ma d=4
- 7 ma d=3
- 11 ma d=10
- 13 ma d=12
- 17 ma d=8
- 19 ma d=18
najwyższe potęgi różnych czynników, które występują w czasach stopu d powyższych liczb to 8,9,5. Mamy więc 8*9*5=360. Czas stopu liczby 3*5*7*11*13*17*19 wynosi zatem 8*9*5=360. Wykonaliśmy tylko 57 operacji oraz musieliśmy rozłożyć na czynniki pierwsze 7 liczb.
Weźmy liczbę 3*5^2*7^3*11^4. Wstępnie mamy czas stopu p_1^(e_1-1)*p_2^(e_2-1)*...*p_n^(e_n-1)*x = 5*7^2*11^3*x. Wyznaczamy d dla kolejnych liczb:
- 3 ma d=2
- 5 ma d=4
- 7 ma d=3
- 11 ma d=10
Najwyższa potęga dwójki wśród tych czasów to 4, trójki to 3 oraz piątki to 5, innych czynników nie ma. Otrzymujemy zatem czas stopu liczby 3*5*7*11 wynoszący 4*3*5, jednak wyrzucamy liczbę 5, ponieważ występuje we wcześniejszym wzorze (5*7^2*11^3*x). Zatem x=4*3. Ostatecznie mamy czas stopu równy 5*7^2*11^3*4*3=3913140. Wykonaliśmy 19 iteracji na liczbach 3, 5, 7, 11 oraz potrzebowaliśmy rozbić na czynniki pierwsze 4 czasy stopu tych liczb.
Ostatnie dwa przykłady.
Liczba 3^2*11^4*19^2. Wstępnie mamy 3*11^3*19*x. Obliczamy d:
- 3 ma d=2
- 11 ma d=10
- 19 ma d=18
Najwyższe potęgi czasów stopu d to 2, 9, 5. Otrzymujemy czas stopu liczby 3*11*19=2*5*9. Wyrzucamy liczbę 3^2, bo 3 wystąpiła we wzorze 3*11^3*19*x, jednak pozostawimy 3^1. Zatem x=2*3*5. Ostatecznie mamy: 3*11^3*19*2*3*5=2276010. Zatem liczba 3^2*11^4*19^2 dzieli bez reszty liczbę 2^2276010-1.
Liczba 3*11^4*19^2:
Wstępnie mamy 11^3*19*x. Obliczamy d:
- 11 ma d=10
- 19 ma d=18
Najwyższe potęgi czasów stopu d to 2, 9, 5. Otrzymujemy czas stopu liczby 11*19=2*5*9. Żaden z czynników nie występuje we wzorze 11^3*19*x, zatem ostatecznie mamy: 11^3*19*2*5*9=2276010. To ten sam wynik co poprzednio. Zatem liczba 3*11^4*19^2 dzieli bez reszty liczbę 2^2276010-1.
Jeżeli dobrze oszacowałem złożoność obliczeniową algorytmu to jest on szybszy niż redukcja Pohliga-Hellmana. Co o nim sądzicie?
Dziś wróciłem do tamtych notatek i chcę Wam przedstawić jeszcze raz pewien algorytm umożliwiający obliczanie logarytmu dyskretnego przy podstawie 2, tj. znalezienie dla pewnej (nieparzystej) liczby g takiego najmniejszego n, że g dzieli 2^n-1 bez reszty. Jeżeli II_(i) (p_i^(e_i)) jest faktoryzacją liczby g algorytm ma złożoność:
O[sum_(i) (p_i*log(p_i) + exp((ln(p_i-1)*ln ln(p_i-1))^0,5))]
przy zastosowaniu metody sita kwadratowego do faktoryzacji liczb p_i-1 (złożoność obliczeniowa faktoryzacji liczby n metodą sita kwadratowego wynosi exp((ln(n)*ln ln(n))^0,5). Jeżeli zastosujemy inną metodę np. GNFS, obliczanie (faktoryzacja) składnika p_i-1 będzie wymagało innej złożoności (ponadto niekiedy będzie możliwa faktoryzacja liczb mniejszych niż p_i-1, gdyż czas stopu d - zdefiniowany w dalszej części niekiedy będzie mniejszy aniżeli p_i-1). Algorytm najlepiej działa dla liczb gładkich i wydaje się być wydajniejszy niż redukcja Pohliga-Hellmana (jeżeli dobrze oszacowałem jego złożoność obliczeniową).
Algorytm:
Zdefiniujmy ciąg określony rekurencyjnie dla liczby x=1 oraz wybranej nieparzystej liczby g (dla której obliczymy logarytm dyskretny):
- 0,5*x + g/2 -->> jeżeli x jest nieparzyste
- 0,5*x -->> jeżeli x jest parzyste
Otrzymujemy w ten sposób ciąg liczb, którego iterowanie rozpoczynamy zawsze od liczby 1. Ponadto ciąg zawsze się zapętla i po pewnej liczbie iteracji znów osiąga 1 (podaję to twierdzenie jak i cały algorytm bez dowodu). Oznaczmy liczbę tych iteracji jako d (d to inaczej czas stopu funkcji, zaprzestajemy obliczeń, gdy ciąg osiągnie znów liczbę 1). Czas stopu nigdy nie jest większy niż g-1 oraz prawdopodobnie da się udowodnić, iż jest on zawsze mniejszy lub równy wartości tocjent obliczonej z g (tocjent z liczby g jest zawsze jakąś wielokrotnością czasu stopu d). Przykład:
Niech g = 5. Mamy zatem funkcję:
- 0,5*x + 5/2 -->> jeżeli x jest nieparzyste
- 0,5*x -->> jeżeli x jest parzyste
Zaczynamy obliczenia od x=1.
1
0,5*1 + 2,5 = 3
0,5*3 + 2,5 = 4
4/2 = 2
2/2 = 1
Kończymy obliczenia uzyskawszy ciąg 1, 3, 4, 2, 1. Zajęło nam to d=4 iteracje. W każdym przypadku funkcja zwróci taką najmniejszą możliwą wartość d, że g będzie dzieliło 2^d-1 bez reszty (w tym przypadku 5 dzieli 2^4-1). Ilość iteracji będzie się różnić dla różnych liczb i to właśnie wyznaczanie tej ilośći iteracji dla liczb g, gładkich jest zasadniczym przedmiotem niniejszej pracy.
W ogólnym przypadku liczba gładka p_1^(e_1)*p_2^(e_2)*...*p_n^(e_n) ma czas stopu:
p_1^(e_1-1)*p_2^(e_2-1)*...*p_n^(e_n-1)*x
przy czym x to czas stopu liczby p_1*p_2*...*p_n pozbawiony czynników w potęgach występujących w p_1^(e_1-1)*p_2^(e_2-1)*...*p_n^(e_n-1) (o ile takie wystąpią). Ponadto dowolna złożona liczba p_1*p_2*...*p_n ma czas stopu będący iloczynem najwyższych potęg różnych czynników które występują w czasach stopów liczb p_1, p_2, ..., p_n.
Uwaga: jedynym wyjątkiem od powyższej reguły wydają się być liczby pierwsze Wieferich.
Weźmy liczbę g=13*17. Obliczamy dwa ciągi:
- 0,5*x + 13/2 -->> jeżeli x jest nieparzyste
- 0,5*x -->> jeżeli x jest parzyste
oraz
- 0,5*x + 17/2 -->> jeżeli x jest nieparzyste
- 0,5*x -->> jeżeli x jest parzyste
Liczba 13 ma d=12=4*3 (po takim czasie osiąga liczbę 1, uwaga: w przypadku większych liczb rozbicie czasu stopu na czynniki pierwsze będzie wymagało zastosowania algorytmu sita kwadratowego lub GNFS), a liczba 17 ma d=8. Najwyższa potęga dwójki w tych czasach to 8, a trójki to 3. Liczba 13*17 ma zatem czas stopu wynoszący 3*8=24. Uwaga: ten sam wynik uzyskamy obliczając funkcję:
- 0,5*x + (13*17)/2 -->> jeżeli x jest nieparzyste
- 0,5*x -->> jeżeli x jest parzyste
ale nie na tym nam zależy, gdyż chcemy redukować problem.
To tyle jeżeli chodzi o sam opis algorytmu. Wszystkie twierdzenia sformułowane na potrzeby niniejszego algorytmu podaję bez dowodów, nie posiadam także na tę chwilę formalnych dowodów wspierających wiarygodność niniejszego algorytmu. Z uwagi na fakt, iż powyższe definicje mogą okazać się niejasne poniżej podaję przykłady działania algorytmu.
Weźmy liczbę 3*5*7*11*13*17*19. By znaleźć takie najmniejsze n, że 3*5*7*11*13*17*19 dzieli 2^n-1 bez reszty możemy obliczyć funkcję:
- 0,5*x + (3*5*7*11*13*17*19)/2 -->> jeżeli x jest nieparzyste
- 0,5*x -->> jeżeli x jest parzyste
ale to zbyt złożone obliczeniowo. Obliczamy zatem (zawsze rozpoczynamy interacje od x=1):
- 0,5*x + 3/2 -->> jeżeli x jest nieparzyste
- 0,5*x -->> jeżeli x jest parzyste
Otrzymujemy:
1
0,5*1+1,5=2
0,5*2=1
d wynosi zatem 2. Następnie obliczamy ciąg:
- 0,5*x + 5/2 -->> jeżeli x jest nieparzyste
- 0,5*x -->> jeżeli x jest parzyste
który został policzony w poprzednim przykładzie. Obliczamy także czasy stopów dla kolejnych liczb stanowiących czynniki 3*5*7*11*13*17*19. Otrzymujemy, że:
- 3 ma d=2
- 5 ma d=4
- 7 ma d=3
- 11 ma d=10
- 13 ma d=12
- 17 ma d=8
- 19 ma d=18
najwyższe potęgi różnych czynników, które występują w czasach stopu d powyższych liczb to 8,9,5. Mamy więc 8*9*5=360. Czas stopu liczby 3*5*7*11*13*17*19 wynosi zatem 8*9*5=360. Wykonaliśmy tylko 57 operacji oraz musieliśmy rozłożyć na czynniki pierwsze 7 liczb.
Weźmy liczbę 3*5^2*7^3*11^4. Wstępnie mamy czas stopu p_1^(e_1-1)*p_2^(e_2-1)*...*p_n^(e_n-1)*x = 5*7^2*11^3*x. Wyznaczamy d dla kolejnych liczb:
- 3 ma d=2
- 5 ma d=4
- 7 ma d=3
- 11 ma d=10
Najwyższa potęga dwójki wśród tych czasów to 4, trójki to 3 oraz piątki to 5, innych czynników nie ma. Otrzymujemy zatem czas stopu liczby 3*5*7*11 wynoszący 4*3*5, jednak wyrzucamy liczbę 5, ponieważ występuje we wcześniejszym wzorze (5*7^2*11^3*x). Zatem x=4*3. Ostatecznie mamy czas stopu równy 5*7^2*11^3*4*3=3913140. Wykonaliśmy 19 iteracji na liczbach 3, 5, 7, 11 oraz potrzebowaliśmy rozbić na czynniki pierwsze 4 czasy stopu tych liczb.
Ostatnie dwa przykłady.
Liczba 3^2*11^4*19^2. Wstępnie mamy 3*11^3*19*x. Obliczamy d:
- 3 ma d=2
- 11 ma d=10
- 19 ma d=18
Najwyższe potęgi czasów stopu d to 2, 9, 5. Otrzymujemy czas stopu liczby 3*11*19=2*5*9. Wyrzucamy liczbę 3^2, bo 3 wystąpiła we wzorze 3*11^3*19*x, jednak pozostawimy 3^1. Zatem x=2*3*5. Ostatecznie mamy: 3*11^3*19*2*3*5=2276010. Zatem liczba 3^2*11^4*19^2 dzieli bez reszty liczbę 2^2276010-1.
Liczba 3*11^4*19^2:
Wstępnie mamy 11^3*19*x. Obliczamy d:
- 11 ma d=10
- 19 ma d=18
Najwyższe potęgi czasów stopu d to 2, 9, 5. Otrzymujemy czas stopu liczby 11*19=2*5*9. Żaden z czynników nie występuje we wzorze 11^3*19*x, zatem ostatecznie mamy: 11^3*19*2*5*9=2276010. To ten sam wynik co poprzednio. Zatem liczba 3*11^4*19^2 dzieli bez reszty liczbę 2^2276010-1.
Jeżeli dobrze oszacowałem złożoność obliczeniową algorytmu to jest on szybszy niż redukcja Pohliga-Hellmana. Co o nim sądzicie?
bartekltg
Oct 25, 2015, 10:03:22 PM10/25/15
to
On 24.10.2015 18:52, osobliwy nick wrote:
> Mniej więcej 2 lata temu toczyłem tu kilka dyskusji o algorytmach
> znajdowania liczb pierwszych oraz obliczania logarytmu dyskretnego.
> Dotyczyły one algorytmu, który wówczas sformułowałem oraz aktualnego
> stanu wiedzy w zakresie niniejszej tematyki. Na zakończenie
> doprecyzowałem wtedy ten algorytm i porzuciłem temat.
>
> Dziś wróciłem do tamtych notatek i chcę Wam przedstawić jeszcze raz
> pewien algorytm umożliwiający obliczanie logarytmu dyskretnego przy
> podstawie 2, tj. znalezienie dla pewnej (nieparzystej) liczby g
> takiego najmniejszego n, że g dzieli 2^n-1 bez reszty. Jeżeli II_(i)
> (p_i^(e_i)) jest faktoryzacją liczby g algorytm ma złożoność:
2^n-1
> Mniej więcej 2 lata temu toczyłem tu kilka dyskusji o algorytmach
> znajdowania liczb pierwszych oraz obliczania logarytmu dyskretnego.
> Dotyczyły one algorytmu, który wówczas sformułowałem oraz aktualnego
> stanu wiedzy w zakresie niniejszej tematyki. Na zakończenie
> doprecyzowałem wtedy ten algorytm i porzuciłem temat.
>
> Dziś wróciłem do tamtych notatek i chcę Wam przedstawić jeszcze raz
> pewien algorytm umożliwiający obliczanie logarytmu dyskretnego przy
> podstawie 2, tj. znalezienie dla pewnej (nieparzystej) liczby g
> takiego najmniejszego n, że g dzieli 2^n-1 bez reszty. Jeżeli II_(i)
> (p_i^(e_i)) jest faktoryzacją liczby g algorytm ma złożoność:
Niezależnie od tego, co to ma wspolnego z logarytmem dyskretnym?
g=5.
n = 4, bo 2^4-1 = 16-1=15
Ale g =\= 2^4-1 w Z_7.
15 = 1 =/= 5. w Z_7
> O[sum_(i) (p_i*log(p_i) + exp((ln(p_i-1)*ln ln(p_i-1))^0,5))]
>
> przy zastosowaniu metody sita kwadratowego do faktoryzacji liczb
> p_i-1 (złożoność obliczeniowa faktoryzacji liczby n metodą sita
> kwadratowego wynosi exp((ln(n)*ln ln(n))^0,5). Jeżeli zastosujemy
> inną metodę np. GNFS, obliczanie (faktoryzacja) składnika p_i-1
> będzie wymagało innej złożoności (ponadto niekiedy będzie możliwa
> faktoryzacja liczb mniejszych niż p_i-1, gdyż czas stopu d -
> zdefiniowany w dalszej części niekiedy będzie mniejszy aniżeli
> p_i-1). Algorytm najlepiej działa dla liczb gładkich i wydaje się być
> wydajniejszy niż redukcja Pohliga-Hellmana (jeżeli dobrze oszacowałem
> jego złożoność obliczeniową).
>
> Algorytm:
>
> Zdefiniujmy ciąg określony rekurencyjnie dla liczby x=1 oraz wybranej
> nieparzystej liczby g (dla której obliczymy logarytm dyskretny):
>
> - 0,5*x + g/2 -->> jeżeli x jest nieparzyste - 0,5*x -->> jeżeli x
> jest parzyste
przepisaliśmy do formy, która była łatwiejsza do interpretacji.
Rozbijasz g na iloczyn liczb pierwszych. p1*p2*...*pn
Dla każdego p^k badasz kongruencje liczb 2^n-1 mod p.
Będzie to skończony ciąg o okresie będącym dzielnikiem (p-1)p^(k-1), w
którymś momencie trafisz na 0. (to tylko grupa multiplikatywna modulo p^k).
Wychodzi, że liczba g dzieli 2^n-1 dla n postaci:
n = d_p^k * coś + a_p. dla dowolnego coś
Albo, inaczej mówiąc:
n = a_p mod d_p^k
Masz zestaw takich równań, szukasz n spełniającego je wszystkie
(nie bardzo rozumiem, jak je wyznaczasz. Tu masz sprawdzony
tysiącletni algorytm:
https://pl.wikipedia.org/wiki/Chi%C5%84skie_twierdzenie_o_resztach )
W ostateczności uzyskujesz algorytm spełniające podzielność
na wszystkie potęgi, a więc i iloraz.
Wszystko pięknie, (może trochę rozwlekle).
Tylko gdzie ten obiecany logarytm dyskretny?
pzdr
bartekltg
0 new messages