CRYPTOGRAPHY AND LOGARITHMS OVER FINITE FIELDS

The problem of computing discrete logarithms over finite fields is studied together with its applications to cryptography. The best known algorithm for computing discrete logarithms over GF(p) for p prime was developed independently by Merkle and Adleman. The algorithm has a subexponential but superpolynomial running time. A similar subexponential time algorithm is developed for the case GF(p('2)). The algorithm uses quadratic fields as the appropriate extention of the integers, and finds an isomorphism between GF(p('2)) and a certain subset of a quadratic field. Also, some ideas about extentions to higher order finite fields are given.; Because of its apparent one-way nature, the discrete logarithm problem is useful for finding cryptographic schemes. Diffie and Hellman developed a public key distribution scheme based on the discrete logarithm problem. A variation of this system is shown to implement a public key cryptosystem. Also, a new digital signature scheme based on discrete logarithms is presented.