2
$\begingroup$

Factorization of integers is hard, but finding irreducibles is expensive. Is there a ring where factorization is assumed hard but finding irreducibles is much cheaper than over $\Bbb Z$?

It could provide an alternative ring to do RSA/Rabin over.


A suggestion is the polynomial ring over $\Bbb Z_{pq}$ where $p$ and $q$ are prime. $\Bbb Z_{pq}$ has zero divisors, so I don't know what kind of creature you get. You still have to find $p$ and $q$ to start with, but still interesting.

Another suggestion is because polynomial factorization over finite fields is tractable, you could look for infinite fields, probably of nonzero characteristic.

$\endgroup$
  • $\begingroup$ Well, I guess, if such a ring would exist and have any computational advantage of RSA / Rabin, people would already have discovered it and have started using it... Still good question. $\endgroup$ – SEJPM Jul 7 '15 at 15:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.