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

Abstract

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^{2})</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^{m})</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.

Keywords

AlgorithmLogarithmDiscrete logarithmPrime (order theory)Computer scienceDiscrete mathematicsMathematicsCombinatoricsPublic-key cryptography

Affiliated Institutions

Stanford University US

Related Publications

An improved algorithm for computing logarithms overGF(p)and its cryptographic significance (Corresp.)

S.C. Pohlig , Martin E. Hellman

A cryptographic system is described which is secure if and only if computing logarithms over <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1...

1978 IEEE Transactions on Information Theory 1179 citations

Fast evaluation of logarithms in fields of characteristic two

Don Coppersmith

A method for determining logarithms in GF <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">(2^{n})</tex> is presented. Its asymptot...

1984 IEEE Transactions on Information Theory 299 citations

On the minimum distance of some quadratic residue codes (Corresp.)

Don Coppersmith , G. Seroussi

We find the minimum distances of the binary <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">(113, 57)</tex> , and ternary <tex xml...

1984 IEEE Transactions on Information Theory 32 citations

Maximum distanceq-nary codes

R. C. Singleton

A <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">q</tex> -nary error-correcting code with <tex xmlns:mml="http://www.w3.org/1998/...

1964 IEEE Transactions on Information Theory 508 citations

Asymptotically optimal block quantization

A. Gersho

In 1948 W. R. Bennett used a companding model for nonuniform quantization and proposed the formula <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3...

1979 IEEE Transactions on Information Theory 868 citations

Publication Info

Year: 1985
Type: article
Volume: 31
Issue: 4
Pages: 473-481
Citations: 56
Access: Closed

External Links

View on DOI.org

Social Impact

Altmetric

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

PlumX Metrics

Social media, news, blog, policy document mentions

Citation Metrics

OpenAlex

Cite This

APA Style

                            
                                    Taher ElGamal
                                
                            (1985). 
                            A subexponential-time algorithm for computing discrete logarithms overGF(p^2). 
                            IEEE Transactions on Information Theory
                            , 31
                            (4)
                            , 473-481.
                            https://doi.org/10.1109/tit.1985.1057075

Identifiers

DOI: 10.1109/tit.1985.1057075