Prime number

tagga · #1 $Old$ 09-05-2008, 09:17 AM

Hi all

I have a quick question, is it true that a formula for prime number's has not yet been found?

I say this because me and a couple of friends have found a way to find a prime number, but not all of them as it misses a few and then finds one.

Like this: Say we only know of primes 2, 3, 5, 7 and wanted to know a prime with 2 digits, our way would work out number 19, ok it missed a few but its prime and it continues working so far. So technically this could be used to calculate the prime with 10 million digits (with a bigger computer without the 32-bit windows limit), ok it might not get the first prime with 10 million digits but maybe the 3rd or 4th.

And cant this be used in encryption keys etc...?

Has this been done before or new?

Edit: Also it doesnt envolve brute force.

Thanks.

Laurent · #2 $Old$ 09-05-2008, 09:33 AM

This would rather fit in the "number theory" section.

Anyway, a quick look at the Prime number page on Wikipedia gives:

Quote:

The Electronic Frontier Foundation (EFF) has offered a US$100,000 prize to the first discoverers of a prime with at least 10 million digits. They also offer $150,000 for 100 million digits, and $250,000 for 1 billion digits. In 2000 they paid out $50,000 for 1 million digits.

So I suppose a 10 million digit prime number is not an easy thing to find... If your idea can be efficiently implemented, it may interest quite a lot of people.

Moo · #3 $Old$ 09-05-2008, 09:43 AM

Hi !

Quote:

Originally Posted by tagga $View Post$

Hi all

I have a quick question, is it true that a formula for prime number's has not yet been found?

Yes it has not been yet. Nowadays, prime numbers seem to be randomly distributed, though there are some conjectures, theorems, properties...

Quote:

I say this because me and a couple of friends have found a way to find a prime number, but not all of them as it misses a few and then finds one.

Like this: Say we only know of primes 2, 3, 5, 7 and wanted to know a prime with 2 digits, our way would work out number 19, ok it missed a few but its prime and it continues working so far. So technically this could be used to calculate the prime with 10 million digits (with a bigger computer without the 32-bit windows limit), ok it might not get the first prime with 10 million digits but maybe the 3rd or 4th.

Yay ! Is it possible to see your method ? (curiosity, not envy

)

Quote:

And cant this be used in encryption keys etc...?

Do you know about the RSA encryption system ? They multiply 2 big prime numbers. But I've read that even with a 1000-digit numbers, finding its decomposition is difficult for a computer >.<
So 10^7, woah !

Quote:

Has this been done before or new?

Well, I'm sure you're not the only one who proposed a method for that

tagga · #4 $Old$ 09-05-2008, 09:43 AM

Yeah thats why I said 10 million digits.

It works so far... upto a size I can display on my PC screen but I cannot test large numbers such as these.

And my other concern is it misses out primes, which I thought might have already been done but not sure?

Also the way they work out primes at the moment is the Sieve of Atkin

Laurent · #5 $Old$ 09-05-2008, 10:25 AM

Quote:

Originally Posted by tagga $View Post$

Also the way they work out primes at the moment is the Sieve of Atkin

I doubt the methods to get extra large prime numbers rely on sieves. A sieve is aimed at finding every prime less than a given number. In the case of numbers larger than $10^{10^6}$ , it would be extremely impossible to keep them all in any kind of memory disk ever to be invented.

The usual methods depend on very specific properties of these large numbers, which usually are Mersenne numbers for instance (of the form $2^n-1$ , where $n$ in fact must be prime itself).

shawsend · #6 $Old$ 09-06-2008, 09:29 AM

Hi guys. Is not Riemann's formula $F(x)=\sum_{m\in\mathbb{N}} \frac{(-1)^{\mu}}{m} f(x^{1/m})$ a means of calculating a prime number? This formula calculates the number of primes less than or equal to $x$ . Thus one can then increment $x$ , and when $F(x)$ increments by one, then that value of $x$ must be prime.

Note this formula is not practical since the term $\mu$ involves the decomposition of $m$ into it's prime factors and one must also know the number of primes less than $\sqrt{m}$ .

Still though, it's a formula for calculating primes or no?

Laurent · #7 $Old$ 09-06-2008, 10:21 AM

There are various "formulas" for primes: cf. this page on the wikipedia for instance. However they're usually pretty inefficient for computation...