Pseudoprimes/Probable Primes

Pseudoprimes and Other Research

I now have a weblog devoted to updates on my research.

Recent Developments in Primality Testing

Here are slides of my talk on this subject. The talk is contained in two separate files.

Media Mentions

The Spring 1997 issue of CryptoBytes, a newsletter of RSA Labs, contains an article entitled "Fast Generation of Random, Strong RSA Primes" which refers to my work. Please note that the number "1770" should be changed to "7710".

There was a June 13, 1997 article in theChristian Science Monitor that mentioned my dissertation.

Frobenius Pseudoprimes

The proliferation of probable prime tests in recent years has produced a plethora of definitions with the word "pseudoprime" in them. I introduced the concept of Frobenius pseudoprimes in order to present a way of viewing many of these tests as special cases of a general principle, as well as to re-formulate them in the context of finite fields.

Frobenius Pseudoprimes

I am happy to be able to make available my first paper on Frobenius pseudoprimes. This will appear in Mathematics of Computation. Take your pick of formats.

Random Quadratic Frobenius Test

I also have made available my paper on the Random Quadratic Frobenius Test. It is an application of ideas in the first paper to produce a probable prime test that has an expected running time 3 times as long as that of the Strong Probable Prime Test, but is more than 3 times as accurate.

Infinitely Many Frobenius Pseudoprimes

This paper shows that for any reasonable polynomial, there are infinitely composites which pass a given Frobenius test. In particular, this answers a 1982 conjecture of Adams and Shanks.

The $620 Question

Please enjoy a list of primes that Red Alford and I have computed. I strongly believe that some sub-product of these primes is a Carmichael number and a Lucas pseudoprime for the Fibonacci sequence, and also is 2 or 3 mod 5. This would be worth $620, so if you can assist in any way, I can make it worth your while.

These computations are based on a heuristic given in 1984 by Carl Pomerance. The paper "appeared" in Dopo Le Parole aangeboden aan Dr. A. K. Lenstra, a privately published volume to honor Arjen Lenstra's receipt of his doctoral degree. Since this paper is not generally available, Carl gave me permission to scan it in and make it available on my web pages.

Carmichael Numbers

Alford, Andrew Granville, and Pomerance showed in a 1994 paper that there were infinitely many Carmichael numbers.

Granville has made this and related papers available on the web.

 Jon
Home
Links
Weblog
Archive
Math
Family
Tree
Gaming
E-mail