Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Question about prime numbers

  1. Nov 28, 2004 #1
    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.
     
  2. jcsd
  3. Nov 28, 2004 #2

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
     
  4. Nov 28, 2004 #3

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  5. Nov 28, 2004 #4
    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 :blushing:
     
  6. Nov 28, 2004 #5

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  7. Nov 29, 2004 #6
    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?
     
  8. Nov 29, 2004 #7

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    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".
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Question about prime numbers
  1. Question about primes (Replies: 11)

Loading...