## [geocentrism] Re: calculating primes

• To: <geocentrism@xxxxxxxxxxxxx>
• Date: Wed, 5 Sep 2007 09:27:35 +1000

```curiosity got me!  I know I'm biased, but is mathmatics a game, or is the
following indicative of doing anything useful?

Can it help make a machine?  McCanny claimed it could be used to decode
cyphers..  what does that accomplish or do?  He inferred this meant breaking in
(hacking) any computer was easy.

Mystified..

Phil.

Calculating Prime Numbers
We now consider the question of how to find prime numbers. The prime number
theorem shows that if we pick an integer n at random, it will be prime with
probability  . So even if n  2512, our random n is prime with probability
0.0028. This is perfectly reasonable; in principle then we can find primes
quickly.
So the important question is how easy is it to tell if a number n is prime. It
is certainly infeasible to check the primality of n directly from the
definition. We've seen an elementary method of finding primes, namely the prime
sieve, in Section 4.5, and we will make use of it shortly, but this method
would also take infeasibly long and use an infeasible amount of storage.
However, using our sieve to generate a list of small primes, we can quickly
decide that many such prime candidates n are composite. We simply check in turn
whether each small prime is a factor of n. And any prime candidate which is
accepted by such a filter is fairly likely to be prime.11.5

Note the result of such a test on a prime candidate n: either

a.. we demonstrate that n is composite; or
b.. it remains unknown whether or not n is prime.
We will call this a one-sided test for primality. We are about to meet more
such tests. Recall Fermat's Little Theorem (11.6). If n is prime, and we choose
any a with 1 < a < n - 1 then an-1  1(mod n). Conversely, if we ever find such
an a for which an-1 1(mod n), we have demonstrated that n is composite.
We call a number n which passes this ``Fermat's Little Theorem (FLT)'' test for
a given base a, but which is not actually a prime, a pseudoprime with respect
to the base a. Such pseudoprimes are very rare; very much rarer than primes
themselves. Of course we can apply the FLT test again using a different a; each
such test passed successfully increase our confidence that n is prime. However
there are numbers, called Carmichael numbers which are composite, but which
satisfy the FLT test for every base a.11.6 Indeed fairly recently it has been
confirmed that there are an infinite number of Carmichael numbers.

```