Is there an algorithm that can take an element on an arbitrary integral domain, and determine whether or not it is prime on that ring?

It is pretty trivial to do so on a finite integral domain, because no finite integral domains have primes (all elements are units). It is also pretty simple on the ring of polynomials of a finite ring where you can check all the polynomials of smaller order, however I am struggling to come up with an algorithm that works on all integral domains, let alone an efficient one.

  • $\begingroup$ How do you plan to represent elements of the integral domain? If it's finite, you can provide a complete list of the addition and multiplication tables for the underlying ring as input to the algorithm. If it's infinite, you can't do that. $\endgroup$ – D.W. May 11 '17 at 17:45
  • $\begingroup$ @D.W. I don't currently have any plans. I was hoping to first figure out a algorithm and then choose an implementation. Is the set of integral domains countable? I am particularly interested in the infinite case, because as both you and I pointed out this is rather easy to computer on a finite integral domain. If there are uncountably many integral domains, this problem is (probably) uncomputable in which case I will need to choose a subset of them. $\endgroup$ – Sriotchilism O'Zaic May 11 '17 at 17:51
  • $\begingroup$ I guess my point is that the problem doesn't seem well-specified yet. The first step of specifying an algorithmic problem is to specify the inputs and outputs, but here, it's not how to specify what the inputs would be. It's not clear to me what a generic algorithm that works for all integral domains would look like, since I can't even see what it's input-output API would look like. Hopefully someone else will have some ideas how to formulate the problem more concretely. $\endgroup$ – D.W. May 11 '17 at 18:19
  • $\begingroup$ @D.W. What do you mean by "it's not how to specify what the inputs would be." I assume this is a typo but I can't figure out what you intended to say. $\endgroup$ – Sriotchilism O'Zaic May 11 '17 at 18:26
  • $\begingroup$ @EpsilonNeighborhoodWatch It should probably have been "not clear how to specify". This isn't really a matter of "picking an implementation": without a representation of the input, one might easily produce an algorithm that cannot actually exist. For example, one can real numbers by just adding up the digits in the decimal expansion and keeping track of the carry in the usual way. But does that mean that there's an algorithm for addint uncomputable numbers? No, because there isn't any way of getting hold of the digits. $\endgroup$ – David Richerby May 11 '17 at 20:21

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.