Register to reply 
Question about prime numbers 
Share this thread: 
#1
Nov2804, 05:17 AM

P: 453

The RSA encryption algorithm that makes use of public keys, is widely used in secure communications such as ecommerce. It depends on the fact that you can multiply two very big prime numbers to get a product, but someone else cannot get back those prime numbers (factorize the product) directly. Why is this the case? There has been news that a French mathematician named De Branges has done an ingenious work in proving a theorem that we can count how many prime numbers are smaller than a given natural number. To him this implies that the job of factorizing the product of two big prime numbers becomes easy enough. If this were the case it would bring enormous consequences to contemporary security, encryption and confidentiality. It would freeze secure Internet transactions that depend on the RSA algorithm. I don't know to what extent the proof of De Branges will make the job of factorizing easier.



#2
Nov2804, 10:06 AM

Emeritus
Sci Advisor
PF Gold
P: 11,155

However, RSA is in fact, getting weaker as a result of newly discovered techniques such as Elliptic Factorization , which are themselves, quite complex techniques. Anyway, it'll be years before RSA falls, if at all. 


#3
Nov2804, 10:48 AM

Sci Advisor
HW Helper
P: 1,995

The announcement earlier this year of de Branges "proof" of the Riemann Hypothesis (RH) didn't appear to be anything new and doesn't actually work. Even if RH were to be proven today, RSA would not crumble. After all, the known algorithms based on it (or similar conjectures) for factoring and primality testing will work in practice if RH is true even if we can't prove it's true.
Factoring a number is *much* more work then determining if a number is prime (which is very much related in producing the two large primes needed for RSA). Type "RSA challenge number" into google and see what that's all about, it's a good example of how people are having trouble factoring products of two primes but were able to produce the two primes to multiply together relatively easily and on much older equipment. 


#4
Nov2804, 02:12 PM

P: 18

Question about prime numbers
Hmmm... I'm not a mathematican so please excuse my ignorance but would you consider the work of Gourdan in testing the Riemann hypothesis as important? I heard that his algorithm is 10,000 faster than what was being used at IBM's zeta project (read it in this weeks New Scientist). Surely with time and the resources at IBM its only a matter of time before the Riemann hypothesis is disproven.
David 


#5
Nov2804, 03:04 PM

Sci Advisor
HW Helper
P: 1,995

If the Riemann Hypothesis is true then all the searching for counter examples can go on for an eternity without yielding anything definitive. These sorts of computations relating to zeros are still fairly important and interesting though. They've given some evidence towards conjectures concering the distributions of the zeros. 


#6
Nov2904, 05:04 AM

P: 18




#7
Nov2904, 11:10 AM

Sci Advisor
HW Helper
P: 1,995




Register to reply 
Related Discussions  
A prime number which equals prime numbers  General Math  10  
Algebra question involving prime numbers  Precalculus Mathematics Homework  7  
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  
Prime Numbers From 2  General Math  10 