Using number fields to compute logarithms in finite fields

Abstract

We describe an adaptation of the number field sieve to the problem of computing logarithms in a finite field. We conjecture that the running time of the algorithm, when restricted to finite fields of an arbitrary but fixed degree, is <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper L Subscript q Baseline left-bracket 1 slash 3 semicolon left-parenthesis 64 slash 9 right-parenthesis Superscript 1 slash 3 Baseline plus o left-parenthesis 1 right-parenthesis right-bracket comma"> <mml:semantics> <mml:mrow> <mml:msub> <mml:mi>L</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>q</mml:mi> </mml:mrow> </mml:msub> <mml:mo stretchy="false">[</mml:mo> <mml:mn>1</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mn>3</mml:mn> <mml:mo>;</mml:mo> <mml:mo stretchy="false">(</mml:mo> <mml:mn>64</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mn>9</mml:mn> <mml:msup> <mml:mo stretchy="false">)</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>1</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mn>3</mml:mn> </mml:mrow> </mml:msup> <mml:mo>+</mml:mo> <mml:mi>o</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mn>1</mml:mn> <mml:mo stretchy="false">)</mml:mo> <mml:mo stretchy="false">]</mml:mo> <mml:mo>,</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">L_{q}[1/3; (64/9)^{1/3}+o(1)],</mml:annotation> </mml:semantics> </mml:math> </inline-formula> where <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="q"> <mml:semantics> <mml:mi>q</mml:mi> <mml:annotation encoding="application/x-tex">q</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is the cardinality of the field, <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper L Subscript q Baseline left-bracket s semicolon c right-bracket equals exp left-parenthesis c left-parenthesis log q right-parenthesis Superscript s Baseline left-parenthesis log log q right-parenthesis Superscript 1 minus s Baseline right-parenthesis comma"> <mml:semantics> <mml:mrow> <mml:msub> <mml:mi>L</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>q</mml:mi> </mml:mrow> </mml:msub> <mml:mo stretchy="false">[</mml:mo> <mml:mi>s</mml:mi> <mml:mo>;</mml:mo> <mml:mi>c</mml:mi> <mml:mo stretchy="false">]</mml:mo> <mml:mo>=</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>exp</mml:mi> </mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mi>c</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>log</mml:mi> <mml:mo> ⁡ </mml:mo> <mml:mi>q</mml:mi> <mml:msup> <mml:mo stretchy="false">)</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>s</mml:mi> </mml:mrow> </mml:msup> <mml:mo stretchy="false">(</mml:mo> <mml:mi>log</mml:mi> <mml:mo> ⁡ </mml:mo> <mml:mi>log</mml:mi> <mml:mo> ⁡ </mml:mo> <mml:mi>q</mml:mi> <mml:msup> <mml:mo stretchy="false">)</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>1</mml:mn> <mml:mo> − </mml:mo> <mml:mi>s</mml:mi> </mml:mrow> </mml:msup> <mml:mo stretchy="false">)</mml:mo> <mml:mo>,</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">L_{q}[s;c]={\exp }(c(\log q)^{s}(\log \log q)^{1-s}),</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and the <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="o left-parenthesis 1 right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>o</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mn>1</mml:mn> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">o(1)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is for <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="q right-arrow normal infinity"> <mml:semantics> <mml:mrow> <mml:mi>q</mml:mi> <mml:mo stretchy="false"> → </mml:mo> <mml:mi mathvariant="normal"> ∞ </mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">q\to \infty</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . The number field sieve factoring algorithm is conjectured to factor a number the size of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="q"> <mml:semantics> <mml:mi>q</mml:mi> <mml:annotation encoding="application/x-tex">q</mml:annotation> </mml:semantics> </mml:math> </inline-formula> in the same amount of time.