RSA Primzahlen bestimmen

Question

also ich soll zeigen, dass wenn ich n und phi(n) gegeben hab, dass ich p und q bestimmen kann.

Überlegung:

n = p * q

phi(n) = (p-1)* (q-1) = pq-p-q+1 = n-(n/q)-(n/p)-(n/pq)

Aber weiter komme icg nicht. Würde mich über Tipps freuen:)

Danke im Voraus!

Answer 1

Hi,

Versuche das mal so:

phi(n) = n-p-q+1

<=> n - phi(n) + 1 = p + q

<=> n - phi(n) + 1 = n/q + q

<=> (n - phi(n) + 1)q = n + q^2

<=> q^2 - (n - phi(n) +1)q + n = 0

Comments

Ich hab mal versucht das mit der Mitternachtsformel versucht zu lösen, aber da bleib ich dann bei:

q1 = (n-phi(n)+1) + Wurzel(n^2 -2nphi(n) -2phi(n) +phi(n)^2 -3)

q1 = (n-phi(n)+1) - Wurzel(n^2 -2nphi(n) -2phi(n) +phi(n)^2 -3)

hängen.

Kannst du mir da weiterhelfen?

---

$$ \underbrace{1}_{=a} q^2+ \underbrace{(\varphi(n)-n-1)}_{=b} q+ \underbrace{n}_{=c} = 0$$

Jetzt erstmal \( b^2 \) berechnen:

$$ b^2 = -2 n \varphi(n) + \varphi(n)^2 - 2 \varphi(n) + n^2 + 2 n + 1 $$

Und anschließend einsetzen:

$$ q_{1,2} = \frac{-b\pm\sqrt{b^2-4ac}}{2a}$$

---

Und dann kommt nur ein Ergebnis in Abhängigkeit von phi(n) und n raus oder?

Zum Beispiel q1 = p und q2 = q

---

Die beiden Lösungen sind die beiden Primzahlen.

---

Aber ich hab da doch so einen langen Term mit phi(n) und n und dann noch die Wurzel sowie die Division durch 2. Woran erkenne ich, dass da genau die Primzahlen rauskommen?

---

Wenn p,q Primzahlen sind

n=pq

phi(n)=(p-1)(q-1)

Setz das mal oben in die quadratische Gleichung ein, dann erhältst du:

a=1

b=-p-q

c=pq

Das dann in die Lösungsformel

$$ x_{1,2} =0.5 \left( p+q \pm \sqrt{p^2-2pq+q^2} \right)= 0.5\left( p+q\pm \sqrt{(p-q)^2}\right)$$

Da kommt also p und q als Lösung raus.