Hacker News new | ask | show | jobs
by nl 2839 days ago
No.

It's the non-factorability of primes that is important.

2 comments

> It’s the non-factorability of primes that is important.

Primes by definition have two, and only two factors.

The difficulty of factoring a number which is the product of two large primes is the important bit.

I think the usual abstract algebra definition is one factor: itself. 1 is not considered a factor so that prime factorizations are unique, otherwise you could tack on an infinity of ones.

Also Möbius becomes strange with infty factors.

The abstract algebra definition is that p is a prime if whenever p divides a product ab then p divides at least one of a and b.

Having no proper factors is the definition of an irreducible element.

The two definitions agree for the integers and nice algebraic structure (UFDs) but there are algebraic structures in which they are not the same which explains why there are two differenr definitions and names in abstract algebra

Pardon my extreme ignorance of the subject, but could you elaborate on why your statement is mutually exclusive of the OP? Not at all combative, just a sincerely interested layman :)
It doesn't matter to the algorithm that we know if it's a product of two primes. Anyone attacking an RSA private key knows that it is.

The only unknown is which two primes.

Which are easier to generate with a prime formula..
Define "easier" in this context. If you have an algorithm whose complexity increases exponentially with the key length, saying you made a 10% gain doesn't mean squat.
And it's wrong already. We already know all primes uses in encryption (just download a prime-number list).
This is wrong. We have lists of all primes used in crypto already. Just knowing them all doesn’t make attacks quicker.