Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I was just reading Is every positive nonprime number at equal distance between two prime numbers? (current hot topic) and was reflecting on the fact that computing security (cryptography) is based around the use of large prime numbers (see: Why are very large prime numbers important in cryptography?).

The answer for the above-mentioned question suggests that the Goldbach Conjecture says that every non-prime positive number is positioned equidistant between two prime numbers.

For the purposes of this question, I'll assume that statement is true (I have no prior knowledge of Goldbach or his/her conjecture).

If the Goldbach Conjecture is true, does it make it easier to find large prime numbers?

For example, I could take any very large number at random and then look at every number below it, find a prime and then work out of the opposite number is also a prime (or something along those lines). In my mind, it's almost as though the assumption would give me a starting point to find an even larger prime...

I expect I'm not the first person to ask this (and if I am, I've probably missed something somewhere..), but I can't find a similar question here :)

Thanks in advance

share|improve this question
2  
How is that going to be efficient? Given number $n$, you'd have to walk through the primes less than $n$, which, when $n$ is, say, $100$ digits, is going to be too many primes to check. And you are effectively skipping candidates, because Goldbach doesn't say that $n-k$ is prime if and only if $n+k$ is prime. –  Thomas Andrews Nov 16 '11 at 14:54

3 Answers 3

up vote 8 down vote accepted

Finding primes of the size wanted for cryptography isn't hard. The prime number theorem says that a "random" number $n$ has one chance in $\ln n$ of being prime. For a $1000$ bit number, this is about $1$ in $700$. If you only try numbers congruent to $1$ or $5 \pmod {6}$, you get another factor $3$, so you only have to try a few hundred before you find one. How to check is described here. The celebrated prime numbers that are found are much larger.

share|improve this answer
    
So in short "No" :) Thanks @rossmillikan –  LordScree Nov 17 '11 at 8:51

Technically it could, in some exceptionally unlikely scenario were you have a large even number $2n$, and you find that all $2n-p_i$ are all composite with small prime-factors except for one small $i$.

But seriously the only information you gain is that atleast one of $2n-p_i$ is prime, but heuristically this is to be expected 99.999% anyways so you gain really nothing except if above magic conspiracy took place.

share|improve this answer

Yes. $2n-p=q$, where $p<q$, and $q$ is the larger "flank" of $n$ as $n$ is midway between $p$ and $q$. You'd probably only have to test the 8 primes less than (but closest to) $p$ to find $q$.

Let's say those primes are called $a,b,c,d,e,f,g,h$. Then $q$ might be $2n-a$ or $2n-b$ or $2n-c$ or $2n-d$ or $2n-e \ldots$ you get the idea. Try it with primes you already know.

What if you thought 181 was the largest known prime. Look for 8 closest primes less than 181, and use $n=200$ (or any number $n$ that is at least 10% greater than your largest known prime). Find $2n-a$. Find $2n-b$. Find $2n-c$. And so on...

Did you have to go through all 8 to find a prime larger than 181?

share|improve this answer
2  
I didn't downvote; I just want to explain some problems with your answer. This doesn't show that Goldbach's conjecture helps us find large primes; you're just testing a handful of odd numbers larger than 181. If you randomly select large odd numbers to test, eventually you'll find a prime. There's no evidence choosing numbers of the form $2n-p$ speeds up this process. Also, the average number of random guesses required to find a prime increases as we search for larger primes (see the Prime Number Theorem). If you want 100- or 200-digit primes, you will usually need more than 8 guesses. –  Jonas Kibelbek Apr 18 '12 at 15:00

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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