Dzielenie z resztą

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
Awatar użytkownika
Johny94
Użytkownik
Użytkownik
Posty: 186
Rejestracja: 11 lut 2011, o 15:54
Płeć: Mężczyzna
Lokalizacja: dolnośląskie
Podziękował: 3 razy
Pomógł: 4 razy

Dzielenie z resztą

Post autor: Johny94 » 3 kwie 2013, o 18:53

Potrzebuję wyznaczyć \(\displaystyle{ x}\) z równania:

\(\displaystyle{ 16575838=x^{11539223} \mod 20288243}\)
Ostatnio zmieniony 4 kwie 2013, o 11:11 przez lukasz1804, łącznie zmieniany 2 razy.
Powód: Temat umieszczony w złym dziale. Niepoprawny kod LaTeX-a: symbol działania modulo to \mod

Awatar użytkownika
Errichto
Użytkownik
Użytkownik
Posty: 1630
Rejestracja: 17 mar 2011, o 18:55
Płeć: Mężczyzna
Lokalizacja: Suwałki
Podziękował: 28 razy
Pomógł: 271 razy

Dzielenie z resztą

Post autor: Errichto » 4 kwie 2013, o 18:54

Rozszerzony algorytm Euklidesa chociażby.

qazze
Użytkownik
Użytkownik
Posty: 4
Rejestracja: 28 cze 2013, o 21:08
Płeć: Mężczyzna
Lokalizacja: Polska

Dzielenie z resztą

Post autor: qazze » 28 cze 2013, o 21:52

przeczytaj sobie to (jest tam ukazany algorytm, który pozwala na ,,odzyskanie x")
http://pl.wikipedia.org/wiki/RSA_%28kryptografia%29

W skrócie trzeba znaleźć liczbę d taką że

\(\displaystyle{ ed\equiv 1 \pmod{\varphi(n)}}\)
gdzie:
\(\displaystyle{ y \equiv x ^{e} \pmod{n}}\)
wtedy można odzyskać x:
\(\displaystyle{ x \equiv y ^{d} \pmod{n}}\)

\(\displaystyle{ 20288243=2027*10009 \\ \varphi(20288243)=(2027-1)(10009-1)=20276208 \\\\ 11539223d \equiv 1 \pmod{20276208}}\)
z rozszerzonego algorytmu euklidesa otrzymamy:
\(\displaystyle{ d = 10007}\)
wystarczy podnieść y (w naszym przypadku \(\displaystyle{ 16575838}\)) do potęgi d modulo n)
\(\displaystyle{ x=16575838 ^{10007} \pmod{20288243}=1243420 \pmod{20288243}}\)

ODPOWIEDZ