Algorytm RSA

marvetrick · Post autor: **marvetrick** » 31 sie 2015, o 16:07

Witam, mam problem ze znalezieniem sposobu rozwiązania jednego z zadań, mianowicie:
mam podane liczby pierwsze:
\(\displaystyle{ p=11, q=13}\), do tego mam podaną liczbę \(\displaystyle{ d = 101}\) ( \(\displaystyle{ e \cdot d \equiv 1\pmod{120}}\) ).
Mam także podaną liczbę do zakodowania \(\displaystyle{ l = 142}\)

jak wyznaczyć z tego liczbę e?
przeszukałem pół internetu w poszukiwaniu rozwiązania/podobnego przykładu ale nie znalazłem a sam nie potrafię wpaść na rozwiązanie.
z góry dzięki!

Medea 2 · Post autor: **Medea 2** » 31 sie 2015, o 16:52

Algorytm Euklidesa (rozszerzony) daje \(\displaystyle{ 16 \cdot 120 - 19 \cdot 101 = 1}\), zatem \(\displaystyle{ - 19 \cdot 101 \equiv 1 \pmod {120}}\).

marvetrick · Post autor: **marvetrick** » 31 sie 2015, o 17:02

A czy liczba e w RSA może być ujemna?

Arytmetyk · Post autor: **Arytmetyk** » 31 sie 2015, o 20:23

A czemu by nie?

Zauważ, że \(\displaystyle{ - 19 \equiv 101 \pmod {120}}\)

marvetrick · Post autor: **marvetrick** » 1 wrz 2015, o 11:07

Tego właśnie było mi trzeba, zadanie zrobione, dziękuję bardzo