A subexponential-time algorithm for computing discrete logarithms overGF(p^2)

An algorithm for computing discrete logarithms over GF <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">(p²)</tex> , where <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">p</tex> is a prime, in subexponential time is described. The algorithm is similar to the Merkle-Adleman algorithm for computing logarithms over GF <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">(p)</tex> , but it uses quadratic fields as the appropriate algebraic structure. It also makes use of the idea of a virtual spanning set due to Hellman and Reyneri for computing discrete logarithms over GF <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">(pᵐ)</tex> , for <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m</tex> growing and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">p</tex> fixed.