text: # Is this problem based on discrete polynomials modulo $(x^3-1)$ strong?
  
  We start working with the Ring $$R=\left(\mathbb{Z}/p\mathbb{Z}\right)\left[x\right]/\left(x^{3}-1\right)$$, $$p$$ prime, i.e. degree two polynomials with coefficients modulo $$p$$ modulo $$x^{3}-1$$. As $$x^{3}-1=\left(x-1\right)\left(x^{2}+x+1\right)$$, we choose a subset of $$R$$, $$S\subset R$$, and a public value, $$z\in\mathbb{Z}/p\mathbb{Z},\ z\neq0$$, $$P\in S,\ P\equiv-z\left(mod\ x-1\right)$$.
  
  We can define the transpose operation of elements of $$S$$ as swaping the $$x$$ coefficient with the $$x^{2}$$one of the corresponding polynomial, so $$\left(ax^{2}+bx+c\right)^{T}=bx^{2}+ax+c$$.
  
  Now, we define a function $$f:S\times S\mapsto S$$, as $$f\left(A,B\right)=\left(xA^{T}+z\right)\left(xB^{T}+z\right)-zx$$. It's null element is $$-zx$$ and $$f$$ is a closed map of $$S$$, so $$A,B\in S,\ f\left(A,B\right)\in S$$.
  
  Next, we define a series as follows:
  
  $$A,B\in S,\ s_{0}=A,\ s_{1}=B,\ s_{n}=f\left(s_{n-2},s_{n-1}\right)$$
  
  And for a given element of the series,$$s_{n}$$, a value $$r_{n}=f\left(s_{n},A\right)$$
  
  ## The question is
  
  Taking into account that the function $$f$$ is not associative, how difficult is, knowing $$B$$ and $$r_{n}$$, recover the value of a secret $$A$$. As an example of sizes let's say $$n=256,\ p\sim2^{128}$$.
  
  This problem can lead to a cryptosystem described in this two documents:
  
  • I don't understand the downvote, take a look at the problem at least. Commented Nov 18, 2019 at 17:19
  • It might be helpful to list some basic approaches/attempts towards solving the problem, what you've tried so far, etc. The question currently reads like a "Here is a novel algorithm, cryptanalyze it for me" type of question, which are not on-topic or well received here. There are ways to make questions about novel algorithms and cryptanalysis on-topic, it involves breaking the question into smaller pieces and asking concisely answerable questions. Commented Nov 18, 2019 at 17:41
  • @daniel Could you please think of a better title? You also don't really ask a question. You state a problem, but that's not the same. Such errors do not harm the semantics of the question all that much, but they certainly harm the clarity of it. Commented Nov 18, 2019 at 18:36
  • Hmmmm, is $z=0$ forbidden because of a specific weakness? It is easy to show an efficient isomorphism between this "group" (ok, it's not a group, I can't think of a better term) with one specific $z$ value and another; hence if $z=0$ is a weak case, then any $z$ value is weak. Commented Nov 18, 2019 at 20:38
  • Thanks for the upvote. Answering @poncho, with $z=0$ the function becomes $f(A,B)=xA^T B^T$, after stepping the function you don't finish with an intractable formula but just with a simple equation like: $A^{e_1}(A^T)^{e_2}=C$, where $C$ is a constant known. This is easy to solve. So you can answer the isomorphism and I will admit the function is weak. Commented Nov 19, 2019 at 10:18
  
  Here's the isomorphism:
  
  $$ax^2 + bx + c$$ (with $$z$$) maps to $$ax^2 + (b + z - z')x + c$$ (with $$z'$$)
  
  The only nonobvious thing about this transform is that it preserves $$f$$, that is, that $$f(A, B)$$ (with $$z$$) is the element that maps to $$f'(A', B')$$ (with $$z'$$, and $$f', A', B'$$ are the mapped versions of $$f, A, B$$)
  
  However, this is not hard to show; we notice that the constraints $$ax^2 + bx + c = -z \pmod {x-1}$$ is equivalent to $$a + b + c = -z$$.
  
  With this in mind, if $$A = ax^2 - (a+b+z)x + b$$ (setting the linear term to the value it must be for it to be consistent with the constraint), and if $$B = cx^2 - (c+d+z)x + d$$, then $$f(A, B) = (bd -2ac – ad – bc)x^2 - (-ac+ad+bc+ad+z)x + (2ad+2bc+ac+bd)$$
  
  If we consider the mapped version of those two elements $$A' = ax^2 - (a+b+z')x + b$$ and $$B' = cx^2 - (c+d+z')x + d$$, then the mapped version of $$f'$$ would have $$f'(A, B) = (bd -2ac – ad – bc)x^2 - (-ac+ad+bc+ad+z')x + (2ad+2bc+ac+bd)$$
  
  We can see that the element $$f(A, B)$$ maps to the element $$f'(A', B')$$, hence the isomorphism is preserved.
  
  • This is the way, a mapping to a solvable function. I don't understand though what you do with the $-zx$ in the function. It seems to me that the isomorphism is for $f(A,B)=(xA^T+z)(xB^T+z)$, the function I propose is $f(A,B)=(xA^T+z)(xB^T+z)-zx$. Commented Nov 19, 2019 at 17:25
  • @daniel: actually, it was in there, but it was a bit subtle. I've revised my proof; take a look at it... Commented Nov 20, 2019 at 4:30
explanation: The document describes a mathematical problem involving polynomials in a specific ring and a function defined on a subset of this ring. The problem is framed in the context of cryptography, specifically the difficulty of recovering a secret value \( A \) given certain public values and a function \( f \). The document also includes a discussion and a solution to a related isomorphism problem.
  
  The document contains a question and an answer to this question.
distilabel_metadata.content: Evaluate the user given text extract and determine if it contains a math question and optionally and answer to this question.
  
  Output rules:
  
  1. Briefly describe the document and mention if it contains a question or a question and answer.
  2. Finalize the output with: Label: no-question,question,question-and-answer,multiple-question,multiple-question-and-answer
distilabel_metadata.role: system
distilabel_metadata.content: # Is this problem based on discrete polynomials modulo $(x^3-1)$ strong?
  
  We start working with the Ring $$R=\left(\mathbb{Z}/p\mathbb{Z}\right)\left[x\right]/\left(x^{3}-1\right)$$, $$p$$ prime, i.e. degree two polynomials with coefficients modulo $$p$$ modulo $$x^{3}-1$$. As $$x^{3}-1=\left(x-1\right)\left(x^{2}+x+1\right)$$, we choose a subset of $$R$$, $$S\subset R$$, and a public value, $$z\in\mathbb{Z}/p\mathbb{Z},\ z\neq0$$, $$P\in S,\ P\equiv-z\left(mod\ x-1\right)$$.
  
  We can define the transpose operation of elements of $$S$$ as swaping the $$x$$ coefficient with the $$x^{2}$$one of the corresponding polynomial, so $$\left(ax^{2}+bx+c\right)^{T}=bx^{2}+ax+c$$.
  
  Now, we define a function $$f:S\times S\mapsto S$$, as $$f\left(A,B\right)=\left(xA^{T}+z\right)\left(xB^{T}+z\right)-zx$$. It's null element is $$-zx$$ and $$f$$ is a closed map of $$S$$, so $$A,B\in S,\ f\left(A,B\right)\in S$$.
  
  Next, we define a series as follows:
  
  $$A,B\in S,\ s_{0}=A,\ s_{1}=B,\ s_{n}=f\left(s_{n-2},s_{n-1}\right)$$
  
  And for a given element of the series,$$s_{n}$$, a value $$r_{n}=f\left(s_{n},A\right)$$
  
  ## The question is
  
  Taking into account that the function $$f$$ is not associative, how difficult is, knowing $$B$$ and $$r_{n}$$, recover the value of a secret $$A$$. As an example of sizes let's say $$n=256,\ p\sim2^{128}$$.
  
  This problem can lead to a cryptosystem described in this two documents:
  
  • I don't understand the downvote, take a look at the problem at least. Commented Nov 18, 2019 at 17:19
  • It might be helpful to list some basic approaches/attempts towards solving the problem, what you've tried so far, etc. The question currently reads like a "Here is a novel algorithm, cryptanalyze it for me" type of question, which are not on-topic or well received here. There are ways to make questions about novel algorithms and cryptanalysis on-topic, it involves breaking the question into smaller pieces and asking concisely answerable questions. Commented Nov 18, 2019 at 17:41
  • @daniel Could you please think of a better title? You also don't really ask a question. You state a problem, but that's not the same. Such errors do not harm the semantics of the question all that much, but they certainly harm the clarity of it. Commented Nov 18, 2019 at 18:36
  • Hmmmm, is $z=0$ forbidden because of a specific weakness? It is easy to show an efficient isomorphism between this "group" (ok, it's not a group, I can't think of a better term) with one specific $z$ value and another; hence if $z=0$ is a weak case, then any $z$ value is weak. Commented Nov 18, 2019 at 20:38
  • Thanks for the upvote. Answering @poncho, with $z=0$ the function becomes $f(A,B)=xA^T B^T$, after stepping the function you don't finish with an intractable formula but just with a simple equation like: $A^{e_1}(A^T)^{e_2}=C$, where $C$ is a constant known. This is easy to solve. So you can answer the isomorphism and I will admit the function is weak. Commented Nov 19, 2019 at 10:18
  
  Here's the isomorphism:
  
  $$ax^2 + bx + c$$ (with $$z$$) maps to $$ax^2 + (b + z - z')x + c$$ (with $$z'$$)
  
  The only nonobvious thing about this transform is that it preserves $$f$$, that is, that $$f(A, B)$$ (with $$z$$) is the element that maps to $$f'(A', B')$$ (with $$z'$$, and $$f', A', B'$$ are the mapped versions of $$f, A, B$$)
  
  However, this is not hard to show; we notice that the constraints $$ax^2 + bx + c = -z \pmod {x-1}$$ is equivalent to $$a + b + c = -z$$.
  
  With this in mind, if $$A = ax^2 - (a+b+z)x + b$$ (setting the linear term to the value it must be for it to be consistent with the constraint), and if $$B = cx^2 - (c+d+z)x + d$$, then $$f(A, B) = (bd -2ac – ad – bc)x^2 - (-ac+ad+bc+ad+z)x + (2ad+2bc+ac+bd)$$
  
  If we consider the mapped version of those two elements $$A' = ax^2 - (a+b+z')x + b$$ and $$B' = cx^2 - (c+d+z')x + d$$, then the mapped version of $$f'$$ would have $$f'(A, B) = (bd -2ac – ad – bc)x^2 - (-ac+ad+bc+ad+z')x + (2ad+2bc+ac+bd)$$
  
  We can see that the element $$f(A, B)$$ maps to the element $$f'(A', B')$$, hence the isomorphism is preserved.
  
  • This is the way, a mapping to a solvable function. I don't understand though what you do with the $-zx$ in the function. It seems to me that the isomorphism is for $f(A,B)=(xA^T+z)(xB^T+z)$, the function I propose is $f(A,B)=(xA^T+z)(xB^T+z)-zx$. Commented Nov 19, 2019 at 17:25
  • @daniel: actually, it was in there, but it was a bit subtle. I've revised my proof; take a look at it... Commented Nov 20, 2019 at 4:30
distilabel_metadata.role: user
distilabel_metadata.raw_output_q_a_detector_0: The document describes a mathematical problem involving polynomials in a specific ring and a function defined on a subset of this ring. The problem is framed in the context of cryptography, specifically the difficulty of recovering a secret value \( A \) given certain public values and a function \( f \). The document also includes a discussion and a solution to a related isomorphism problem.
  
  The document contains a question and an answer to this question.
  
  Label: question-and-answer