<p><em>Sorry for the haphazard title: really not sure what this should be called</em></p>

<p>Suppose we have a set of $z$ random values $S = r_1, \dots, r_z$ drawn from $\mathbb{Z}_N$ (where $N$ is some large prime).</p>

<p>Now, suppose we have $n+1$ variables $R_1, \dots, R_n, R_{n+1}$, such as for each $R_i$:
$R_i = r_{i_1} r_{i_2} \dots r_{i_k}$ where $r_{i_j}$ are $k$ randomly drawn values from $S$ with replacement$^*$.</p>

<p>We consider the problem of expressing $R_{n+1}$ as a quotient of $R_i$ ($i &lt; n+1$). That is, find $S_1$, $S_2$ such that:</p>

<p>$R_{n+1} = \frac{\prod_{i \in S_1}{R_i}}{\prod_{i \in S_2}{R_i}}$</p>

<p>(ideally, we are looking in $\mathbb{Z}_N$, but I doubt it makes a big difference, provided $N$ is large enough compared to the other parameters)</p>

<ol>
<li><p><strong>How "difficult" is this problem?</strong></p></li>
<li><p>(Assuming the previous answer to be: "not so easy" or worse) What about even deciding on the existence of a solution?</p></li>
<li><p>Does this problem (or something it can be trivially reduced to) have a formal name? [guess this should be my first question, huh]</p></li>
<li><p>Bonus question (depending on the above): Can any hypothesis be made about the uniqueness of $S_1$/$S_2$ elements (by default, it does not sound like elements should be unique in either collection) or the maximum size of either collection...</p></li>
</ol>

<p>My intuition is that there is no easy solution, but I cannot see a simple reduction to any NP-Hard problem that I can think of... (there's an obvious parallel set-theory problem, but I'm not sure I see an easier answer for it)</p>

<p>$^*$: or without replacement, if it makes a major difference to the questions/proofs...</p>

CC BY-SA 3.0
2015-01-23T01:04:09.680Z
Neglecting the possibility that any of the $r_i$ are zero, can you assume that the residues $r_i$ are generated by selecting some $a \in \mathbb Z_N^\times$, randomly generating $d_i \in {[0,N-1)}$, and assigning $r_i := a^{d_i} \pmod{N}$? Neglecting the possibility that $r_1 = 1$, could you go further and let $a = r_1$?
Niel de Beaudrap
CC BY-SA 3.0
2015-01-23T03:06:49.567Z
@NieldeBeaudrap: I think I understand your idea (reducing to an additive problem), but not sure I understand your formulation. Wouldn't it be rather: find an $a$ and $d_i$ **such that** $r_i = a^{d_i} \mod N$ and rewrite all $r_i$ that way? This *seems* doable assuming $N$ prime (but number theory is not my biggest strength). Not actually sure that the resulting problem has a non-exponential solution, though...
Dave
CC BY-SA 3.0
2015-01-23T04:11:00.760Z
@NieldeBeaudrap: I see. In that case, no: we cannot make any assumption about the generations of $r_i$. In fact, the framework I am working in is adversarial (security proof) and I'll be particularly happy if I can show that the above problem (which is a very generous relaxation of the original conditions) is intractable or (better yet) NP-complete. Original conditions involve actually *not even knowing* the $r_i$ (only the resulting $R_j$).
Dave
CC BY-SA 3.0
2015-02-08T18:50:06.640Z
Off-hand comment: It seems like a restriction of your problem is exactly a Subset Product instance. Consider only a (worst-case) list of numbers $R_1 ... R_n$ and a target number $T = R_{n+1}$. The question is, is there a subset $S$ of $\{R_1, ..., R_n\}$ whose product $\prod_{i\in S} R_i \stackrel{?}{=} T,$ which is NP-complete.
Daniel Apon
<np-hardness><nt.number-theory><exp-time-algorithms><set-theory>
Finding exact value with a quotients of products of random values
Dave
# Finding exact value with a quotients of products of random values

(Asked by: username_0 on 2015-01-22)

*Sorry for the haphazard title: really not sure what this should be called*

Suppose we have a set of $z$ random values $S = r\_1, \dots, r\_z$ drawn from $\mathbb{Z}\_N$ (where $N$ is some large prime).

Now, suppose we have $n+1$ variables $R\_1, \dots, R\_n, R\_{n+1}$, such as for each $R\_i$:
$R\_i = r\_{i\_1} r\_{i\_2} \dots r\_{i\_k}$ where $r\_{i\_j}$ are $k$ randomly drawn values from $S$ with replacement$^\*$.

We consider the problem of expressing $R\_{n+1}$ as a quotient of $R\_i$ ($i < n+1$). That is, find $S\_1$, $S\_2$ such that:

$R\_{n+1} = \frac{\prod\_{i \in S\_1}{R\_i}}{\prod\_{i \in S\_2}{R\_i}}$

(ideally, we are looking in $\mathbb{Z}\_N$, but I doubt it makes a big difference, provided $N$ is large enough compared to the other parameters)

1. **How "difficult" is this problem?**
2. (Assuming the previous answer to be: "not so easy" or worse) What about even deciding on the existence of a solution?
3. Does this problem (or something it can be trivially reduced to) have a formal name? [guess this should be my first question, huh]
4. Bonus question (depending on the above): Can any hypothesis be made about the uniqueness of $S\_1$/$S\_2$ elements (by default, it does not sound like elements should be unique in either collection) or the maximum size of either collection...

My intuition is that there is no easy solution, but I cannot see a simple reduction to any NP-Hard problem that I can think of... (there's an obvious parallel set-theory problem, but I'm not sure I see an easier answer for it)

$^\*$: or without replacement, if it makes a major difference to the questions/proofs...

**Tags:** np-hardness, nt.number-theory, exp-time-algorithms, set-theory

> **Comments:**
> **username_1**: Neglecting the possibility that any of the $r_i$ are zero, can you assume that the residues $r_i$ are generated by selecting some $a \in \mathbb Z_N^\times$, randomly generating $d_i \in {[0,N-1)}$, and assigning $r_i := a^{d_i} \pmod{N}$? Neglecting the possibility that $r_1 = 1$, could you go further and let $a = r_1$?  
> **username_0**: @NieldeBeaudrap: I think I understand your idea (reducing to an additive problem), but not sure I understand your formulation. Wouldn't it be rather: find an $a$ and $d_i$ **such that** $r_i = a^{d_i} \mod N$ and rewrite all $r_i$ that way? This *seems* doable assuming $N$ prime (but number theory is not my biggest strength). Not actually sure that the resulting problem has a non-exponential solution, though...  
> **username_0**: @NieldeBeaudrap: I see. In that case, no: we cannot make any assumption about the generations of $r_i$. In fact, the framework I am working in is adversarial (security proof) and I'll be particularly happy if I can show that the above problem (which is a very generous relaxation of the original conditions) is intractable or (better yet) NP-complete. Original conditions involve actually *not even knowing* the $r_i$ (only the resulting $R_j$).  
> **username_2**: Off-hand comment: It seems like a restriction of your problem is exactly a Subset Product instance. Consider only a (worst-case) list of numbers $R_1 ... R_n$ and a target number $T = R_{n+1}$. The question is, is there a subset $S$ of $\{R_1, ..., R_n\}$ whose product $\prod_{i\in S} R_i \stackrel{?}{=} T,$ which is NP-complete.  

---

## 0 answers

