Factorization in coNP- in other domains?

I had on an exam in my grad complexity course to show that the following set is in coNP

FACT = { (n,m) : there is a factor y of n with 2 \le y \le m }

The answer I was looking for was to write FACTbar (the complement) as

FACTbar = { (n,m) | (\exists p_1,...,p_L) where L \le log n
for all i \le L we have m < p_i \le n and p_i is prime (the p_i are not necc distinct)
n =p_1 p_2 ... p_L
}
INTUITION: Find the unique factorization and note that the none of the primes are < m
To prove this work you seem to need to use the Unique Factorization theorem and you need
that PRIMES is in NP (the fact that its in P does not help).

A student who I will call Jesse (since that is his name) didn't think to complement the set  so instead he wrote the following CORRECT answer

FACT = { (n,m) | n is NOT PRIME and forall p_1,p_2,...,p_L  where 2\le L\le log n
for all i \le L,  m< p_i \le n-1 , (p_i prime but not necc distinct).
n \ne p_1 p_2 ... p_L
}
(I doubt this proof that FACT is in coNP is new.)
INTUITION: show that all possible ways to multiply together numbers larger than m do not yield n,
hence n must have a factor \le m.

Here is what strikes me- Jesse's proof does not seem to use Unique Factorization.  Hence it can be used in other domains(?). Even those that do not have Unique Factorization (e.g. Z[\sqrt{-5}]. Let D= Z[\alpha_1,...,\alpha_k] where the alpha_i are algebraic. If n\in D then let N(n) be the absolute value of the sum of the coefficients (we might want to use the product of n with all of its conjugates instead, but lets not for now).

FACT = { (n,m) : n\in D, m\in NATURALS, there is a factor y in D of n with 2 \le N(y) \le m}

Is this in NP? Not obvious (to me) --- how many such y's are there.

Is this the set we care about? That is, if we knew this set is in P would factoring be in P? Not obv (to me).

I suspect FACT is in NP, though perhaps with a diff definition of N( ). What about FACTbar?
I think Jesse's approach works there, though might need  diff bound then log L.

I am (CLEARLY) not an expert here and I suspect a lot of this is known, so my real point is
that a students diff answer then you had in mind can be inspiring. And in fact I am inspired to
read Factorization: Unique and Otherwise by Weintraub which is one of many books I've been
meaning to read for a while.