Previous Page Next Page Contents

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:

Increasing Ecpp::maxit or Ecpp::maxh will make the algorithm more powerful, but slower.

Related Functions

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

Details

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

Changes




Do you have questions or comments?


Copyright © SciFace Software GmbH & Co. KG 2000