this is for holding javascript data
Scott Fluhrer edited section_Abstract_This_paper_explores__.tex
almost 9 years ago
Commit id: c2cb28604146c33083b2033098d247e3d02525c8
deletions | additions
diff --git a/section_Abstract_This_paper_explores__.tex b/section_Abstract_This_paper_explores__.tex
index dac2a61..e1c8603 100644
--- a/section_Abstract_This_paper_explores__.tex
+++ b/section_Abstract_This_paper_explores__.tex
...
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); when $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), symmetry) and the factor of $3^{43}$ increase (because of the values of $G$ we need to consider), this gives us
$1/N|F_3| $3^40/N|F_3| \approx
2^{107.285}$. 2^{170.68}$. When we consider the number of $F_1 F_2$ polynomials, we get
$\binom{593}{20}\binom{20}{10}\binom{593}{20}\binom{20}{10}$; ; 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$. 2^{271.165}$. A Quantum Computer is able to search over a set of this size in approximately $2^{136}$ time, and
this second 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.
...