2
$\begingroup$

Edited to clarify question

So my question is whether anyone knows of an efficient way to compute the neutral element (I'm gonna call it 1, but the operation doesn't have to be multiplication) in an abstract ring isomorphic to $\mathbb Z/ N\mathbb Z$? More specifically, the scenario is this:

Suppose we have a ring $ R = \mathbb Z/ N\mathbb Z$ (here, the operations are addition and multiplication) and a ring isomorphism $ f: (R,+,\cdot) \rightarrow (S, \triangle, *)$. However, we do not know what this bijection $f$ is. We also assume $N$ is very large, like an RSA-Modulus, and thus factorization is unknown. As has been pointed out, if $N$ is exponentially large, we can't just have a list of the elements, so we will assume that the elements are given through a black box that when invoked outputs an element of $S$, but does not tell us which element of $R$ it corresponds to. The elements of $S$ could, for example, be bitstrings.

D.W. has shown in his answer that if we only have oracle access to $\triangle$ and $*$, the neutral element regarding $*$ cannot be efficiently computed if $N$ can't be factored efficiently. So the question remaining is:

If the operations $\triangle$ and $*$ are explicitly given as a formula, can we always efficiently compute the inverse operation of $*$ and thus the neutral element?

Or are there cases when even having the formula instead of oracle access does not help us?

Here is a short example:

$R$ is $\mathbb Z/ 7\mathbb Z$ with regular modulo-addition and multiplication. $S$ is $\mathbb Z/ 7\mathbb Z$, $ x \triangle y := x + y - 4 \bmod 7, \ \ \ x * y := (x-4)(y-4) + 4 \bmod 7$.
So in the ring $S, \ e_\triangle = 4$ (we get this through solving $x \triangle e_\triangle = x \forall x \in S \Leftrightarrow x + e_\triangle - 4 = x \forall x \in S \Leftrightarrow e_\triangle - 4 = 0$, or more generally because we know that the order of the group regarding $\triangle$ is 7, i.e. we can take an arbitrary $x$ and compute $ x \triangle x \triangle x \dots \triangle x$ (7 times)).

But what about $e_*$? In this specific example, we can easily solve $x * e_* = x \forall x \in S$ to obtain $e_* = 5$, but we are only able to solve it because this is an easy example.

Thank you for your help :)

$\endgroup$
16
  • 1
    $\begingroup$ I don't think so - e.g. if $S = \mathbb Z/15\mathbb Z$, we have $|S| = 15$, i.e. $\varphi (|S|) = 8$. But, for example, $5^8 \bmod 15 = 10$. Euler's Theorem only holds for elements coprime to $|S|$, when $S = \mathbb Z/ n \mathbb Z$. As for the "coprime": I see your point. I really don't know how to answer this at the moment, but I will think about it. $\endgroup$
    – Angela
    Commented Jan 21, 2014 at 14:02
  • $\begingroup$ You are of course right about the need for several tries, my mistake, oups! $\endgroup$
    – fgrieu
    Commented Jan 21, 2014 at 14:27
  • 1
    $\begingroup$ Well, it really depends on your group structures, there is probably no standard way for arbitrary rings. For example, the multiplicative structure in general is not needed to be a group (only a monoid), and neither is it required to be abelian. Additionally, knowledge of the additive order of the group does not automatically help you with the multiplicative order: E.g. $\mathbb{Z}/16\mathbb{Z}$ has multiplicative order 8, while $\mathbb{F}_{2^4}$ has multiplicative order 15 (all elements except $0$ are invertible), while both have 16 elements in the additive structure $\endgroup$
    – tylo
    Commented Jan 21, 2014 at 14:42
  • $\begingroup$ I'm having a hard time understanding the question. What's given? What are you trying to compute? Am I given an integer $N$, and told that there is some ring $S$ that is isomorphic to the ring $\mathbb{Z}/N\mathbb{Z}$, but I'm given no other information about $S$, and my job is to find the image of $1$ in $S$? That is obviously not solvable. Did you mean to supply some additional side information? For instance, do you have some way of representing elements in $S$, and some black box that can perform addition, multiplication, inversion in $S$, and that can apply the isomorphism function? $\endgroup$
    – D.W.
    Commented Jan 21, 2014 at 23:24
  • 2
    $\begingroup$ anyway: In order to get a really useful answer, you might want to edit the topic to reflect your given situation more clearly. You asked for a general ring, and now it is isomorphic to $\mathbb{Z}/N\mathbb{Z}$ (your given example fulfilled this property, but not the original statement). Btw, if you are given the "formula" for $*$, you can just use standard algebra to calculate the neutral element, and you don't need the multiplicative group order at all. $\endgroup$
    – tylo
    Commented Jan 23, 2014 at 17:23

1 Answer 1

3
$\begingroup$

This is a spectacularly ambiguous, poorly-posed question, so I'm going to instantiate it in a way that I find interesting. If this wasn't the question you wanted answered, then edit your question to do a better job of asking a well-formed question.


$\newcommand{\tri}{\mathbin{\triangle}}$ I'm going to assume we are given an integer $N$ of unknown factorization, and we have a representation of elements of $\mathbb{Z}/N\mathbb{Z}$ as bit strings, via some representation function $[\cdot] : \mathbb{Z}/N\mathbb{Z} \to \{0,1\}^*$. Thus, $[x]$ is the representation of $x \in \mathbb{Z}/N\mathbb{Z}$. Define the operations $\triangle,*$ so that $[x+y] = [x] \tri [y]$ and $[xy] = [x] * [y]$. Or, in other words, define $\tri$ by $s \tri t = [\langle s \rangle + \langle t \rangle ]$ where $\langle \cdot \rangle : \{0,1\}^* \to \mathbb{Z}/N\mathbb{Z}$ is the inverse map of $[\cdot]$, and similarly for $*$.

(In terms of the original question, the bit strings play the role of the ring $S$.)

Suppose we are given the following abilities (and only these abilities):

  • We have a black box that, when invoked, will generate a random element $r$ in $\mathbb{Z}/N\mathbb{Z}$ and output $[r]$ (it won't tell us $r$, though).

  • We have a black box that, when given $s,t$ as inputs, will output $s \tri t$.

  • We have a black box that, when given $s,t$ as inputs, will output $s * t$.

The question becomes: can we compute $[1]$, a bit string that is the representation of $1 \in \mathbb{Z}/N\mathbb{Z}$? In other words, we're looking for a generic algorithm that will work correctly no matter what representation map $[\cdot ]$ happens to be chosen.


And the answer is: no, there is no efficient algorithm to compute $[1]$, given only these operations. This can be shown, using the same techniques used to show lower bounds in generic black-box groups, e.g., the same techniques used to show that there is no polynomial-time generic algorithm for the discrete log in a generic group.

How do we show it? I'll start by illustrating a proof, for the case where we are only allowed to invoke the first black box once: we can generate a single random value $[r]$, and then we can apply $\tri,*$ polynomially many times. Here's the proof. Let $x_0=r$, and let $x_i$ denote the $i$th element of $\mathbb{Z}/N\mathbb{Z}$ that we compute. For instance, if our algorithm takes $[r]$ and computes $s = [r]\tri [r]$ and then computes $t = s*[r]$ (say), we'll have $x_0=r$, $x_1=r+r$, $x_2=x_1x_0$. Say that the algorithm runs for $k$ steps. For the algorithm to be correct, we need it to output $[1]$, or in other words, we need to have $x_k=1$. Notice that each $x_i$ can be expressed as some polynomial of $x_0$, say, $x_i=p_i(x_0)$ (this can be proven by induction). So our algorithm corresponds to a polynomial $p_k(\cdot)$.

If the algorithm is correct, we must have $p_k(r)=1$ with high probability over the random choice of $r$. Is this possible? It turns out that this is not possible, if $k$ is not too large and if $N$ is hard to factor. In particular, if $\Pr_r[p_k(r)=1]$ is large, then we get an algorithm for factoring $N$ with $k$ steps and with a non-trivially large success probability. Here's why. Define the polynomial $q(\cdot)$ by $q(x)=p_k(x)-1$. By assumption, $\Pr_r[q(r)=0]$ is large, i.e., the polynomial $q(x)$ has many roots. On the other hand, it can't have too many roots: it has at most $k^2$ roots, by a simple application of the Chinese remainder theorem, so if $k$ is smaller than $\sqrt{N}$, $\Pr_r[q(r)=0]$ is large but strictly smaller than $1$. Now suppose $N=PQ$, and consider the polynomials $q(x) \bmod P$ and $q(x) \bmod Q$. Notice that

$$\Pr_r[q(r)=0] = \epsilon_P \times \epsilon_Q$$

where $\epsilon_P = \Pr_r[q(r)=0 \pmod P]$ and $\epsilon_Q = \Pr_r[q(r)=0 \pmod Q].$

Since the left-hand side ($\Pr[q(r)=0]$) is large, then both right-hand side terms ($\epsilon_P,\epsilon_Q$) must be large. In particular, $q$ has many roots modulo $P$ and many roots modulo $Q$. So, here is an efficient algorithm for factoring $N$. We pick $r$ randomly, compute $q(r)$, and then compute $\gcd(N,q(r))$. Notice that this outputs a non-trivial factor of $N$ with probability $\epsilon_P (1-\epsilon_Q) + \epsilon_Q (1-\epsilon_P)$. Since $\epsilon_P \times \epsilon_Q < 1$ but both $\epsilon_P,\epsilon_Q$ are large, it follows that $\epsilon_P (1-\epsilon_Q) + \epsilon_Q (1-\epsilon_P)$ is large, i.e., this algorithm for factoring $N$ has a large success probability.

So this is a reduction which shows that any efficient solution to this problem immediately yields an efficient algorithm for factoring. As a consequence, we should not expect any efficient solution to this problem (since we don't expect there to be any efficient algorithm for factoring). The reduction is tight, since I have shown in the comments that if you can factor $N$, then it is easy to solve this problem.

Technically, I only proved the result for algorithms that make just one call to the first black box (the one that generates a random value $[r]$). However, this proof technique can be extended to algorithms that make any feasible number of calls to the first black box, by looking at multivariate polynomials instead of univariate polynomials. These are basically the same techniques used to show that there is no generic algorithm for the discrete log (in generic/black-box groups) that runs faster than square-root time.

$\endgroup$
2
  • $\begingroup$ Thank you, that was very helpful. I have changed the question as you suggested - I'm sorry for doing such a poor job of asking it. The question changed/narrowed down along the way, but I should have rewritten it instead of just putting a note on the bottom. Again, I'm sorry. The only question that remains is what happens when we are not given black box access to $\triangle$ and $*$ but actual formulas - can we always invert these? Anyway, thank you a lot for your answer! $\endgroup$
    – Angela
    Commented Jan 29, 2014 at 9:08
  • $\begingroup$ @Angela, ahh, good question! Probably the answer will depend on the formulas or how they were generated; in some cases, yes, knowing the explicit formulas will allow you to invert them -- but not always. I don't know if it is possible to give a general answer. $\endgroup$
    – D.W.
    Commented Jan 29, 2014 at 16:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.