Cryptography Reference
In-Depth Information
<
<
(
,
)
=
n
. Note that, by Remark 6.4, any
b
such that 1
b
n
and gcd
b
n
1isa
witness for
n
.
Algorithm 6.1. Strong probable prime test.
Input
: An odd integer
n
>
3 and an integer
b
with 1
<
b
<
n
−
1.
Output
: Either “strong probable prime” or “composite”.
1.
Compute
s
and
t
such that
n
2
s
t
,with
t
odd.
−
1
=
b
t
mod
n
;
i
2.
Set
u
:=
:=
1.
3.
if
u
1
then
return
“strong probable prime”
end if
;
while
u
=
=
1
and
u
=
n
−
1
and
i
<
s
do
x
2
mod
n
;
i
:=
i
+
1
end do
;
if
u
=
n
−
1
then
return
“strong probable prime”
else
return
“composite”
end if
.
u
:=
The strong probable prime test can be implemented in Maple as follows. First we
give an auxiliary function that tests whether
b
2
i
t
≡−
1
(
mod
n
)
for some
i
with
2
s
t
:
0
≤
i
≤
s
−
1, where
n
−
1
=
> MinusOneTest := proc(x, s, n)
local u, i;
u:=x;
i:=1;
while u <> n-1 and u <> 1 and i<sdo
u := modp(uˆ2, n);
i:=i+1
end do;
u = n-1
end proc:
We will also use the compiled version of this function:
> CompMinusOneTest := Compiler:-Compile(MinusOneTest):
Now, the strong probable prime test is given by the next function. The function is
indexed by the base so that, to submit an integer to the test to base
b
, this function will
be called as
StrongProbablePrimeTest[b]
. The function is able to use the
compiled version of
MinusOneTest
whenever the size of the integer to be tested
allows it; this produces some speed gains that probably will only be noticeable,
for integers of appropriate size, with 64-bit versions of Maple (with the external C
compiler installed). The function takes as input the odd integer
n
to be tested and
an optional Boolean argument compiled that tells the function whether or not to use
the compiled version of
MinusOneTest
; the default value is
false
so that the
procedure will work even if the C compiler is not installed. The output is either
true