# Primes and Primality Testing

Primality testing algorithms enable the user to certify the primality of prime integers. Proving the primality of very big integers can be time consuming and therefore in some of the algorithms using primes and factorization of integers the user can speed up the algorithm by explicitly allowing Magma to use probable primes rather than certified primes. A *probable prime* is an integer that has failed some compositeness test; if an integer passes a compositeness test it will be composite, but there is a (small) probability that a composite number will fail the test and is hence called a probable prime. Each Miller-Rabin test for instance, has a probability of less than $1/4$ of declaring a composite number probably prime; in practice that means that numbers that fail several such cheap independent Miller-Rabin compositeness tests will be prime. Unless specifically asked otherwise, Magma will use rigorous primality proofs.

## Primality

If a positive integer $n$ is composite, this can be shown quickly by exhibiting a *witness* to this fact. A witness for the compositeness of $n$ is an integer $1<a<n$ with the property that

$$
a^r\not\equiv1\bmod n\quad \hbox{and}\quad a^{r2^i}\not\equiv-1\bmod n\text{  for }i=0,1,\ldots, k-1
$$

where $r$ odd, and $k$ are such that $n-1=r\cdot 2^k$. A witness never falsely claims that $n$ is composite, because for prime $n$ it must hold that $a^{n-1}\equiv 1\bmod n$ and only $\pm1$ are square roots of $1$ modulo prime $n$. Moreover, it has been shown that a fraction of at least $3/4$ of all $a$ in the range $2\ldots n-1$ will witness the compositeness of $n$. Thus randomly choosing $a$ will usually quickly expose compositeness. Unless more than $1/4$ of all possibilities for $a$ are checked though (which in practice will be impossible for reasonable $n$) the procedure of checking $k$ bases $a$ at random for being a witness (often referred to as ‘Miller-Rabin’) will not suffice to prove the primality of $n$; it does however lend credibility to the claim that $n$ is most likely prime if among $k$ (say 20) random choices for $a$ no witness for compositeness has been found. In such cases $n$ is called *probably prime of order* $k$, and in some sense the probability that $n$ is composite is less than $4^{-k}$. A slight adaptation of this compositeness test can be used for primality proofs in a bounded range. There are no composites smaller than the Sorenson/Webster bound $B=3317044064679887385961981$ (approx $3.3\times 10^{24}$) for which a witness does not exist among $a=2,3,5,7,11,13,17,19,23,29,31,37$ ([[Sorenson and Webster, 2017](../../references.md#cite-sorenson2017strong)]). Using these values of $a$ for candidate witnesses it is certain that for any number $n$ less than $B$, the test will either find a witness or correctly declare $n$ prime. Since V2.29, Magma uses this test to prove primality (deterministically) of any prime $n<B$.

But even for large integers it is thus usually easy to identify composites without finding a factor; to be certain that a large probable prime is truly prime, a primality proving algorithm is invoked. Magma uses the ECPP (Elliptic Curve Primality Proving) method. Since V2.29, Magma uses a new implementation, that can handle 1000 digit numbers in a few minutes.

This ECPP method is both fast and rigorous, but for large integers (of say more than 100 decimal digits) it will be still be much slower than the Miller-Rabin compositeness test. The method is too involved to be explained here; we refer the reader to the literature ([[Atkin and Morain, 1993](../../references.md#cite-atkinmorain)], [[Franke *et al.*, 2004](../../references.md#cite-frankeetalt)]). The `IsPrime` function invokes ECPP, unless a Boolean flag is used to indicate that only ‘probable primality’ is required. The latter is equivalent to a call to `IsProbablePrime`.

### `IsPrime(n): RngIntElt -> BoolElt`

### `IsPrime(n: parameter): RngIntElt -> BoolElt`

```magma
Proof: BoolElt                    Default: true
```

Returns `true` iff the integer $n$ is prime. A rigorous deterministic method will be used, unless $n > B$, where $B=3317044064679887385961981$ (approx $3.3\times 10^{24}$), and optional parameter `Proof` is set to `Proof := false`, in which case the result indicates that $n$ is a probable prime (a strong pseudoprime to 20 bases).

### `SetVerbose("ECPP", v): MonStgElt, Elt`

Sets the verbose level for output when the ECPP algorithm is used in the above primality tests. The legal values are `true`, `false`, 0, 1 and 2 (`false` and `true` are the same as 0 and 1 respectively). Level 1 outputs only basic information about the times for the top-level stages (downrun and uprun). Level 2 outputs full information about every step : this level is very verbose!

### `PrimalityCertificate(n): RngIntElt -> SeqEnum`

### `CheckCertificate(cert): SeqEnum -> BoolElt`

```magma
Print: BoolElt                    Default: false
Full : BoolElt                    Default: true
```

`PrimalityCertificate` is a variant on `IsPrime` which uses ECPP and outputs a certificate of primality at the conclusion. If the number $n$ is actually proven to be composite or the test fails, then a runtime error occurs. The certificate is a `Magma` sequence of lists. Each list represents one step of the proof.

The first entry in each list $L$ indicates the method used. If the first enty is `E`, the elliptic curve `E := EllipticCurve(L[6])` is used. Its reduction modulo `n := L[2]` has the point $P$ with coordinates `L[7]`. The step assumes that `p := L[5]` is a prime. In this case $P$ has order $p$. As the prime `p` is sufficiently large, the primality of `n` follows. The next entry in the certificate will contain a proof that `p` is in fact prime. The elliptic curve was found via the CM approach with discriminant `L[3]` and the number of points on its reduction modulo `n` is given by `L[4]`.

If the first enty is `N-1`, the multiplicative group modulo `n := L[2]` has the element `g := L[4]`. The step assmes that `p := L[3]` is a prime. The `p`-th power of `g` is one modulo `n`. As the prime `p` is sufficiently large, the primality of `n` follows. The next entry in the certificate will contain a proof that `p` is in fact prime.

If the first enty is `Det`, `L[2]` is small enough to be covered by a deterministic Miller-Rabin test.

To confirm that a primality certiciate is correct, the function `CheckCertificate` can be used. It returns `true` if the certificate is corret and `false` otherwise. Setting `Print` to `true` displays the proof in a human readable format. Further, setting `full` to `true` results in an independet check of the result obtained by the deterministic Miller-Rabin test. A skeptical user is advised to check every certificate with this function, as it uses an independent implementation of elliptic curve arithmetic and also replaces the deterministic Miller-Rabin test with an independent test.

### `OldCertificate(cert): SeqEnum -> List`

The function `OldCertificate` converts the currenly used primality certificate and returns it in the format used by Magma V 2.28 and earlier. It can be used for an independet check of the certificate by a program that supports that format.

### `IsProbablePrime(n: parameter): RngIntElt -> BoolElt`

### `IsProbablyPrime(n: parameter): RngIntElt -> BoolElt`

```magma
Bases: RngIntElt                    Default: 20
```

Returns `true` if and only if the integer $n$ is a probable prime. More precisely, the function returns `true` if and only if either $n$ is prime for $n < 3317044064679887385961981$, or $n$ is a strong pseudoprime for 20 random bases $b$ with $1 < b < n$. By setting the optional parameter `Bases` to some value $B$, the number of random bases used is $B$ instead of $20$.

### `IsPrimePower(n): RngIntElt -> BoolElt, RngIntElt, RngIntElt`

Returns `true` if and only if the integer $n$ is a prime power; that is, if $n$ equals $p^k$ for some prime $p$ and exponent $k\geq 1$. If this is the case, the prime $p$ and the exponent $k$ are also returned, Note that the primality of $p$ is rigorously proven.

### `Example: Rep Units (ex-ca5938)`

This piece of code uses $5$ Miller-Rabin tests to find the next probable *repunit*-prime (consisting of all $1$’s as decimal digits), using the fact that primes of this form consist of a prime number of digits:

```magma
> NextPPRepunit := function(nn)
>    n := nn;
>    repeat
>       n := NextPrime(n);
>    until IsProbablePrime( (10^n-1) div 9 : Bases := 5);
>    return n;
> end function;

```

The first few cases are easy:

```magma
> NextPPRepunit(1);
2
> NextPPRepunit(2);
19
> NextPPRepunit(19);
23
> NextPPRepunit(23);
317

```

So we found a 317 digit prime (although we should check genuine primality, using `IsPrime`)! We leave it to the reader to find the next (it has more than $1000$ decimal digits).

## Other Functions Relating to Primes

The functions `NextPrime` and `PreviousPrime` can be used to find primes in the neighbourhood of a given integer. After sieving out only multiples of very small primes, the remaining integers are tested for primality in order. Again, a rigorous method is used unless the user flags that probable primes suffice. The `PrimeDivisors` function is different from all other functions in this section since it requires the factorization of its argument.

### `NextPrime(n): RngIntElt -> RngIntElt`

### `NextPrime(n: parameter): RngIntElt -> RngIntElt`

```magma
Proof: BoolElt                    Default: true
```

The least prime number greater than $n$, where $n$ is a non-negative integer. The primality is proved. The optional boolean parameter ‘Proof’ (`Proof := true` by default) can be set to `Proof := false`, to indicate that the next probable prime (of order $20$) may be returned.

### `PreviousPrime(n): RngIntElt -> RngIntElt`

### `PreviousPrime(n: parameter): RngIntElt -> RngIntElt`

```magma
Proof: BoolElt                    Default: true
```

The greatest prime number less than $n$, where $n\geq 3$ is an integer. The primality is proved. The optional boolean parameter ‘Proof’ (`Proof := true` by default) can be set to `Proof := false`, to indicate that the previous probable prime (of order $20$) may be returned.

### `PrimesUpTo(B): RngIntElt -> [RngIntElt]`

This function lists the primes up to (and including) the (positive) bound $B$. The algorithm is not super-optimised, but is reasonable. The limit on $B$ is $2^{30}-1$ for practical reasons, as otherwise the memory requirements can become too large with non-small integers (see below).

### `PrimesInInterval(b, e): RngIntElt, RngIntElt -> [RngIntElt]`

This function lists the primes in the interval from $b$ to $e$, including the endpoints. The algorithm is not very optimised. The interval must be smaller than $2^{30}$ in size, but if there are non-small integers ($>2^{30}$) involved then these will create a large memory overhead in any case. For instance, the `PrimesUpTo` intrinsic for $2^{30}-1$ returns 54400028 primes in 650 megabytes, while the `PrimesInInterval` intrinsic for $(2^{30}+1,2^{31}-1)$ takes over 5 gigabytes for its array of 50697537 primes.

### `NthPrime(n): RngIntElt -> RngIntElt`

Given a number $n$, this function returns the $n$th prime. This is implemented for primes up to $10^{10}$, or $n\le 455052511$.

### `RandomPrime(n: parameter): RngIntElt -> RngIntElt`

```magma
Proof: BoolElt                    Default: true
```

A random prime integer $m$ such that $0 < m < 2^n$, where $n$ is a small non-negative integer. The function always returns $0$ for $n=0$ or $n=1$. A rigorous method will be used to check primality, unless $m > 3317044064679887385961981$ and the optional parameter ‘Proof’ is set to `Proof := false`, in which case the result indicates that $m$ is a probable prime (of order 20).

### `RandomPrime(n, a, b, x: parameter): RngIntElt, RngIntElt, RngIntElt -> BoolElt, RngIntElt`

```magma
Proof: BoolElt                    Default: true
```

Tries up to $x$ iterations to find a random prime integer $m$ congruent to $a$ modulo $b$ such that $0 < m < 2^n$. Returns true, $m$ if found, or false if not found. $n$ must be larger than 0. $a$ must be between 0 and $b-1$ and $b$ must be larger than $0$. A rigorous method will be used to check primality, unless $m > 3317044064679887385961981$ and the optional parameter ‘Proof’ is set to `Proof := false`, in which case the result indicates that $m$ is a probable prime (of order 20).

### `PrimeBasis(n): RngIntElt -> [RngIntElt]`

### `PrimeDivisors(n): RngIntElt -> [RngIntElt]`

A sequence containing the distinct prime divisors of the positive integer $|n|$.