for some fixed and two integers with a low weight representation. We call this class of exponents split exponents, and we show that with certain choice of parameters the DL problem on split exponents is essentially as secure as the standard DL problem, while the exponentiation operation using exponents of this class is significantly faster than best exponentiation algorithms given for standard exponents. For example, the speed of scalar multiplication on the standard Koblitz curve K163 is estimated to be accelerated by up to 51.5% and23.5% at the cost of memory for one precomputed point, compared to the TNAF and window TNAF methods, respectively. As for security, we show that the provable security of the DL problem using split exponents isonly byasmall constant, e.g., , worse than the security of the standard DL problem. Split exponents can be adopted to speed up various DL-based cryptosystems. We exemplify this on the recent CCA-secure public key encryption of Bellare, Kohno, and Shoup.