Scott Fluhrer edited section_Abstract_This_paper_explores__.tex  almost 9 years ago

Commit id: 3ed7d7f72408dc3cca1a098a227336c517715ad2

deletions | additions      

       

In addition, we can reduce this work effort by taking advantage of the rotational symmetry of the multiply operation within $F[x]/x^N-1$; if we consider the product $AB$, and then consider the product $A'B$ (where $A'$ has the same coefficients as $A$, only rotated by $m$ positions, then the product $A'B$ will have the same coefficients as $AB$, only rotated by $m$ positions. This can easily be seen as the operation of rotating by $m$ positions is the operation of multiplying by the polynomial $x^m$, and $(x^mA)B = x^m(AB)$. This allows us to reduce the number of $F_3$ polynomials we consider by a factor of N (because if a specific value of $F_3$ gives a solution with small coefficients, so will any rotation of $F_3$ and the corresponding $F_1F_2$.  Ttere is also a second symmetry that we can take advantage of; if we rotate the elements of $F_1$ left by $m$ positions, and the elements of $F_2$ right by $m$ positions, the resulting product $F'_1 F'_2$ will be unchanged. That is, $(x^m F_1)(x^{-m}) F_2 = F_1 F_2$. This is a second symmetry that reduces the number of the products $F_1 F_2 F_2$  we need to consider by a factor of $N$. The result of these two improvements reduce the number of $G - F_3H$ values we need to precompute by a factor of $N$, and the number of $F_1 F_2$ polynomials that we need the Quantum Computer to search over by a factor of N.