probable prime


A sufficiently large odd integer q believed to be a prime numberMathworldPlanetmath because it has passed some preliminary primality test relative to a given base, or a pattern suggests it might be prime, but it has not yet been subjected to a conclusive primality test.

For primes with no specific form, it is required to test every potential prime factorMathworldPlanetmath p<q to be absolutely sure that q is in fact a prime. For Mersenne probable primesMathworldPlanetmath, the Lucas-Lehmer test is accepted as a conclusive primality test.

Once a probable prime is conclusively shown to be a prime, it of course loses the label ”probable.” It also loses it if conclusively shown to be composite, but in that case it might then be called a pseudoprimeMathworldPlanetmathPlanetmath (http://planetmath.org/PseudoprimeP) relative to base a.

Title probable prime
Canonical name ProbablePrime
Date of creation 2013-03-22 15:53:46
Last modified on 2013-03-22 15:53:46
Owner PrimeFan (13766)
Last modified by PrimeFan (13766)
Numerical id 5
Author PrimeFan (13766)
Entry type Definition
Classification msc 11A41