# Are there UFDs where the factorization problem is difficult but finding irreducibles is cheap?

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.

• 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. – SEJPM Jul 7 '15 at 15:30