Sorry for the haphazard title: really not sure what this should be calledSuppose 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)How difficult is this problem?(Assuming the previous answer to be: not so easy or worse) What about even deciding on the existence of a solution?Does this problem (or something it can be trivially reduced to) have a formal name? [guess this should be my first question, huh]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...
Finding exact value with a quotients of products of random values
np hardness;nt.number theory;exp time algorithms;set theory