Cryptography Reference
In-Depth Information
so gilt
x
2
y
2
≡
(
mod
N
)
, wie gewünscht. Dabei stellt die Wahl der
μ
j
sicher, dass
r
j
ν
ij
μ
j
für alle
i
gerade ist, also
y
∈
N
∑
gilt.
=
1
Beispiel
Wir erzeugen ad hoc einige Kongruenzen für den Modul
N
=
91 über der Fak-
torbasis
F
=
{−
1, 2, 3, 5
}
:
5
2
≡−
·
·
·
(
)
1
2
3
11
mod 91
6
2
≡−
1
·
5
·
11
(
mod 91
)
8
2
3
3
≡−
·
(
)
1
mod 91
9
2
≡−
1
·
2
·
5
(
mod 91
)
11
2
≡
·
·
(
)
2
3
5
mod 91
12
2
≡−
1
·
2
·
19
(
mod 91
)
.
Die ersten beiden und die letzte Kongruenz sind zu verwerfen. Das Gleichungs-
system aus der dritten bis fünften Kongruenz lautet
⎛
⎝
⎞
⎠
⎛
⎞
⎛
⎞
110
011
301
011
μ
0
μ
1
μ
2
0
0
0
⎝
⎠
≡
⎝
⎠
(
)
mod 2
T
. Das führt auf
(
)
und hat als Lösung
1, 1, 1
3
2
und
x
2
y
2
x
=
8
·
9
·
11
=
792 ,
y
=(
−
1
)
·
2
·
·
5
=
−
90
≡
(
mod 91
)
.
(
+
)=
(
)=
In der Tat gilt ggT
x
y
,91
ggT
702, 91
13.
Bemerkung
Zum Lösen des linearen Gleichungssystems über
Z
2
bietet sich zunächst der
Gauß-Algorithmus an. Wenn die Parameter
r
,
s
sehr groß sind, geht das nicht
mehr. Andererseits enthält die Koeffizientenmatrix sehr viele Nullen, sodass spe-
zialisierte Verfahren erfolgversprechend sind.
11.4.4 Die Faktorbasis
In den beiden Verfahren, die wir behandeln werden, sind diejenigen Primzahlen
p
2
,...,
p
r
unterhalb einer gewissen Schranke
B
, für die
N
ein Quadrat modulo
p
ist, zu bestimmen. Dazu kommen
p
0
=
−
=
1 und
p
1
2. Diese Zahlen fassen wir
zur
Faktorbasis
zusammen:
F
:
=
{−
1, 2 ,
p
2
,...,
p
r
}
, wobei
N
ein Quadrat modulo
p
i
,
p
i
<
B
, für
i
>
1.
