Scott Fluhrer edited section_Abstract_This_paper_explores__.tex  almost 9 years ago

Commit id: ab06f9b9225690bc095dfaa05159c669c3c453d9

deletions | additions      

       

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.  When we consider the parameter set EES593EP1, we find it has $N = 593$, and $dF_1 = 10$, $dF_2 = 10$ and $dF_3 = 8$. This implies that the total number of $F_3$ polynomials is $\binom{593}{16}\binom{16}{8}$ (because each $F_3$ polynomial coefficients consists of 8 $p$s, 8 $-p$'s, and 577 $0$s), and the number of $F_1F_2$ polynomials as $\binom{593}{20}\binom{20}{10}\binom{593}{20}\binom{20}{10}$. This gives us $z = 40$, and so (when we take into account the factor of $N$ decrease (because of the rotational symmetry) and the factor of $3^{40}$ increase (because of the values of $G$ we need to consider), this gives us $3^40/N|F_3| $3^{40}/N|F_3|  \approx 2^{170.68}$. When we consider the number of $F_1 F_2$ polynomials, we get ; when we take account of the factor $N$ decrease (because of the second rotational symmetric), this gives us $1/N|F_1||F_2| \approx 2^{271.165}$. A Quantum Computer is able to search over a set of this size in approximately $2^{136}$ time, and for the first step would dominate. This search time is strictly smaller than the $2^{192}$ time that is the design strength of this parameter set. ...