logarytm dyskretny

[niebieska_biedronka]

Dwa zadania:
1. Pokazać, że \(\displaystyle{ \log_3 8576 =1234, \quad p=53047}\)
Znam metodę szukania logarytmu dyskretnego, ale czy da się to jakoś zrobić szybciej? Tu są takie duże liczby, że obliczanie tego metodą Pohliga - Hellmana zajmie wieczność...

2. Niech \(\displaystyle{ p}\) będzie liczbą pierwszą. Jeśli \(\displaystyle{ \alpha}\) jest pierwiastkiem pierwotnym \(\displaystyle{ (\mod p )}\), to \(\displaystyle{ \log_{\alpha} (\beta_1 \beta_2)=\log_{\alpha} (\beta_1 )+\log_{\alpha} ( \beta_2) (\mod p-1)}\)

[Zordon]

1. Masz tylko zweryfikować. Więc liczysz \(\displaystyle{ 3^{1234} \pmod{p}}\)


2. u mnie \(\displaystyle{ g}\) to pierwiastek pierwotny.
Mamy taki izomorfizm: \(\displaystyle{ f:\ZZ_{p-1}\to\ZZ_p^*}\), \(\displaystyle{ f(k)=g^k}\). Gdzie \(\displaystyle{ \ZZ_{p-1}}\) rozumiem jako zbiór \(\displaystyle{ \{0,1,...,p-1\}}\).
wtedy \(\displaystyle{ f^{-1}}\) to logarytm dyskretny, i równość z zadania to po prostu zachowywanie działań. Wystarczy zatem uzasadnić, że \(\displaystyle{ f}\) jest izomorfizmem.

[niebieska_biedronka]

Gdzie \(\displaystyle{ \ZZ_{p-1}}\) rozumiem jako zbiór \(\displaystyle{ \{0,1,...,p-1\}}\)

Chyba raczej \(\displaystyle{ \{0,1,...,p-2\}}\), żeby zachodziła równoliczność...? bo \(\displaystyle{ \ZZ^*_{p-1}=\{1,..p-1\}}\)

[Zordon]

Tak, mała pomyłka.

[niebieska_biedronka]

Ok, wolałam się upewnić