| The discrete logarithm problem has been the basis of numerous cryptographic schemes. The security of those cryptosystems is based on the presumed intractability of the discrete logarithm problem in some group. The subject of this thesis is the discrete logarithm problem in the multiplicative group of finite fields and in the group of points of elliptic curves over finite fields.; The most successful algorithm for computing discrete logarithms in finite fields is the index calculus method. A significant parameter of the method is the factor base, which has invariably been chosen to contain all irreducible elements up to some size. Until now, this choice had not been questioned. We attempt a rigorous study of the behavior of the algorithm in the case that a different factor base is used. This leads us to generalize the notion of smoothness, and prove density theorems for those generalized smooth polynomials analogous to the existing once for smooth polynomials. Subsequently, we use them to analyze the index calculus method, that operates with a non-smooth factor base. The analysis shows that the more general version of the method has the same asymptotic running time, as the traditional version.; For the discrete logarithm problem on elliptic curves, our goal is to obtain a polynomial time reduction to the discrete logarithm problem in finite fields. A complete such reduction has been given by Frey and Ruck. Our reduction is a generalization of that of Menezes, Okamoto, and Vanstone.We present a generalization of the Weil pairing, that is parameterized by an isogeny y . Then we specialize the isogeny to 1 - &phis;, where &phis; is the Frobenius endomorphism, and use it to construct an isomorphism between the group of points of interest and a suitable group of roots of unity. For an elliptic curve E/Fq , and a point P in EFq of prime order r, our construction works for r|q - 1. Finally, we present an efficient algorithm for evaluating the pairing, which makes the isomorphism efficiently computable. Our contribution is a new, conceptually simpler construction, that is equivalent to the one by Frey and Ruck. The Frobenius endomorphism has been used in the past to speed up the arithmetic on elliptic curves, as well as to speed up Pollard's p method for computing discrete logarithms. |
