Cryptography Reference
In-Depth Information
2 2
3063
12667
12667
3063
415
3063
3063
12667
·
=−
=−
=
=
3063
415
158
415
2
79
415
415
79
20
79
79
415
·
=−
=−
=−
=−
=
=
2 2
5
79
79
5
4
5
·
5
=
=
=
=
=
1
.
79
Thus we see that 41069779796933 is a quadratic residue modulo 673275095033.
The built-inMaple function numtheory:-Jacobi uses this algorithm to com-
pute the Jacobi symbol n by calling numtheory:-Jacobi(m,n) . In particu-
lar, this function also computes Legendre symbols and, as already mentioned, there
is also numtheory:-legendre which is just the specialization of the preceding
function when the second argument is prime. To carry out the preceding computation
we can use either of these functions, for example:
> numtheory:-Jacobi(41069779796933, 673275095033);
1
The algorithm applied in the preceding example is then the following. Note that
the algorithm is recursive, i.e., it calls itself:
Algorithm 2.7. Jacobi (
(Computation of the Jacobi symbol) .
Input :Aninteger m and an odd positive integer n .
m
,
n
)
Output : The Jacobi symbol n .
if n
=
1 then return 1.
Set m
:=
m mod n .
if m
=
0 then return 0.
if m
1 then return 1.
Write m = 2 e m 1 with m 1 odd.
if e is even then
s := 1
elif n ≡± 1 ( mod 8 ) then
s := 1
elif n ≡± 3 ( mod 8 ) then
s := − 1
end if .
if m 1
=
(
) and n
(
) then
3
mod 4
3
mod 4
s := − s
end if .
return s
· Jacobi (
n
,
m 1
)
.
Remark 2.10 Except for the removal of powers of 2, the sequence of recursive calls
in Algorithm 2.7 is the same as the one used by the Euclidean algorithm to com-
pute gcd
, and an analysis similar to that of the Euclidean algorithm shows
that the complexity is also the same, so that the running time of this algorithm
can be estimated as O
(
m
,
n
)
2
(
len
(
m
)
len
(
n
))
or, assuming that m
<
n , O
(
len
(
n
)
)
. Thus
 
 
Search WWH ::




Custom Search