numlib::proveprime

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.

Syntax

numlib::proveprime(n)

Description

numlib::proveprime(n) tests whether n is a prime. Unlike isprime, numlib::proveprime always returns a correct answer.

numlib::proveprime returns the following values:

  • 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, numlib::proveprime returns 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)

numlib::checkPrimalityCertificate checks primality certificates produced by numlib::proveprime.

Examples

Example 1

Proving that 1159523 is prime can be reduced to proving that 10343 is prime:

certificate := numlib::proveprime(1159523)

Example 2

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.

numlib::proveprime(179424673)

Use numlib::checkPrimalityCertificate to check the result:

numlib::checkPrimalityCertificate(%)

Parameters

n

Positive integer.

Return Values

TRUE, FALSE, FAIL, or a list or sequence of lists.

References

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.

See Also

MuPAD Functions