|
|
|
Revision difference : primality |
| Version 2 |
Version 1 |
|
A general dictionary would define {\em primality} as ``the quality or condition of being a prime number.'' In mathematics, it might be more useful to define primality as a Boolean-valued function that returns True if the input number is prime and False otherwise. Two examples: the primality of 47 is True; the primality of 42 is False.
|
A general dictionary would define {\em primality} as ``the quality or condition of being a prime number.'' In mathematics, it might be more useful to define primality as a Boolean-valued function that returns True if the input number is prime and False otherwise. Three examples: the primality of 47 is True; the primality of 42 is False; the primality of $1729 + 10i$ is True.
|
|
|
| It is not necessary to perform integer factorization to know the primality of a given integer, as there are various congruences and other relations which prime numbers satisfy but non-primes don't; these can serve as primality tests. The primality of certain large numbers, such as the thirtieth Fermat number, has been determined even though all we know of its least prime factor is that it is less than the square root of the composite Fermat number. Before the primality of a large number is ascertained, it might be considered a probable prime. 1 is the only integer to be declared non-prime without either a factor being discovered or it failing a primality test. |
With small numbers, it is practical to use integer factorization to determine primality; this is not the case for larger numbers with a large least prime factor. For larger numbers, such as most Mersenne numbers, there are special primality tests which in the case of a composite input return only False without giving any idea as to any of the factors. (The only number of questionable primality with unquestionable factorization is 1.) |
|
|
|
For practical purposes, primality testing might further have to be limited to answering whether a given number is a probable prime which could turn out to be a pseudoprime to a given base with further testing. In Mathematica, the primality function is \verb=PrimeQ[n]=, which uses the strong Miller-Rabin primality test, which is thought to be infallible even for large numbers which Mathematica would not be able to factor. |
|
|
|
|
