Rozkład n w systemie RSA

[Makiwarrior]

Znane jest \(\displaystyle{ n = 84773093}\) oraz \(\displaystyle{ \phi(n) = 84754668}\). Rozwiązując odpowiednie równanie, znaleźć rozkład \(\displaystyle{ n}\).

[Qń]

Jeśli \(\displaystyle{ n}\) jest iloczynem liczb pierwszych \(\displaystyle{ p,q}\), to mamy:
\(\displaystyle{ \phi (n) = (p-1)(q-1)= n+1 - (p+q)}\)

Q.

[Makiwarrior]

Fajnie tylko z tego wychodzi równanie kwadratowe, a przy tak dużych liczbach jest nie do rozwiązania :/ Jakieś sugestie?

[Qń]

Dlaczego nie do rozwiązania? Przy pomocy kalkulatora to kwestia pół minuty, a bez kalkulatora też się da - jedyna trudność to znalezienie pierwiastka z \(\displaystyle{ 26569}\), ale to można zrobić metodą prób i błędów: wiadomo, że \(\displaystyle{ 160^2=25600}\), więc ten pierwiastek to musi być niewiele ponad \(\displaystyle{ 160}\), a dodatkowo ostatnia jego cyfra to musi być \(\displaystyle{ 3}\) lub \(\displaystyle{ 7}\). I łatwo sprawdzić, że jet to \(\displaystyle{ 163}\).

Q.

[Makiwarrior]

No dobra, ja to liczę tak i wychodzi chyba inaczej niż tobie:
\(\displaystyle{ 84754668=84773093+1-(p+q)}\)
\(\displaystyle{ 84754668=84773094-p-q}\)
\(\displaystyle{ p=18426-q}\)

\(\displaystyle{ p \cdot q=84773093}\)
\(\displaystyle{ q=\frac{84773093}{p}}\)

\(\displaystyle{ p=18426- \frac{84773093}{p}}\)
\(\displaystyle{ 18426=p+\frac{84773093}{p}}\)
\(\displaystyle{ 18426=\frac{p^{2}+84773093}{p}}\) \(\displaystyle{ \cdot p}\)
\(\displaystyle{ 18426p=p^{2}+84773093}\)
\(\displaystyle{ 0=p^{2}-18426p+84773093}\)

\(\displaystyle{ \Delta=425104}\)
\(\displaystyle{ \sqrt{\Delta}=652}\)

\(\displaystyle{ p=9539}\)
\(\displaystyle{ q=8887}\)

Dobrze?

[Qń]

Zgadza się, ale można było szybciej - skoro wiemy, że \(\displaystyle{ p+q=18426}\) oraz \(\displaystyle{ pq= 84754668}\), to ze wzorów Viete'a od razu możemy stwierdzić, że \(\displaystyle{ p,q}\) to pierwiastki równania:
\(\displaystyle{ x^2-18426x+84754668=0}\)
Twoje rachunki są poprawne, a moja propozycja wykonania ich bez użycia kalkulatora opierała się na obserwacji:
\(\displaystyle{ \Delta = 425104=4\cdot 106276= 4\cdot 4\cdot 26569}\)
(podzielność przez cztery łatwo zauważyć) i teraz jeśli szukamy pierwiastka z delty, to musimy spierwiastkować \(\displaystyle{ 26569}\) (i robimy to jak wyżej).

Q.

[Makiwarrior]

Heh, nieźle. Ja na razie będę sobie liczył na piechotę