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
Search WWH ::




Custom Search