🚀 go-pugleaf

In article <Bv6Izu.Aoq@newcastle.ac.uk> Graham.Shaw@newcastle.ac.uk (G.D.Shaw) writes:
>Factor this, and the resulting primes can be trivially combined together
>to yield the private key.  Once you know the private key, you can decrypt
>the message in the normal way.

May I ask an ignorant newbie question please?  It was my understanding that
the two primes used in most of these public key systems weren't real primes
at all, but were usually pseudo-primes that had been picked at random and
tested with statistical methods to give a high *probability* of being prime.

If that is the case, factoring a 500-bit product into two 250-bit primes may
well reduce to factoring it into 2 125-bit primes and a 250-bit prime, which
might well be *much* easier.

Am i mistaken?

Graham
PS I assume there's no point in buying a list of second-hand known prime
numbers because *anyone* could acquire the same list which would of
course be much smaller than the space of pseudo-primes.
--