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.

  • $\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, 2015 at 15:30


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.