Potrzebuję wyznaczyć \(\displaystyle{ x}\) z równania:
\(\displaystyle{ 16575838=x^{11539223} \mod 20288243}\)
Dzielenie z resztą
-
Johny94
- 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ą
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
Powód: Temat umieszczony w złym dziale. Niepoprawny kod LaTeX-a: symbol działania modulo to \mod
Dzielenie z resztą
przeczytaj sobie to (jest tam ukazany algorytm, który pozwala na ,,odzyskanie x")
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}}\)
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}}\)