Algorithmus zur Primfaktorenzerlegung

unforgiven

Well-Known Member
Hi

zuerst einmal entschuldigung, dass ich mein posting hier hin geknipst habe, aber wusste sonst nicht wo hin damit :-/

also habe folgendes problem:
im büro muss ich ein Software-Dongle programmieren. nun arbeite ich gerade an der Verschlüsselung und da dachte ich mir ich setze hier RSA ein. nun habe ich mich mit RSA etwas auseinander gesetzt und muss nun einen Wert (N, Modulus) in Primfaktoren zerlegen, also Primfaktorenzerlegung :)

nun habe ich aber das problem wie ich das anstellen soll, gibts da irgend ein algorithmus dafür?
mit google hab ich nichts gescheites gefunden... :confused:

danke schomal im voraus für eure hilfe
und nochmals sorry falls es im falschen
bereich war..

thx&bye
u4giv
 

oBdA

Well-Known Member
Tach auch!

So'n Algorithmuß gibt es "Euklidische Primfaktorzerlegung". Wenn ich mich recht erinnere geht das so:

Zahl : Primzahl => Ergenbis_1 // Primzahl beginnend mit 2
Ist dies nicht restfrei möglich, das ganze mit der nächst größeren Primzahl ...

Ergebnis_1 : Primzahl => Ergebnis_2

...

Das Ganze solange widerholen bis als Ergebins "1" herauskommt.

=> Multiplikation der benutzten Primzahlen entspricht der Primfaktorzerlegung

Bsp:

85 : 2 = \not \in N
85 : 3 = \not \in N
85 : 5 = 17 \in N
17 : 2 = \not \in N
17 : 3 = \not \in N
17 : 5 = \not \in N
17 : 7 = \not \in N
17 : 11 = \not \in N
17 : 13 = \not \in N
17: 17 = 1 \in N

=> 5*17 ist Primfaktorzerlegnug von 85


Achtrung : Das ist nur aus meinem löchrigen Gedächtnis, muß also nicht zwangsläufig richtig sein

hang lost
 
Oben