Re: Question from an intelligent (?) layman

[Al]
I understand that one element of cryptography is to publish a large
number that is the product of two primes.

Two /large/ primes, not teensy primes. That's key.

It is believed impossible to factor that number (call it N).

Factoring is always possible "in theory". The point is that it's believed
to be so expensive (require so much time and computer resources) to factor N
that potential adversaries can't afford to do it, or at least that it will
take them so long that you'll no longer care about keeping your secret by
then (for example, if you encrypt a day order to buy some stock, you
probably wouldn't care if a competitor could decrypt it given a month of
intense effort -- in fact, you might be delighted to see them wasting their
time ;-)).

But can't one make a table of products of pimes and just compare the
key with values in the table? For example take the primes 2, 3, 5,
and 7:

N Primes
--- ---------
6 2*3
10 2*5
14 2*7
15 3*5
21 3*7
35 5*7

Now if N =21, one goes to the table and reads off the answer (3*7).
Is this wrong or am I missing something? I will appreciate any
comments.

Think about the size of the table if the primes each have, say, 100 decimal
digits. There are about 4.3*10^97 primes of that size, and about the square
of that many products of two primes of that size: 1.8*10^195 products.
That's far, far, far more than the estimated number of electrons in the
universe. Some of those products are actually easy to factor with current
methods (for example, if the difference between p and q is small, it's very
easy to factor p*q quickly), but the ones believed to be "hard to factor"
make up an overwhelming majority.

In any case, there's "not enough stuff" in the entire universe to store a
table so large.


.

Relevant Pages

  • Re: [Full-Disclosure] Crypto and Primes
    ... My rough estimate says ... capable of generating random 512 bit primes at the rate of 100 trillion ... Age of the universe given as 18 billion years, which is rounded up to the ... >> hackmeister could do a crack on large prime based crypto, ...
    (Full-Disclosure)
  • Re: Problems With Public Key Cryptosystems
    ... |>>> until those used in RSA. ... |>>> for all those primes. ... |>> who can really say other than the NSA? ... |> universe contains approximately 1e90 hydrogen atoms. ...
    (sci.math)
  • Re: Problems With Public Key Cryptosystems
    ... |>>> until those used in RSA. ... |>>> for all those primes. ... |>> who can really say other than the NSA? ... |> universe contains approximately 1e90 hydrogen atoms. ...
    (sci.crypt)
  • Re: Problems With Public Key Cryptosystems based on "product of prime numbers"
    ... > There is no chance we will run out of primes. ... > number is more than the number of atoms in the universe? ... JLC ...
    (sci.crypt)
  • Re: I was right, surrogate factoring proof
    ... primes divide n -- at most I'll have to look through sqrt/ ... But don't forget that's included in the cost of the algorithm! ... if surrogate factoring ever becomes ... two values are congruent modulo p, and hopefully not congruent modulo n/p. ...
    (sci.math)