Re: prime numbers?

From: Barry Margolin (barry.margolin_at_level3.com)
Date: 08/11/03

  • Next message: Niklas Poser: "Re: Which service to stop to prevent people from accessing my pc" 
    Date: Mon, 11 Aug 2003 15:35:28 GMT

    In article <20030809101117.22028.00000262@mb-m07.aol.com>,
    PCportinc <pcportinc@aol.combatSPAM> wrote:
    >> In fact, from what I know, the largest prime number has less
    >>than 1,000,000 digits.
    >
    >ok, but why is that important in cryptography and how are prime numbers used?

    Since your mathematical background is apparently pretty limited, I'm going
    to answer with a very brief, non-detailed answer. If you want more, there
    are lots of books on modern cryptography that explain everything.

    As far as we currently know, it's very hard to factor numbers that are the
    product of large primary numbers -- finding the primes and multiplying them
    can be done in a few seconds, but breaking the product back into its
    original prime factors can take weeks, months, or even years, depending on
    how large the primes were. A few hundred digits is currently sufficient,
    and the difficulty grows exponentially with the number of digits (so when
    computers get 10 times faster, we would only need to add 1 more digit to
    compensate).

    Most public-key encryption algorithms take advantage of this by using
    products of prime numbers to generate the public and private keys. If you
    know the public key, the only known way to figure out the private key
    (other than brute force trial and error) is to factor the product. 

    -- 
Barry Margolin, barry.margolin@level3.com
Level(3), Woburn, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
  • Next message: Niklas Poser: "Re: Which service to stop to prevent people from accessing my pc"