Cryptography Reference
In-Depth Information
Let us compute the square roots of
F
7
modulo
p
using Algorithm 2.8 with the
help of Maple, i.e., let us solve the equation
x
2
2
2
7
≡
+
1
(
mod 31873
)
.Wedoit
step by step. Observe first that:
> F_7 := 2ˆ128+1;
a := F_7 mod p;
340282366920938463463374607431768211457
17919
and hence computing these square roots amounts to computing the square roots of
17919 in
Z
31873
. Note also that
> p mod 4;
1
so that we are in the “difficult” case of the algorithm and we will need to execute the
for
loop in it. Next we choose a quadratic non-residue modulo
p
;
> randomize():
lg := 1:
while lg = 1 do
h := (rand(1 .. p-1))():
lg := numtheory:-legendre(h, p)
end do:
h;
30863
We compute
s
and
t
:
> ifactor(p-1);
(2)ˆ7 (3) (83)
> s := 7; t := 3*83;
7
249
Now we compute
A
and
H
:
> A := Power(a, t) mod p;
H := Power(h, t) mod p;
29298
5250
We initialize
v
:
>v:=0:
We start the
for
loop with
i:=1
:
> i := 1: (A*Hˆv)ˆ(2ˆ(s-1-i)) mod p;
1
2
s
−
1
−
i
AH
v
does not hold, thus the value of
v
remains equal to 0. Similarly, the analogous computation for
i
The condition
(
)
≡−
1
(
mod
p
)
3gives
1 as result, so the value of
v
remains 0 during the first three iterations of the loop. In
the fourth iteration we have:
=
2 and
i
=
> i := 4: (A*Hˆv)ˆ(2ˆ(s-1-i)) mod p;
31872
