Consider a uniform random variable $n$ which is an integer in the interval $2^{1023} < n < 2^{1024}$. What is the oldest algorithm capable of determining whether or not $p$ is a probable prime and which could be executed in a reasonable amount of time in pen and paper by mathematicians of the day?

The oldest example I know of is Fermat's little theorem from 1640. Is there anything older?


According to this link for the paper "A Brief History of Factoring and Primality Testing B. C. (Before Computers)", Cataldi created a method for primality testing which was verified by Fermat. The following is an excerpt from the paper:

In particular, his work "Trattato del modo brevissimo di trovar la radice quadra delli numeri" published in 1613, represents a significant contribution to the development of continued fractions. His work on perfect numbers was also considerable. Among his thirty 20 MATH EMATICS MAGAZI N E VOL. 75, NO. 1, FEBRUARY2002 21 books, he wrote on military applications of algebra, and even published an edition of Euclid's Elements. Cataldi proved that the fifth, sixth, and seventh perfect numbers are:

Perfect Numbers

It is uncertain whether Cataldi was the first to discover these perfect numbers, but his are the first known proofs of these facts. Cataldi was also the first to observe that if 2n _ 1 is prime then n must be prime. In fact, the following result was known to Cataldi, though proved by Fermat.

Theorem 1

Long after Cataldi, Euler showed that every even perfect number has the form given in Theorem 1. It is unknown whether there are any odd perfect numbers and the search for them has exceeded the bound 10^300. Moreover, if such a beast exists, then it is known that it must have at least twenty-nine (not necessarily distinct) prime factors (see Guy [6, B l, p. 44]).

I hope this helps!

  • $\begingroup$ I'm afraid I'm missing something. Nowhere in this excerpt do I see any method for primality testing (the same is true for the section of the referenced book). $\endgroup$ – Erick Wong Mar 17 at 1:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.