Documentation

# `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.