Information Technology Reference
In-Depth Information
Proof.
We analyse case by case.
-
Gold:
Let
d
=2
e
+1, with
gcd
(
e, m
) = 1, and let
e
=
rk
+
s
,where
s<k
0.
Then
2
e
+1=2
s
(2
rk
1) + 2
s
+1
2
s
+1(mod 2
k
−
≡
−
1)
,
with
gcd
(
e, m
)=1
⇒
gcd
(
e, k
)=1
⇒
gcd
(
s, k
)=1.
-
Kasami:
Let
d
=2
2
e
2
e
+1,with
gcd
(
e, m
) = 1, and let
e
=
rk
+
s
,where
−
s<k
0. Then
2
2
e
2
e
+1=2
2
s
(2
rk
1) + 2
2
s
2
s
(2
rk
2
s
+1
−
−
−
−
1)
−
2
2
s
2
s
+1(mod 2
k
≡
−
−
1)
.
⇒
gcd
(
s, k
)=1.
-
Welch
and
Niho
:Let
m
=2
t
+1,and
m
=
kl
.Then
with
gcd
(
e, m
)=1
⇒
gcd
(
e, k
)=1
kl
−
1
=
kl
−
k
+
k
−
1
l
−
1
k
+
k
−
1
t
=
=
.
2
2
2
2
2
Note that
k>
k−
1
2
>
0. Therefore, for the Welch exponent
d
=2
t
+3, we
have
2
t
+3=2
k
−
2
(2
l
−
2
k
1) + 2
k
−
1
−
+3
2
2
k
−
1
+3(mod2
k
≡
−
1)
.
2
l−
1
2
k−
1
2
Let
r
=
k
,and
s
=
.Then
t
=
rk
+
s
.FortheNihocasewehaveto
consider two cases:
•
t
even:
In
t
=
rk
+
s
,if
s
is also even, then
t/
2=
rk/
2+
s/
2 and:
2
t
+2
t/
2
1=2
s
(2
rk
1) + 2
s
+2
s/
2
(2
rk/
2
1) + 2
s/
2
−
−
−
−
1
2
s
+2
s/
2
1(mod2
k
≡
−
−
1)
.
If
s
is odd, then
t
2
rk
+
s
2
=
(
r
−
1)
k
+
k
+
s
2
(
r
−
1)
k
+3
s
+1
2
=
(
r
−
1)
k
+
3
s
+1
2
=
=
,
2
and finally 2
t
+2
t/
2
2
s
+2
(3
s
+1)
/
2
1(mod2
k
−
1
≡
−
−
1)
.
•
t
odd:
We have
t
+1
2
=
rk
+
s
+1
2
t
+
t
+1
2
=
rk
+
s
+
rk
+
s
+1
2
3
t
+1
2
=
3
rk
+3
s
+1
2