## `numlib::proveprime` -- primality proving using elliptic curves

#### Introduction

`numlib::proveprime``(n)` tests whether `n` is a prime.

Unlike `isprime`, `numlib::proveprime` always returns a correct answer.

#### Call(s)

`numlib::proveprime(n)`

#### Parameters

`n` | - | positive integer

#### Returns

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

#### Side Effects

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.

#### Related Functions

`ifactor`, `isprime`, `ithprime`, `nextprime`, `numlib::prevprime`

#### Details

- If `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).
- Each primality certificate produced by `numlib::proveprime` can be checked by the function `numlib::check`.
- Some information about the steps of the proof and checking can be obtained by using the function setuserinfo (see Example 3).

#### Example 1

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]]

#### Example 2

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

#### Example 3

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

#### Background

- This function implements the algorithm described in ``Elliptic curves and primality proving'', by A. O. Atkin and F. Morain, Mathematics of Computation, volume 61, number 203, 1993.

#### Changes

- no changes

Do you have questions or comments?
Copyright © SciFace Software GmbH & Co. KG 2000