|
Autor: mk 01.04.2011 19:27 1256 |
|
||
| RSA |
Nachricht-zu-Zahl
modulo-Rechnen
modulares Potenzieren
Algorithmus von Euklid
Euler-Funktion
Satz von Euler
modulares Inverses
Primzahlen finden
Schlüsselpaar
Angriff
Sicherheit
|
|
|
Primfaktorzerlegung |
import math
import functools
import operator
def primfaktoren(n):
"""
die Primfaktoren von n werden als Liste zurückgegeben
"""
# m = n
f = []
while n%2 == 0:
f = f + [2]
n = n//2
while n%3 == 0:
f = f + [3]
n = n//3
t = 5
diff = 2
w = round(math.sqrt(n))
while t <= w:
while n%t == 0:
f = f + [t]
n = n//t
t = t + diff
diff = 6 - diff
if n > 1:
f = f + [n]
# assert functools.reduce(operator.mul,f,1) == m
return f
Für eine Primzahl p gibt es nur die Fälle: 1.Fall: 3∣p+1 oder 2.Fall: 3∤p+1. Im 1.Fall könnte p+2 eine Primzahl sein, da ungerade und nicht durch 3 teilbar. p+4 =p+1 + 3 ist aber wieder durch 3 teilbar, sodass der nächste Primzahl-Kandidat p+6 wäre. Im zweiten Fall muss p+2 durch 3 teilbar sein, weil p und p+1 es nicht waren. Man wird daher p+4 untersuchen. p+5 ist aber wieder durch 3 teilbar, sodass p+6 es nicht ist. p+6 kommt als Primzahl-Kandidat in Frage. Im ersten Fall sollte man also p+2 und dann p+6, im zweiten Fall p+4 und dann p+6 untersuchen. Die Primzahlkandidaten haben also abwechselnd eine Differenz von 2 und 4.
// Herrmann, Algorithmen Arbeitsbuch, S.133
type
tP = array[1..50] of integer;
tH = array[1..50] of integer;
procedure primfak(n : longint; var p : tP; var h : tH);
var
t,w : longint;
diff,i : integer;
begin
for i := 1 to 50 do h[i] := 0;
i := 0;
for t := 2 to 3 do
if n mod t = 0
then
begin
i := i+1; p[i] := t;
while n mod t = 0 do
begin
n := n div t;
h[i] := h[i] + 1;
end;
end;
t := 5; diff := 2;
w := round(sqrt(n));
while t <= w do
begin
if n mod t = 0
then
begin
i := i+1; p[i] := t;
while n mod t = 0 do
begin
n := n div t;
h[i] := h[i] + 1;
end;
end;
t := t + diff; diff := 6 - diff;
end;
if n > 1
then
begin
i := i + 1; p[i] := n; h[i] := h[i] + 1;
end;
end;