IntegerPrimesPackage IΒΆ

intfact.spad line 1 [edit on github]

The IntegerPrimesPackage implements a modification of Rabin's probabilistic primality test and the utility functions nextPrime, prevPrime and primes.

nextPrime: I -> I

nextPrime(n) returns the smallest prime strictly larger than n

prevPrime: I -> I

prevPrime(n) returns the largest prime strictly smaller than n

prime?: I -> Boolean

prime?(n) returns true if n is prime and false if not. Note that we ignore sign of n, so -5 is considered prime. The algorithm used is Rabin's probabilistic primality test (reference: Knuth Volume 2 Semi Numerical Algorithms). If prime? n returns false, n is proven composite. If prime? n returns true, prime? may be in error however, the probability of error is very low. and is zero below 25*10^9 (due to a result of Pomerance et al), below 10^12 and 10^13 due to results of Pinch, and below 341550071728321 due to a result of Jaeschke. Specifically, this implementation does at least 10 pseudo prime tests and so the probability of error is < 4^(-10). The running time of this method is cubic in the length of the input n, that is O( (log n)^3 ), for n<10^20. beyond that, the algorithm is quartic, O( (log n)^4 ). Two improvements due to Davenport have been incorporated which catches some trivial strong pseudo-primes, such as [Jaeschke, 1991] 1377161253229053 * 413148375987157, which the original algorithm regards as prime

primes: (I, I) -> List I

primes(a, b) returns a list of all primes p with a <= p <= b