The solution to the problem has been tantalizingly close for many years. It requires no more theory than that developed two centuries ago, despite the heavy mathematical artillery that has been aimed at it in recent years. But first, some background to the problem.
Background
An intuitive way of testing whether a number is prime is to try to divide it by the numbers less than it. This can be made faster by dividing only those less than the square root of the number being tested, and even faster if you use only primes as divisors. So, for 2003, you need to try the first 13 primes to ensure you're dealing with a prime. Unfortunately, this method quickly runs out of steam once the numbers being tested get bigger. For instance, a 20-decimal digit prime needs about 1019 divisions to be proved so by this method. A 200-digit prime requires 1098 divisions.
Big primes are where these things find their most important current application, specifically in cryptography, although primes are involved in almost all areas of mathematical research. Public-key cryptography was first announced in 1976, and it was followed by a series of protocols and methods such as digital signatures, key distribution systems, and identification methods. For their security, all of these rely on difficult problems from the branch of mathematics known as "number theory," and all of them require prime numbers.
The Greek mathematician Euclid proved that there is an infinite number of primes. Then, nearly 1500 years later, Pierre de Fermat announced in 1640 a theorem known as his "little theorem," which states that if a number p is prime, then it divides all the numbers ap-1-1 whenever a is not divisible by p. At first sight, this appears to be a sure test for primes, but around the beginning of last century, R.D. Carmichael showed that there were numbers (since known as "Carmichael numbers") that pass Fermat's test and are composite.
One such composite is made up of 6k+1, 12k+1, and 18k+1, when all are primes. For example, 7x13x19=1729 is a Carmichael number, as is 37x73x109=294,409. In the 1990s, it was proven that there is an infinite number of Carmichael numbers.
Modifications of Fermat's theorem have been used for the best general-purpose prime testing algorithms. The method is to test a particular candidate with a number of a values, and if it passes for all of the a values, then there is a good chance that the number is prime. The Miller-Rabin Test (see "Riemann's Hypothesis and Tests for Primality," by G.L. Miller, Journal of Computer and System Sciences, Volume 13, 1978; and "Probabilistic Algorithm for Testing Primality," by M.O. Rabin, Journal of Number Theory, Volume 12, 1980) has until now been the fastest general-purpose method of finding primes. The odds that any particular a value will give a false reading — that is, indicate that a composite number is prime — are 1/4. So if the candidate passes n tests, then the chances of it being a composite are (1/4)n. Hence the more values of a that are used, the better the chance of producing a prime.
Once again, unfortunately for the Miller-Rabin Test, it has been proven that for any finite number of a values, there are composite numbers that pass all the tests (see "Primality Testing and Carmichael Numbers," by A. Granville, Notices of the American Mathematical Society, 1992). Because it is so efficient, the Miller-Rabin Test was used throughout the 1980s and early '90s in producing large cryptographic prime numbers. Despite the fact that a programming error is more likely than a false Miller-Rabin prime, a lingering doubt remains. Digital signatures are now used to seal important and valuable financial instruments, such as trusts and wills, far into the future. If some of the primes on which these signatures are based turn out to be phonies, the entire system is compromised.
There is a general-purpose method of proving a number is prime (see "On Distinguishing Prime Numbers From Composite Numbers," by L.M. Adleman, C. Pomerance, and R.S. Rumely, Annals of Mathematics, Volume 117, 1983), but it is much less efficient than Miller-Rabin and uses recondite entities from advanced number theory. A specialized method of finding provable primes was published in 1994 (see "Fast Generation of Prime Numbers and Secure Public-key Cryptographic Parameters," by U.E. Maurer, Journal of Cryptology, Volume 3, 1994), which is a little less efficient than a single pass of the Miller-Rabin Test. Maurer's method is the new de facto standard in the cryptography industry.
Maurer's method relies on predetermining some of the factors of p-1, where p is the test candidate for primality. It recursively builds up p from earlier passes that find factors of p-1. It gives prime numbers that are nearly randomly distributed; though this distribution is somewhat skewed by the use of a partially factored p-1. Being able to produce random prime numbers is important in cryptosystems such as LUC or RSA, as it is currently believed that these offer the best protection against factorization. Factorization of an LUC modulus breaks the cryptosystem, and is believed to be the only way of breaking the cipher.
There are other methods that produce provable primes, the most well known being the Lucas-Lehmer Test for Mersenne primes. These are primes of the form 2t-1, where t itself is also a prime, like 7(t=3), or 8191 (t=13), or the current world record, a Mersenne prime of over 4 million decimal digits, with t=13,466,917. This was found late last year in an ongoing collaborative effort over the Internet (http://www.mersenne.org/). Having forked out $100,000 for that Mersenne prime, the Electronic Freedom Foundation (http://www.eff.org/) is now offering an even larger cash prize for the first 10 million decimal-digit prime number.
The Mersenne-proving method was found by Edouard Lucas in the late 19th century, and it was proven to be correct by D.H. Lehmer early last century (see "An Extended Theory of Lucas' Functions," D.H. Lehmer, Annals of Mathematics, Volume 31, 1930; and "Théories des fonctions numeriques simplement périodiques," by F.E.A. Lucas, American Journal of Mathematics, Volume 1, 1878). Lehmer was able to generalize much of Lucas's work, and his theorem (see Example 1) can be seen as analogous to Fermat's "little theorem."
An important difference between the two is that Lehmer's Theorem uses number theoretic parameters called "quadratic residues" (QRs), and "quadratic non-residues" (QNRs). A number, b, is a quadratic residue of another number, c, if there exists yet a third number, d, such that d2-b is divisible by c. If no such number exists, then b is termed a quadratic nonresidue of c.
It has long been suspected that a combination of a Fermat and Lehmer Test produces numbers that are always prime, and small cash prizes are offered to people who can demonstrate a number that is simultaneously a Carmichael number and a constituent of the Fibonacci sequence (http://www.pseudoprime.com/).
Primality Proof and the CUL Algorithm
Rather than a Fermat and Lehmer Test, the method I present here uses two Lehmers: One for a base that appears to be a quadratic residue of the test number, and the other with a base that appears to be a quadratic nonresidue. The method can be proven to give prime numbers. And since it makes no demands on the form of the candidate (as the Maurer method does), the primes found are as random as the seeding process, which inaugurates the search for them. In terms of efficiency, it takes about 2 log p modular multiplications, making it equivalent to two passes of Miller-Rabin.
There is a number theory function known as the "Jacobi algorithm" (Example 2), which quickly lets you find such numbers. On average, one of every two numbers will be a quadratic residue of a candidate, and similarly for quadratic nonresidues. For instance, taking p=13, then 1, 3, 4, 9, 10, and 12 are quadratic residues of p; and 2, 5, 6, 7, 8, and 11 are quadratic nonresidues.
The proof applies Lehmer's Theorem (Example 1) in two cases, and uses the Lehmer totient function (Example 3). It relies on the mathematical proof method of contradiction. In other words, you assume that what you want to prove true is false, follow the implications of that assumption, and produce a contradiction of it.
The CUL algorithm proceeding from the proof (Example 4) is named for the aspect of "culling" prime numbers from among the composite numbers. In structure, it follows the proof. Example 5 is the Lucas V algorithm, a fast method of calculating the Lucas V functions. The Lucas U function can be calculated from the V function through use of the formula:
Uk2=(Vk2-4)/(P2-4)
Proof
Two Lucas function tests are sufficient to prove whether a number is prime. Let p be the number to be tested for primality, and p has passed both the lambda tests. We show in a proof by contradiction that p is prime.
Assume that p is not prime and has the composition outlined in the following: With respect to a number, 
, if the Jacobi (J) of with respect to p is -1, then p is composed of one or more primes such that is a Quadratic Nonresidue (QNR) of an odd number of them and is a Quadratic Residue (QR) of any number of them, whether an even or odd number or none.
When J=1, then p is composed of one or more primes such that is a QNR of an even number of them, and any number of primes such that is a QR of them, or p is such that is a QR of all the primes composing p.
The two lambda functions are: 
1=(p-1) and 2=(p+1). These follow from Lehmer's Theorem (Example 1), and are the two points at which the tests are made, with suitable P values such that P2-4Q=.
Specifically, these are whether U(P,Q)=0 mod p; and whether V(P,Q)=2 mod p for each of the lambdas, and U and V are the Lucas functions. The discriminant, =P2-4Q.
Let Q=1 to simplify the exposition. This does not affect the proof.
Choose 2 such that J=-1 for p; and then choose 1 such that J=1 for p. Clearly a different P value is required in each test. The first situation implies that there is at least one prime in the composition of p, such that 2 is a QNR of it. The second situation implies that there are either no primes in the composition of p, such that 1 is a QNR of them, or that there is an even number such that 1 is a QNR of them. It follows that in moving from the first to the second situation, that at least one prime in p has changed (from 2 being a QR of it to 1 being a QNR of it [Case 1], or vice versa i.e. from 2 being a QNR of p to 1 being a QR of p [Case 2]). We nominate this prime as r. The remainder of the primes in p, whether single or multiple powers of distinct primes (or both) are lumped together as 
. Thus p=r.
Case 1. Let L1=(r-1)S, the Lehmer totient of p, where S is the Lehmer totient of with respect to J=1, and r-1 is the Lehmer totient function with respect to r; and let L2=(r+1)T, where T is the Lehmer totient of with respect to J=-1, and r+1 is the Lehmer totient function with respect to r. The number p has passed both lambda tests, so p+1 is divisible by L2 by Lehmer's Theorem (Examples 1 and 2).
Say it goes in A times: p+1=AL2=A(r+1)T=ATr+AT, so p=ATr+AT-1. Repeating this process with respect to L1, which goes into p-1, say, B times, we get p=BSr-BS+1.
Comparing the coefficients of the two equations for p gives AT=BS for the coefficients of r; and -BS+1=AT-1 for the constant terms. From these we get 2BS=2, so BS=AT=1, which, when substituted back in the two equations for p, gives p=r.
Case 2. The second case is similar. Reusing the aforementioned variables, we end up with p=ATr-AT-1 and p=BSr+BS+1. Again comparing coefficients, AT=BS, -AT-1= BS+1, so AT=-1. Substituted in p=ATr-AT-1 and p=BSr+BS+1, we get a value of p, which is negative: p=-r. Both cases let us conclude that p is prime.
DDJ