Is there a unique factorization domain where computing the GCD of two elements is thought to be computationally intractable?
Here are some relevant results I've found:
- Wikström 2005 - For all rings of integers of number fields that are principal ideal domains$^1$:
[The algorithm] computes the greatest common divisor of its inputs in time $O(n^2)$ in the bit-size n of its input using naive arithmetic in $\mathbb{Z}$
- Phatak et al. 2014 - The authors attempt to construct a cryptosystem based on the existence of such a UFD. They remark (specifically for norm-Euclidean algorithms in rings of integers of quadratic fields, but the general point is similar):
As cryptologists, we now face several puzzles:
- That the norm-Euclidean GCD algorithm fails to exist might not rule out the existence of some other kind of efficient GCD algorithm. Indeed, Kaltofen and Rolletschek [33] construct a GCD algorithm in any quadratic number field (even ones with non-unique factorization), with running time bounded by a polynomial function of the number of bits describing the field-elements, provided D is fixed. But their running time grows proportionally to a power of D, i.e., exponentially in the number of bits in D. [...]
- It might be that only some quadratic fields yield security—in which case we want to know which ones, how common they are, how to find them quickly, and how to estimate their security levels.
1: The relevant Wikipedia page claims that the result applies to arbitrary UFDs, but this seems to be unfounded.