Register to reply 
So you discovered Prime(n)? 
Share this thread: 
#1
Dec1712, 03:49 PM

P: 82

Let's say you discovered a discreet, simple formula that gave you the nth prime. Ok, but now being a web developer, I'm somewhat familiar with the use of large primes for online security. Now if you published this formula, wouldn't you be essentially responsible for compromising the better part of online security? (I could be wrong about primes forming the "better"part of online security, but they're certainly an important one nonetheless I think).



#2
Dec1712, 04:38 PM

P: 36

It's the duty of the other guy to pick safe passwords; it was their decision to place faith in prime numbers. If such a formula does exist and is found, I'm sure it will make for a great footnote in future math texts to show how "backwards" those guys from the 21st century were that they thought primes were safe.



#3
Dec1712, 05:40 PM

P: 82

I this case, the password you choose is unlikely to make much of a difference. From what I understand, knowing the nth prime could potentially allow a hacker sniffing online traffic to decrypt an otherwise secure and encrypted connection, one which, for example, was being used to send a user's password to the server when logging in.
I don't know, I doubt an algorithm responsible for securing much of if not all of internet communication could be deemed as "backwards" anytime soon. I guess we'll hope that such a nice simple formula doesn't exist :P 


#4
Dec1712, 05:56 PM

Admin
P: 23,397

So you discovered Prime(n)?
Coding/decoding  at least for RSA  is based not on knowing nth prime, but on factoring primes product. My understanding is that the cost of finding primes during factorization is negligible (but I can be wrong).



#5
Dec1712, 06:21 PM

P: 82

I'm somewhat familiar with how RSA works, and I'm not at all suggesting that knowing the nth prime will reveal a straight forward path to breaking RSA, but straightforward or not, it may well be its Achilles' heal. I'm no number theorist, but I'm sure that combining a knowledge of the nth prime with some numbertheoretic methods will allow you to quickly determine which primes might be factors of some arbitrarily large number.
The simplicity of the assumed function is meant to imply that if I can know the nth prime, then I should be able to solve for n and in turn solve for the index of an arbitrarily large prime number. The prime counting function, π(x), that tells you the (approximate?) number of primes less than a number x might play a role here as well. So, anyone find that there really isn't anything to worry about? 


#6
Dec1712, 06:30 PM

P: 82




#7
Dec1712, 07:09 PM

PF Gold
P: 469

Let's assume we have already calculated all 1024 bit primes so that Prime(n) runs in O(1) time.
Then what? 


#8
Dec1712, 07:28 PM

P: 82




#9
Dec1712, 08:13 PM

PF Gold
P: 469

2^1024 would only store all the prime numbers.
To perform a dictionary attack on a public key you would have to index the product of every pair of those prime numbers. 


#10
Dec1812, 12:34 AM

Sci Advisor
P: 1,132

In Computer Science, problems are grouped according to time complexity. Generally speaking, problems in the complexity class P are efficiently solved by today's computers, even for large instances (e.g. sorting a million numbers can be done in a few million operations). The problem of factorization is contained in the complexity class BQP and is only known to be efficiently solvable by Quantum Computers. Factoring large integers, of hundreds or thousands of digits, is not viable even in today's super computers, using the best known algorithms  this is not to say that it's impossible. Integer Factorization has not been proven to not be in P  it's actually an open problem in Computer Science. A related problem, Primality Testing, which asks whether a given number is a prime, is efficiently solvable  it was proven to be in P in 2002. The popularity of RSA based encryption is one reason why governments have a particular interest in Quantum Computers. 


#11
Dec1812, 03:12 AM

Sci Advisor
P: 1,132

However, there may well be a strategy by which a number may be factored in n^{c} operations for some constant c  it's an open question. An efficient factoring algorithm would be quite a significant achievement in the field of Computer Science (and quite possibly a national threat). It might interest you that there is another computational problem that is also not known to be efficiently solvable, Graph Isomorphism, which asks whether two graphs of n nodes are essentially the same graph. Graph Isomorphism and Integer Factorization sit in the same "unknown spot", between the complexity classes P and NPComplete, not known to belong to either one. These open questions in Computer Science are alot of fun to think about if you enjoy a good puzzle  why can't we determine whether two graphs are the same in n^{2} operations? 


#12
Dec1812, 05:21 AM

Sci Advisor
P: 2,470

At any rate, the process boils down to factorization problem, and knowing primes only speeds up the process by a factor of number of nonprime numbers you can skip. Since number of primes goes roughly as n/ln(n), a very simple formula for Nth prime only gives you an advantage of ln(n), which would still keep long keys completely safe. On another hand, having ability to get Nth prime would make it easier to generate RSA keys of significant length. Since computational intensity is the main limit on how long you want keys for particular application, odds are, discovering formula for Nth prime would actually make RSA more secure. 


Register to reply 
Related Discussions  
A prime number which equals prime numbers  General Math  10  
A prime generator I discovered  Linear & Abstract Algebra  3  
A formula of prime numbers for interval (q; (q+1)^2), where q is prime number.  Linear & Abstract Algebra  0  
Prime Numbers in the Diophantine equation q=(n^2+1)/p and p is Prime  Linear & Abstract Algebra  5  
7million digit prime number discovered  Linear & Abstract Algebra  11 