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




Custom Search