Cryptography Reference
In-Depth Information
−
=−
Now we obtained
p
1
1mod
p
as result, so we increase the value of
v
accordingly:
>v:=v+2ˆi;
16
Similarly, the value of
v
gets increased for
i
=
5 and
i
=
6:
>i:=5:
(A*Hˆv)ˆ(2ˆ(s-1-i)) mod p;
31872
> v := v + 2ˆi;
48
>i:=6:
(A*Hˆv)ˆ(2ˆ(s-1-i)) mod p;
31872
> v := v + 2ˆi;
112
At the end of the loop we obtain the value
v
=
112 and hence we should have
that
AH
112
≡
1
(
mod
p
)
. We check that this is indeed the case:
> A*Hˆ112 mod p;
1
We can now find a square root of
F
7
modulo
p
, which is:
> x := aˆ((t+1)*(1/2))*Hˆ56 mod p;
23037
Therefore, the other square root is:
>y:=-xmodp;
8836
Z
31873
:
A quick check that these are indeed the square roots of
a
=
17919 in
> modp
∼
([x, y]ˆ
∼
2, p);
[17919, 17919]
The previous example serves to illustrate how the algorithm works step by step
but Maple has this algorithm built-in in the function
numtheory:-msqrt
, which
computes modular square roots whenever possible, even if the modulus is not prime.
For the prime case, this function calls the function
numtheory:-_msqrtprime
,
which implements Tonelli's algorithm. This function is local to the module
numtheory
but the reader interested in looking at its code can do so with the com-
mands
kernelopts(opaquemodules=false)
followed by
interface
(verboseproc=2)
and
print(numtheory:-_msqrtprime)
. Of course,
in what follows we will use the function
numtheory:-msqrt
to compute modular
square roots whenever necessary.
The algorithm to compute modular square roots can be extended to non-prime
moduli. There is a case of special interest for cryptographywhich iswhen themodulus
n
pq
is the product of two distinct primes
p
,
q
. We have already discussed the
existence and the number of roots in this case. Based on this discussion, the following
exercise is straightforward:
=
