Question about prime numbers

ramollari

The RSA encryption algorithm that makes use of public keys, is widely used in secure communications such as e-commerce. 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.

Gokul43201

The number of primes below a certain number (also known as the prime counting function ) has been known pretty accurately since the time of Gauss and Riemann (nearly 2 centuries ago). But knowing the number of primes is a long way off from actually factoring the number itself. In fact, typical key lengths are such that the number of primes to try with are astronomically large. I've heard that de Branges appears really close to a proof of the Riemann Hypothesis (a millenium problem, no ?), but that doesn't endanger RSA.

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.

shmoe

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.

davidmerritt

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

shmoe

Assuming it's false it would only be a matter of time before someone with a very long lifespan, several thousand truckloads worth of pencils and several forests worth of paper could prove it's false. The thing is, if it's false the first zero off the critical line could be so massively high that even if you could somehow muster all the computing power in the world it might not be able to find this counter example before the sun explodes.

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.

davidmerritt

I thought the Riemann hypothesis needed the zeros to be randomly distributed, so if the zeta project or something similar can make inferences about the distribution then wont the it be disproven?

shmoe

The Riemann Hypthesis only needs the non-trivial zeros to be on the critical line. The distribution I'm referring to is the spacings between heights of the zeros. It was conjectured that these spacings followed a certain distribution, one that was found to be identical to the spacings of eigenvalues of large, random, Hermitian matrices. The fact that large samples of zeros conform to the conjectured distribution adds evidence that "all is nice".