Decomposing an ideal in intersections Let $R$ be an ring, and let $(a),(b)$ be the ideals generated by $a,b\in R$ respectively. Let $c=a\cdot b$ and $(c)$ the ideal generated by $c$.

I am supposing that, given $c$, it is computationally difficult to deduce $a,b$ (because the group of units of $R$ is large).
Suppose that we are given $c$ and we have a test function $T:R\to \{0,1\}$ that outputs 1 if the input is in $\{a,b\}$ and 0 otherwise.

Is it an algorithm to parameterize a list of ideals $I_1,I_2$ such that $(c)=I_1\cap I_2$? It looks to my that writing all such decompositions is essentially the same as listing all solutions $x,y$ such that $c=xy\in R$. Is that so?

I am interested in the particular case $R=\mathbb{Z}[x]/(x^{2^k}+1)$, and the coefficients of $a,b$ are bounded in magnitude by $B\in \mathbb{Z}_+, B&gt;2$.
For all units $u$, ​ $(a\hspace{-0.04 in}\cdot \hspace{-0.04 in}u)\hspace{-0.04 in}\cdot \hspace{-0.05 in}\left(u^{-1}\hspace{-0.06 in}\cdot \hspace{-0.04 in}b\hspace{-0.02 in}\right)$ ​ is a factorization of $c$, and ​ $a^{-1} \hspace{-0.06 in}\cdot \hspace{-0.04 in}(a\hspace{-0.04 in}\cdot \hspace{-0.04 in}u)$ ​ and ​ $\left(\hspace{-0.04 in}\left(\hspace{-0.02 in}u^{-1}\hspace{-0.06 in}\cdot \hspace{-0.04 in}b\hspace{-0.02 in}\right)\hspace{-0.06 in}\cdot \hspace{-0.04 in}b^{-1}\hspace{-0.04 in}\right)^{\hspace{.04 in}-1}$ ​ both give $u$, so [either factor and which side it is] is enough to deduce $u$.

Let "the modified factors" be ​ $a\hspace{-0.04 in}\cdot \hspace{-0.04 in}u$ ​ and ​ $u^{-1}\hspace{-0.06 in}\cdot \hspace{-0.04 in}b$ , ​ let N be the number of units,

and suppose the guesser makes at most q+1 guesses.

Game 0: ​ The guesser wins if and only if at least one of its guesses is $u$.

Game 1: ​ The guesser wins if and only if at least one of its

guesses is [either modified factor and the modified factor's side].

Game 2: ​ The guesser wins if and only if at least one

of its guesses is at least one of the modified factors.

Game 3: ​ The guesser may indicate at most one of its guesses as "final", but regardless,

it wins if and only if at least one its guesses is at least one of the modified factors.

Game 4: ​ ​ ​ The guesser may indicate at most one of its guesses as "final".

After each guess that is not indicated as final, the guesser is sent 0.

The guesser wins if and only if at least one of its guesses is at least one of the modified factors.

Game 5: ​ ​ ​ The guesser may indicate at most one of its guesses as "final".

After each [guess that's not indicated as final] which is not one of the modified factors,

the guesser is sent 0. ​ After each [guess that's not indicated as final]

which is one of the modified factors, the guesser is sent 1. ​ The guesser wins

if and only if at least one of its guesses is at least one of the modified factors.

Game 6: ​ ​ ​ The guesser may indicate at most one of its guesses as "final".

After each [guess that's not indicated as final] which is not one of the modified factors,

the guesser is sent 0. ​ After each [guess that's not indicated as final] which is

one of the modified factors, the guesser is sent 1. ​ The guesser wins if and only if

[it indicated a guess as final] and that guess was at least one of the modified factors.

Game 7: ​ ​ ​ The guesser may indicate at most one of its guesses as "final".

After each [guess that's not indicated as final] which is not one of the modified factors,

the guesser is sent 0. ​ After each [guess that's not indicated as final] which is

one of the modified factors, the guesser is sent 1. ​ The guesser wins if and only if

[it indicated a guess as final] and that guess was the modified factors.

Game 8: ​ ​ ​ The guesser may indicate at most one of its guesses as "final".

After each [guess that's not indicated as final] which is not one of $\{\hspace{-0.02 in}a,\hspace{-0.02 in}b\hspace{-0.02 in}\}$, the guesser is sent 0. ​ After each [guess that's not indicated as final] which is one of $\{\hspace{-0.02 in}a,\hspace{-0.02 in}b\hspace{-0.02 in}\}$, the guesser is sent 1.

The guesser wins if and only if [it indicated a guess as final] and that guess was $a,\hspace{-0.02 in}b$.

In Game 0, there are only q+1 guesses for N equally-likely possibilities,

so the probability of winning Game 0 is at most (q+1)/N.

As explained before, $u$ can be deduced from [either modified factor and the

modified factor's side], so for each Game-1 guesser, there's a Game-0 guesser with the

same winning probability. ​ Thus the probability of winning Game 1 is also at most (q+1)/N.

For each Game-2 guesser, there's a Game-1 guesser with half the winning probability (just guess the side at random), so the probability of winning Game 2 is at most twice the maximum probability of winning Game 1. ​ Thus the probability of winning Game 2 is at most (2*(q+1))/N.

For each Game-3 guesser, there's a Game-2 guesser with the same winning probability.

(Just ignore the presence or absence of a "final" indication.)

Thus the probability of winning Game 3 is at most (2*(q+1))/N.

For each Game-4 guesser, there's a Game-3 guesser with the same winning probability.

(Just send it 0 after each guess that's not indicated as final.)

Thus the probability of winning Game 4 is at most (2*(q+1))/N.

Game 4 and Game 5 only differ when a win is already guaranteed,

so the probability of winning Game 5 is at most (2*(q+1))/N.

The only difference between Game 6's winning conditions and Game 5's winning condition

is that the former's winning condition is a restriction of the latter's winning condition, so the probability of winning Game 5 is at most (2*(q+1))/N.

For each Game-7 guesser, there's a Game-6 guesser

with at least as large a winning probability.

(Just pick one part of its indicated-as-final guess).

Thus the probability of winning Game 7 is at most (2*(q+1))/N.

For each $u$, the equations $\;\;\; a\cdot u \: = \: c \;\;\;$ and $\;\;\; u^{-1} \cdot b \: = \: d \;\;\;$ both have a unique solution, so exactly N choices of $a,\hspace{-0.02 in}b,\hspace{-0.02 in}u$ yield modified factors $c,\hspace{-0.02 in}d$. $\;\;\;\;\;\;\;\;$ That means the

distribution of modified factors is uniform, so identical to the distribution of $a,\hspace{-0.02 in}b$. ​ Thus the probability of winning Game 8 is at most (2*(q+1))/N.

Finally, observe that Game 8 is exactly the game for guessing $a,\hspace{-0.02 in}b$ given $c$ and [at most q queries to the test function]. ​ Therefore, for all adversaries which make at most q oracle queries, their success probability is at most (2*(q+1))/N, where N is the number of units.



As mentioned by Chris Peikert,

Input: $R$

Output: ​ $R,\hspace{-0.02 in}R$

is "an algorithm to parameterize a list of ideals $I_1,I_2$ such that $(c)=I_1\cap I_2$".

That will be "the same as listing all solutions $x,y$

such that $c=xy\in R$" at least when $R$ is commutative.

(Finiteness might also be enough; I can't figure that out right now.)

However, there are rings in which $1$ can be factored into two non-units.