primality: Probabilistic Primality Tests for vli Objects

In VeryLargeIntegers: Store and Operate with Arbitrarily Large Integers

Probabilistic Primality Tests for vli Objects

Description

Functions to compute different probabilistic primality tests for vli (Very Large Integer) objects.

The function is.primeF computes the Fermat Primality Test.

The function is.primeMR computes the Miller-Rabin Primality Test.

The function is.primeSS computes the Solovay-Strassen Primality Test.

The function is.prime is a general function that computes the test specified in the test argument.

Usage

is.primeF(x, iter = 10)

## Default S3 method:
is.primeF(x, iter = 10)

## S3 method for class 'numeric'
is.primeF(x, iter = 10)

## S3 method for class 'vli'
is.primeF(x, iter = 10)

is.primeMR(x, iter = 10)

## Default S3 method:
is.primeMR(x, iter = 10)

## S3 method for class 'numeric'
is.primeMR(x, iter = 10)

## S3 method for class 'vli'
is.primeMR(x, iter = 10)

is.primeSS(x, iter = 10)

## Default S3 method:
is.primeSS(x, iter = 10)

## S3 method for class 'numeric'
is.primeSS(x, iter = 10)

## S3 method for class 'vli'
is.primeSS(x, iter = 10)

is.prime(x, iter = 10, test = "MR")

Arguments

x	number to be tested; object of class vli or 32 bits integer
iter	number of iterations; numeric
test	chosen test: "F" for the Fermat Test, "SS" for the Solovay-Strassen Test or "MR" (by default) for the Miller-Rabin Test; character

Details

Probabilistic primality tests are algorithms that determine if an integer is prime or composite. They are not deterministic tests so there is a probability of error (it is never reported a prime number as composite, but it is possible for a composite number to be reported as prime). This probability of error can be calculated and reduced as much as we want by increasing the number of iterations of the test.

Each test is different, therefore they have different computational efficiency and one could be better than other for testing some numbers. However, the Miller-Rabin test is the most accurated of all three and, because of that, it is the test chosen by default in every function that needs primality testing in the present package.

The Fermat Primality Test detects composite numbers by using the Fermat's Little Theorem, which says that, if p is prime, for any integer a satisfaying gcd(a, p) = 1 we have that a^(p-1) = 1 (mod p). Each iteration randomly pick an integer a. The more iterations are computed, the greater probability to find an a that does not verify such conditions and, therefore, it reveals that p is composite. However, there are some composite numbers p that have the property that a^(p-1) = 1 (mod p) for every a coprime to p. These numbers are called Carmichael numbers or Fermat pseudoprimes, and it is not possible for the Fermat Test to detect that they are composite numbers. But there are only 105212 such numbers up to 10^15 (approximately 1 Carmichael number per each 10.000.000.000 integer numbers). The first five are: 561, 1105, 1729, 2465 and 2821.

As a conclusion, we can say that if the chosen x number is prime, the Fermat test returns TRUE. If it is an odd composite (but not a Carmichael number), it returns FALSE with probability at least 1/2^k, where k is the number of computed iterations.

The Miller-Rabin Primality Test is a more sophisticated version of the Fermat test. If the chosen x number is prime, the test returns TRUE. If x is an odd composite the algorithm returns TRUE (that is, it fails) with probability less than 1/4^k, where k is the number of computed iterations. In cases of very big numbers, the probability is even smaller.

The Solovay-Strassen test is based in a known algebraic property of the Jacobi symbol. The probabily of failure is also less than 1/2^k, where k is the number of computed iterations. However, unlike it happens with the Fermat test, there are not odd composite numbers that can not be detected with enough iterations of the Solovay-Strassen test.

Value

boolean: if the test determines that the given number is prime it returns TRUE if the test determines that the given number is composite it returns FALSE

Author(s)

Javier Leiva Cuadrado

Examples

## Not run: 
## Testing a 32 bits integer using the Miller-Rabin Test
is.primeMR(2845127, iter = 10)

## Testing an object of class vli using the Fermat Test
x <- as.vli("2801401243675128975602569907852141")
is.primeF(x, iter = 100)

## Testing the same object of class vli using the general
##     is.prime function and the Solovay-Strassen Test
is.prime(x, iter = 100, test = "SS")

## End(Not run)

VeryLargeIntegers documentation built on May 31, 2023, 7:06 p.m.