wyznaczanie potęgi (modularnie)

[niebieska_biedronka]

Wyznacz\(\displaystyle{ k}\) takie, że \(\displaystyle{ 3^{k} = 2 (\mod 65537).}\)
Wskazówki:
a) pokaż, że \(\displaystyle{ 3}\) jest pierwiastkiem prymitywnym \(\displaystyle{ (\mod 65537)}\)
b) wywnioskuj, że \(\displaystyle{ 2048 | k}\), ale \(\displaystyle{ 4096 \nmid k}\)
c) uzasadnij, że jest \(\displaystyle{ 16}\) możliwych wartości dla \(\displaystyle{ k}\).

ja nie wiem, czemu mają służyć te wskazówki i jak to rozwiązać (nie obliczając logarytmu dyskretnego)...

[Zordon]

Po pierwsze, \(\displaystyle{ p=65537}\) to bardzo specjalna liczba, mianowicie \(\displaystyle{ 65537=2^{16}+1}\). W dodatku jest to liczba pierwsza.
Po drugie, w tym zadaniu istotnie trzeba obliczyć logarytm dyskretny, ale można to zrobić sprytnie, po to są te wskazówki.

a) nie da się tego zrobić bez sporej porcji obliczeń, trzeba obliczyć \(\displaystyle{ 3^2,3^4,3^8,3^{16},...,3^{2^{16}} \pmod{p}}\)

b,c) ale trochę inaczej:
Wszystkie równości \(\displaystyle{ \pmod{p}}\).
skoro \(\displaystyle{ 3^k=2}\) oraz \(\displaystyle{ 2^{16}=-1}\) (dlaczego?), to \(\displaystyle{ 3^{16k}=-1}\)
ale \(\displaystyle{ 3}\) jest pierwiastkiem pierw., zatem \(\displaystyle{ -1=3^{\frac{p-1}{2}}=3^{2^{15}}}\)
Stąd \(\displaystyle{ 3^{16k}=3^{2^{15}}}\)
czyli \(\displaystyle{ 16k\equiv 2^{15} \pmod{p-1}}\)
\(\displaystyle{ 16k\equiv 2^{15} \pmod{2^{16}}}\)
No i to rzeczywiście ma 16 rozwiązań modulo \(\displaystyle{ 2^{16}}\), tylko trzeba się zastanowić.

[niebieska_biedronka]

o raaaaany... no nic, dzięki, to już mam prawie gotowe rozwiązanie.

Zapytam jeszcze tylko z ciekawości - skąd wiedziałeś, że \(\displaystyle{ 65537}\) to akurat \(\displaystyle{ 2^{16} +1}\) ?

[bakala12]

To bardzo znana liczba, na przykład czwarta liczba Fermata.

[Zordon]

Po jakimś czasie zabawy w programowanie zostają w głowie takie liczby Nie pamiętałem dokładnej wartości, ale wiedziałem, że się zaczyna od \(\displaystyle{ 655...}\), ale to wystarczyło, żeby wykryć co trzeba...

[niebieska_biedronka]

No tak, znam to uczucie - tyle że zatrzymałam się już na \(\displaystyle{ 1024}\)