3 ms·
Does that include factoring large prime numbers? If a good approximation would exist for that, wouldn't that make public-key encryption pretty useless?
by voidpointer 16y ago
Does that include factoring large prime numbers? If a good approximation would exist for that, wouldn't that make public-key encryption pretty useless?
- amalcon 16y agoPublic-key encryption schemes would simply need to avoid reasonable circumstances. I suspect "product of two large primes" falls outside the "reasonable circumstances" for factoring.
- eru 16y agoIt's even harder than that. There are lots of known attacks, if you are not careful with your choice of prime numbers. (`Careful' is equal to `choosing pathological instances'.)
- jerf 16y agoIncluded in that handwave about probability distributions was a caveat about not being handed pathological instances of problems. Encryption harnesses pathological instances and wouldn't be covered by such a handwave. (Is there ever any other reason to generate multi-hundred digit numbers and try to factor them? Honest question, if anybody's got a fun answer, though I am asking about something actually useful that you know about, not something hypothetical.)
- eru 16y agoActually, it's quite hard to come up with good primes for RSA. They need to avoid lots of properties, because researches have found efficient attacks on numbers with those properties.
- eru 16y agoFactoring numbers is already suspected to be much easier than NP-complete. That is because factoring prime numbers is in the intersection between NP and co-NP. Co-NP is the set of problems where a "NO" answer is easily checkable with a certificate. If NP ?= co-NP is as much a question as P ?= NP. (I.e. no known proof either way, but every expects them to be unequal.)