Primality proving using elliptic curves
MuPAD® notebooks will be removed in a future release. Use MATLAB® live scripts instead.
MATLAB live scripts support most MuPAD functionality, though there are some differences. For more information, see Convert MuPAD Notebooks to MATLAB Live Scripts.
numlib::proveprime(n) tests whether
a prime. Unlike
returns a correct answer.
numlib::proveprime returns the following
TRUE when it can prove that the
number is a prime.
FALSE when it can prove that the
number is not a prime.
FAIL when it cannot prove that
the number is a prime and cannot prove otherwise. In such cases, the
input most likely is a prime.
A primality certificate, which is a list or a sequence
of lists containing proof for the primality of the number. Typically,
primality certificates for very large numbers.
A primality certificate is a sequence of lists of the form [N, D, lm, a, b, x, y, ls], where
N is a pseudoprime
D is an integer (fundamental discriminant)
lm is a list of prime factors
a, b, x, y are integers modulo N
ls is another list of prime factors (subset of the factors in lm)
primality certificates produced by
Proving that 1159523 is prime can be reduced to proving that 10343 is prime:
certificate := numlib::proveprime(1159523)
Typically, 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.
check the result:
or a list or sequence of lists.
numlib::proveprime implements the Atkin-Goldwasser-Kilian-Morain
algorithm for proving primality. For information about primality proving
and this particular algorithm, see:
Atkin, A. O., and F. Morain. “Elliptic curves and primality proving.” Mathematics of Computation. Vol. 61, Number 203, 1993.
Goldwasser, S., and J. Kilian. “Almost all primes can be quickly certified”. Proceedings of the 18th annual ACM symposium on theory of computing. Berkeley, CA, US, 1986, pp. 316–329.