# pseudoprime test

(0.001 seconds)

## 1—10 of 27 matching pages

##### 1: 27.22 Software

Mathematica. PrimeQ combines strong pseudoprime tests for the bases 2 and 3 and a Lucas pseudoprime test. No known composite numbers pass these three tests, and Bleichenbacher (1996) has shown that this combination of tests proves primality for integers below ${10}^{16}$. Provable PrimeQ uses the Atkin–Goldwasser–Kilian–Morain Elliptic Curve Method to prove primality. FactorInteger tries Brent–Pollard rho, Pollard $p-1$, and then cfrac after trial division. See §27.19. ecm is available also, and the Multiple Polynomial Quadratic sieve is expected in a future release.

For additional Mathematica routines for factorization and primality testing, including several different pseudoprime tests, see Bressoud and Wagon (2000).

ECMNET Project. Links to software for elliptic curve methods of factorization and primality testing.

Number Theory Web. References and links to software for factorization and primality testing.

Wolfram’s Mathworld. Descriptions, references, and Mathematica algorithms for factorization and primality testing.

##### 2: 27.12 Asymptotic Formulas: Primes

*pseudoprime test*is a test that correctly identifies most composite numbers. …Descriptions and comparisons of pseudoprime tests are given in Bressoud and Wagon (2000, §§2.4, 4.2, and 8.2) and Crandall and Pomerance (2005, §§3.4–3.6). …

##### 3: 4.48 Software

###### §4.48(v) Testing

…##### 4: 27.18 Methods of Computation: Primes

*Mersenne numbers*, ${2}^{n}-1$, and

*Fermat numbers*, ${2}^{{2}^{n}}+1$. … ►The

*APR (Adleman–Pomerance–Rumely)*algorithm for primality testing is based on Jacobi sums. … ►The

*AKS (Agrawal–Kayal–Saxena)*algorithm is the first deterministic, polynomial-time, primality test. …

##### 5: 1.16 Distributions

###### §1.16(i) Test Functions

… ►A*test function*is an infinitely differentiable function of compact support. … ► ►The linear space of all test functions with the above definition of convergence is called

*a test function space*. … …

##### 6: 35.9 Applications

##### 7: David M. Bressoud

*Second Year Calculus from Celestial Mechanics to Special Relativity*, published by Springer-Verlag in 1992,

*A Radical Approach to Real Analysis*, published by the Mathematical Association of America in 1994, with a second edition in 2007, Proofs and Confirmations: The Story of the Alternating Sign Matrix Conjecture, published by the Mathematical Association of America and Cambridge University Press in 1999, A Course in Computational Number Theory (with S. …

##### 8: 1.1 Special Notation

$x,y$ | real variables. |
---|---|

… | |

$\varphi $ | a testing function. |

$\u27e8\mathrm{\Lambda},\varphi \u27e9$ | action of distribution $\mathrm{\Lambda}$ on test function $\varphi $. |

… |