UserManual

prime

prime module provides functions of primarity tests.

The simplest way of primality test is to call primeq, which automatically calls appropriate function according to the given number.

If there is no need for rigorous proof, pseudoprime tests can be used. There are spsp (strong pseudoprime test), lpsp (Lucas pseudoprime test) and fpsp (Frobenius pseudoprime test). Miller-Rabin test is also provided as millerRabin.

Prime generation is another feature. The generator generator can generate unbounded sequence of primes. For smaller numbers less than a million, say, generator_eratosthenes can generate bounded sequence faster (using more memory). For more information about generators and iterators, please refer Python document. There are prime function to obtain n-th prime, nextPrime function to obtain the next bigger prime, etc.

Functions

apr(n)

apr is the main function for Adleman-Pomerance-Rumery primality test or the Jacobi sum test. Assuming n has no prime factors less than 32. Assuming n is spsp for several bases.

bigprimeq(z)

Giving up a rigorous proof of the primality of z, return True if z is a probable prime.

fpsp(n, a, b)

Frobenius test.
Return True if n is a Frobenius pseudoprime of parameters a, b, i.e. with respect to x**2-a*x+b.

generator()

Generate primes from 2 to infinity.

generator_eratosthenes(n)

Generate primes up to n using Eratosthenes sieve.

lpsp(n, a, b)

Lucas test.
Return True if n is a Lucas pseudoprime of parameters a, b, i.e. with respect to x**2-a*x+b.

millerRabin(n, times=20)

Miller-Rabin pseudo-primality test. Optional second argument times (default to 20) is the number of repetition. The error probability is at most 4**(-times).

nextPrime(n)

returns the smallest prime bigger than the given integer.

prime(s)

returns the s-th prime number.

primeq(n)

A convinient function for primatilty test. It uses one of trialDivision, smallSpsp or apr depending on the size of n.

primitive_root(p)

return a primitive root of the odd prime p. If p is not an odd prime, the returned value is nonsense.

properDivisors(n)

Return proper divisors of n (divisors of n excluding 1 and n).
It is only useful for a product of small primes.

randPrime(n)

returns a random n-digits prime

smallSpsp(n)

4 spsp tests are sufficient to determine whether an integer less than 10**12 is prime or not.

spsp(n, base, s=None, t=None)

Strong Pseudo-Prime test. Optional third and fourth argument s and t are the numbers such that n-1 = 2**s * t and t is odd.

trialDivision(n, bound=0)

Trial division primality test for an odd natural number. Optional second argument is a search bound of primes. If the bound is given and less than the sqaure root of n and 1 is returned, it only means there is no prime factor less than the bound.

Classes

These are the classes for Jacobi sum test.


Last-modified: 2006-06-13 (Ва) 14:29:57