Cryptography Reference
In-Depth Information
11.3.1 Die Methode
Es sei
p
ein - uns unbekannter - Primteiler von
N
, also
N
∈
N
>
1
.
Ist
a
eine zu
N
teilerfremde natürliche Zahl, so ist
a
auch zu
p
teilerfremd. Nach
dem Satz 6.10 von Fermat gilt
=
pm
mit
m
a
p
−
1
≡
1
(
mod
p
)
.
−
Jedes Vielfache
k
von
p
1 erfüllt dann ebenfalls
a
k
a
k
≡
(
)
|
−
1
mod
p
,d.h.
p
1.
a
k
|
−
Wegen
p
1 liefert der euklidische Algorithmus eine Zahl
d
mit
a
k
p
|
d
=
ggT
(
−
1,
N
)
.
Ist
d
=
N
,soist
N
zerlegt. Diese
p
−
1
-Methode von Pollard
ist dann sinnvoll,
−
wenn
p
1 ein Produkt von kleinen Primzahlen ist. Man wählt für
k
das Produkt
aller Primzahlpotenzen unterhalb einer vorgegebenen Schranke
B
und findet so
ein Vielfaches
k
von
p
−
1, d. h.,
)=
q
∈
P
q
e
,
wobei
q
e
=
λ
(
)=
(
≤
k
B
kgV
1, . . . ,
B
B
.
11.3.2 Glatte Zahlen
∈
N
∈
N
Es sei
B
. Eine Zahl
m
heißt
B
-glatt
, wenn jede Primzahl
p
, die
m
teilt,
kleiner gleich
B
ist:
|
⇒
≤
p
m
p
B
.
Die Zahl
m
heißt
B
-potenzglatt
, wenn jede Primzahlpotenz
p
ν
, die
m
teilt, kleiner
gleich
B
ist:
p
ν
p
ν
≤
|
m
⇒
B
.
Glattheit
spielt eine wichtige Rolle bei modernen Faktorisierungsverfahren.
Beispiel
Die Zahl
N
=
60 ist 5-potenzglatt, die Primzahlen 59 und 61 nicht. Übrigens ist
λ
(
)=
60.
Die Zahl 2
104
5
3
44
5
49
7
47
ist 7-glatt und 7
47
-potenzglatt (7
47
10
39
).
·
·
·
≈
5
·
Bemerkung
Eine natürliche Zahl
m
∈
N
ist genau dann
B
-potenzglatt, wenn gilt
m
|
λ
(
B
)
.
