# 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>2$.

• By the way, with "ideal ring", do you mean "principal ideal ring"? Jul 22, 2016 at 10:08
• Sorry, was a typo, I meant just 'ring'. Btw, is $\mathbb{Z}[x]/(x^{2^k}+1)$ a principal ideal ring? Jul 22, 2016 at 10:23
• If "the group of units of $R$ is large" then deducing $a,b$ given $c$ is in fact information-theoretically impossible. ​ Did you mean to instead suppose that it's hard to find any non-trivial factorization of $c$ (not necessarily into the $a,b$ you started with)? ​ If yes, then "the group of units of $R$" being large doesn't help; consider fields. ​ ​ ​ ​
– user991
Jul 22, 2016 at 11:07
• Finding factorizations is easy, for instance $(a,b)=(u,cu^{-1})$ for any unit $u$. I mean I want to find the specific $a,b$ using the test function $T$. Could you please elaborate in why is it information theoretically impossible to recover $a,b$? Thanks and regards Jul 22, 2016 at 11:23
• That's why I said non-trivial factorization. ​ I'll elaborate on the impossibility tomorrow. ​ ​ ​ ​
– user991
Jul 22, 2016 at 11:43

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.