numlib::proveprime
--
primality proving using elliptic curvesnumlib::proveprime
(n)
tests whether
n
is a prime.
Unlike isprime
,
numlib::proveprime
always returns a correct answer.
numlib::proveprime(n)
n |
- | positive integer |
numlib::proveprime
may simply return TRUE
or FALSE
.
numlib::proveprime
may return FAIL
to
indicate that the input is prime with high probability, but no proof
could be found.
numlib::proveprime
may also return a list or a sequence
of lists containing a proof for the primality of n
.
A particular domain numlib::Ecpp
contains three
parameters that control the algorithm:
Ecpp::maxit
(default 10000) is the maximal number of
iterations in Pollard's rho factorization method.Ecpp::maxh
(default 17) is an integer that controls
the number of possibilities tried at each level of the algorithm [in
technical words, it is the maximum value of the order
h(-D)].Ecpp::B
(default 1000) controls the size of the
numbers to check. If n<=Ecpp::B
, the program simply
calls isprime to check if n
is prime. In this case the
program returns either TRUE
or FALSE
. The
integer Ecpp::B
should be at least 11, because the
algorithm used does not work for n=2, 3, 5, 7 or 11.Increasing Ecpp::maxit
or Ecpp::maxh
will
make the algorithm more powerful, but slower.
ifactor
, isprime
, ithprime
, nextprime
, numlib::prevprime
numlib::proveprime
manages to prove that
n
is a prime, it returns a primality certificate. A
primality certificate is a sequence of lists of the form
[N,D,l_m,a,b,x,y,l_s] where `N is a pseudo-prime,
D is an integer (fundamental discriminant), l_m
is a list of prime factors, a, b, x, y are integers modulo
N, and l_s is another list of prime factors
(subset of the factors in l_m).numlib::proveprime
can be checked by the function
numlib::check
.Proving that 10007 is prime can be reduced to proving that 317 is prime. The primality of 317 is known because 317 is sufficiently small.
>> numlib::proveprime(10007)
[10007, 43, [31, 317], 9439, 4778, 0, 5622, [317]]
Normally, the primality of the input is reduced to the primality of a smaller integer, the primality of that integer is reduced to the primality of an even smaller integer, and so on.
>> numlib::proveprime(1048583)
[1048583, 7, [2, 2, 2, 130817], 665765, 793371, 1, 44804, [130817]], [130817, 7, [2, 7, 2, 4663], 26992, 105206, 0, 75747, [4663]], [4663, 24, [2, 5, 463], 1343, 4004, 1, 2809, [463]]
numlib::check
can be used to check the
result:
>> numlib::check(%)
TRUE
Use userinfo
to get more detailed
information:
>> setuserinfo(Any,1): numlib::proveprime(1048583)
Info: found next candidate: 130817 Info: found next candidate: 4663 Info: found next candidate: 463 [1048583, 7, [2, 2, 2, 130817], 665765, 793371, 1, 44804, [130817]], [130817, 7, [2, 7, 2, 4663], 26992, 105206, 0, 75747, [4663]], [4663, 24, [2, 5, 463], 1343, 4004, 1, 2809, [463]]
>> numlib::check(%)
Info: 1048583 is prime if 130817 is prime Info: 130817 is prime if 4663 is prime Info: 4663 is prime if 463 is prime TRUE