# Breaking the code - How to determine large and very large Primes?

A discussion on how to determine large and very large primes from the context of Number Theory.

## Sunday, January 24, 2010

### Breaking the code - How to determine large and very large Primes?

Issue:  How can we determine large and very large primes?

This question on how to determine large and very large primes are most likely asked by most mathematicians, mathematics enthusiasts and students. Even long long time ago, the search for large primes was a focus of study and research. Fortunately, the people in the "gone but not forgotten" era came up with theorems, algorithms and formulas in getting these primes to satisfy the need. Among the contributors were Euclid who developed the Euclidian algorithm, Father Mersenne with his famous Mersenne primes, Eratosthenes with his Sieves of Eratosthenes, Fermat with his Factorization Method and Little Theorem and others like, Gauss, Reimann and Euler who belong to the antique generation. Further studies were also been conducted by enthusiasts in the middle ages and they came up to determine large primes without the help of a computer and mostly, done with their bare hands. To name few of them, they are  Anton Felkel, J.P. Kulik, EDF Meissel, BK Parady, J.R. Smith and S. Zarantonello, they are the ones who used to publish tables of primes in large numbers as we say it. Most of their work were based on the theorems and correlations from the prototypes of antique generation.

So, what is the formula to determine exact large or very large primes? The answer is that based on the study, the accurate, exact and realistic method of determining large primes is by the use of Sieves of Erastosthenes. From the name itself you can think that numbers in a range are being sieved or "filtered" and that you can come up with real and exact primes. Here is an example of primes determined by the method in a range less than 100 or 10^2:

1,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97....

Of course, the only problem with this method is that this is very tedious when done by hands especially when expanding in the range to 10^3, 10^4, or 10^n, where: n may be any number greater than 2. However, with the advent of computers, large primes may be generated with the Sieve of Eratosthenes faster than any publishable table may be read (Anderson and Bell, 1997, p.116). This is done by writing a program usually in high level computer language like Turbo Pascal or Turbo C using syntax such as arrays and loops that would command the computer to generate large or very large primes to a certain range. (Note: I am sorry that I could not discuss the programming technique here but I could give the key points in making a flowchart for this program.)

The second question one might ask is: What is the use of other theorems or formulas made by Mersenne, Fermat or Gauss in determining large primes? The answer to that is - the theorems or formulas made by these mathematicians were simple assumptions or estimations to get large primes and may or may not be representing exact single large primes. Let us take the definition of Mersenne which states that a Mersenne number is an integer of the form M(n) = 2^n - 1. If a Mersenne number is prime, it is called a Mersenne prime or can be stated this way "If (M(n) is prime, then n is a prime." Let us therefore prove if this is absolute.

Proof:

n             2^n - 1  =  M(n)                            Remarks

1             2^1 - 1  =  1                                    Empty

2            2^2 - 1  =  3                                    2 is prime; M(n) = 3 prime

3            2^3 - 1  =  7                                    3 is prime; M(n) = 7 prime

4            2^4 - 1  =  15 = 3 x 5                     4 is not prime; M(n) = 15 composite

5            2^5 - 1  =  31                                  5 is prime; M(n) = 31 prime

6            2^6 - 1  =  63 = 3^2 x 7                6 is not prime; M(n) = 63 composite

7            2^7 - 1  =  127                                7 is prime; so M(n) = 127  prime

8            2^8 - 1  =  255 = 3 x 5 x 17          8 is not prime; M(n) = 255 composite

9            2^9 - 1  =  511 = 7 x 73                 9 is not prime; M(n) = 511 composite

10          2^10 - 1 = 1023 = 3 x 11 x 31    10 is not prime; M(n) =1023 composite

11          2^11 - 1 = 2047 = 23 x 89           11 is prime; M(n) = 2047 composite ?

As you can see in the table above, when n = 11; M(n) = 2047 = 23 x 89 which does not produce a single prime but rather composite. Therefore, we can deduce that Mersenne formula is good only for assumption for predicting primes but does not determine exact single large prime. The same thing also happens when we use Fermat number which is defined as a Fermat number is an integer of the form F(n) = 2^2n + 1. If a Fermat number is prime, it is called a prime. Unfortunately, the Fermat number, F(5) = 4294967297 is divisible by 641 and therefore, not a prime number and so Fermat number is also not absolute.

The third question one might ask is: Can we assume for a large prime number using the definitions or theorems made by antique mathematicians? My answer is yesWe could use the ancient formulas to predict or test a certain large number if its a prime or composite. The method is simple you just assume a large or very large number and test it for primality. This is done using the theorem that if the positive integer n is a composite integer, then n has a prime factor p such that p^2 < n.This is also similar with the suggestion made by Dr. Wilkinson in his conversation with Mr. Ulric Cajuste ([usepmat_group]primes,1/16/10). Let us take a proof on this: ex. determine whether  n = 521 is prime?

Proof:

We only need to consider primes p that are less than or equal to 2 for 22^2 = 484 which is less than 521 according to the theorem p^2 < n. If we are to use 23^2 = 529 this would be greater than 521 and therefore, does not conform to the theorem. Hence, we have to use 22. The primes less than 22 or equal to 22 are 2, 3, 5, 7, 11, 13, 17, and 19. Trying these primes to be divided to 521, we find that none of the primes divides 521. Therefore, we can say the 521 is a prime.

The only disadvantage with this method is that we just have to keep on guessing numbers until we find numbers to be prime.

Is there another formula aside from Sieves of Eratosthenes that could generate large primes? Yes, I have found one but this is subject yet to scrutiny. The equation looks like this:

P(n) = (2n + 1 - p) dN(n) + p = p (2n + 1 / p)^ dN(n)

where: N if N = 2n + 1 is prime

p if N = 2n + 1 is composite (p: arbitrary prime number)

This equation was formulated by Prof. S.M.R. Hashemi Moosavi who claimed that he solved the problem on prime number generation. To prove this formula would be for our next discussion.

What is the rationale behind why computer companies offer prices to those who can get larger primes? I believe that the rationale behind offering prices by computer companies is that 1.) as a sort of advertisement 2.) to test their product, say computer. I am convinced that the greater weight falls to the second reason since computer companies tend to test their hardware such as processors or chipsets if it can perform long and complex mathematical operations, including also is the speed and time to process instructions.

References:

James A. Anderson and James M Bell, Number Theory with Applications, 1997, Prentice Hall Publishing

Prof. S.M.R. Hashemi Moosavi, The Discovery of on-to generating function of the prime numbers and its results, www.primenumbersformula.com, Date accessed: January 17, 2010

Ultima_syd, [usepmat_group]primes, 1/16/2010