Crate machine_prime

Source
Expand description

Machine-prime has 4 different variants. Lucas, Table, SSMR and Tiny. Implementation specifics is given below for each. First the algorithm is described then a general estimate of time complexity is provided. is_prime_wc never uses trial division. Time complexity is expressed as a ratio of 1 fermat test base-15 and taken as an average of the input candidates. is_prime’s time complexity is approximated from the computation time for the interval [2^64-10^8;2^64]. is_prime_wc’s time complexity is calculated from evaluating 2^64-59.

Additionally there is the Wide feature which extends the functions to 2^128. This is much slower than the previous algorithms and may pass composites.

Enabling the Internal feature, exposes the internal arithmetic for integration and reducing code duplication in other number theory software.

§Default/Table

Algorithm

  • Trial Division by first 67 primes
  • Base-2 strong fermat test
  • Look-up table of 262144 candidate bases for a strong fermat test

Properties

  • is_prime complexity: 0.163
  • is_prime_wc complexity: 2.0
  • Data Memory : 525072 bytes

§SSMR

Algorithm

  • Trial Division by first 67 primes
  • Base-2 strong fermat test
  • Look-up table of 262144 candidate bases for a strong fermat test
  • Branches for n < 2^47 to use a single strong fermat test

Properties

  • is_prime complexity: n < 2^47 0.154; n > 2^47 0.167
  • is_prime_wc complexity: n < 2^47 1; n > 2^47 2.0
  • Data Memory: 525072 bytes

§Lucas

Algorithm

  • Trial Division by first 67 primes
  • Base-2 strong fermat test
  • Lucas sequence test using a look-up table of parameters

Properties

  • is_prime complexity: 0.2
  • is_prime_wc complexity: 2.5
  • Data Memory: 811 bytes

§Tiny/No feature

Algorithm

  • Divison by 2
  • Base-2 strong fermat test
  • Lucas sequence test using parameters calculated over 2Z+1

Properties

  • is_prime complexity: 0.6
  • is_prime_wc complexity: 2.5
  • Data Memory: Negligible - no-std Binary compiles to 9.6 kb

§Wide

Algorithm

  • Division by first 67 primes
  • Base-2 strong test
  • Lucas sequence test

Branches to whatever algorithm is selected by other features for n < 2^64

Functions§

  • is_prime
    Primality testing optimized for the average case in the interval 0;2^64.
  • is_prime_wc
    Primality testing for the worst case.