Logarytmy dyskretne wciąż są traktowane jako funkcje jednokierunkowe. A z tą jednokierunkowością... Poniżej przedstawiam program liczący potęgi na dwie różne permutacje modulo n. Przypominam, bo wiele lat temu to publikowałem, teraz mam gotowy kod.
Moją słabością jest brak zapamiętywania - zawsze na nowo wyprowadzam, i okazywało się, że jestem w stanie łatwo pomylić ze sobą potęgę oraz podstawę potęgi w kodzie. Dlatego to co piszę o kodzie nie zawsze daje właściwy obraz. Dlatego wolę opisywać kod niż go prezentować. Tutaj prawie kopiuj - wklej gotowego.
g jest podstawą potegi, s = '1000..._g' jest wartością potegi,modulo n
Numer w linii oznacza poziom wcięcia kodu.
0 def dysLog(g,s,n):
1 if s==g: return 1
1 r = n-g
1 c = 1
1 a = g
1 while 1:
2 a = -a*r
2 c+=1
2 #patrz a,r, dla zobaczenia co sie dzieje z danymi, funkcja % może dawać zły wynik
2 if 0>a:
3 b=(-a)//n
3 a+=b*n
3 a+=n
2 #patrz a koncowa wartosc
2 if a==s: return c
2 if a==g and c>n-1: return -c #nie ma rozwiazań, cykl z małego twierdzenia Fermata
Dane np.:
g=11
n=17
0 for a in range(n):
1 print g,"^", dysLog(g,a,n), "=",a,
0 print
0 for i in range(1,n):
1 print i,":",(g**i)%n," ",
0 print
Rekursywna konwersja potęgi na system o podstawie n, w którym wystarczy obserwować wartość na pozycji najmniej znaczącej modulo n.
