Cryptography Reference
In-Depth Information
in case n is a strong probable prime to the base b or false otherwise, in which case
we know that n is composite.
> StrongProbablePrimeTest := proc(n::odd, compiled::truefalse:=false)
local b, c, s, k, x;
if type(procname, 'indexed') then
b := op(procname)
else
error "base not specified"
end if;
if compiled and n <= (kernelopts(wordsize)/2)-1 then
c := CompMinusOneTest
else
c := MinusOneTest
end if;
s:=0;
k := n-1;
while k mod 2=0do
k := k/2;
s:=1+s
end do;
x := Power(b, k) mod n;
x=1orx=n-1orc(x, s, n)
end proc:
The strong probable prime test cannot be used to prove the primality of an integer
but it can prove n to be composite if n actually is. The problem is that if we submit
n to the test for a given base b and n passes it, we do not know if it is because n
is prime or because n is a strong b -pseudoprime. We will see that, for large n ,the
first alternative is much more likely than the second one and this makes it possible
to use this test to find large primes. We perform some computations to illustrate the
behavior of strong pseudoprimes. The next Maple function tells us whether or not a
given odd integer n is strong pseudoprime to the base b :
> StrongPseudoPrimeTest := proc(n::odd, compiled::truefalse := false)
local b;
if type(procname, 'indexed') then
b := op(procname)
else
error "base not specified"
end if;
not isprime(n) and StrongProbablePrimeTest[b](n, ':-compiled')
end proc:
Example 6.4 The strong 2-pseudoprimes less than 10000 are:
> select(StrongPseudoPrimeTest[2], [seq(2*i-1, i=2..5000)]);
[2047, 3277, 4033, 4681, 8321]
We see that there are only five strong 2-pseudoprimes in this interval while, as we
have seen, the number of 2-pseudoprimes in the same interval is 22. We also counted
94 2-pseudoprimes in the interval
10 8
10 8
10 7
[
..
+
]
and now we see that the number
of strong 2-pseudoprimes in the same interval is:
> count(10ˆ8 ..10ˆ8+10ˆ7, StrongPseudoPrimeTest[2]);
21
Search WWH ::




Custom Search