A Survey of Fast Exponentiation Methods
---
paper_title: A method for obtaining digital signatures and public-key cryptosystems

paper_content:

An encryption method is presented with the novel property that publicly revealing an encryption key does not thereby reveal the corresponding decryption key. This has two important consequences: (1) Couriers or other secure means are not needed to transmit keys, since a message can be enciphered using an encryption key publicly revealed by the intented recipient. Only he can decipher the message, since only he knows the corresponding decryption key. (2) A message can be “signed” using a privately held decryption key. Anyone can verify this signature using the corresponding publicly revealed encryption key. Signatures cannot be forged, and a signer cannot later deny the validity of his signature. This has obvious applications in “electronic mail” and “electronic funds transfer” systems. A message is encrypted by representing it as a number M, raising M to a publicly specified power e, and then taking the remainder when the result is divided by the publicly specified product, n , of two large secret primer numbers p and q. Decryption is similar; only a different, secret, power d is used, where e * d ≡ 1(mod (p - 1) * (q - 1)). The security of the system rests in part on the difficulty of factoring the published divisor, n .
---
paper_title: Modular Multiplication Without Trial Division

paper_content:

Let N > 1. We present a method for multiplying two integers (called N-residues) modulo N while avoiding division by N. N-residues are represented in a nonstandard way, so this method is useful only if several computations are done modulo one N. The addition and subtraction algorithms are unchanged. 1. Description. Some algorithms (1), (2), (4), (5) require extensive modular arith- metic. We propose a representation of residue classes so as to speed modular multiplication without affecting the modular addition and subtraction algorithms. Other recent algorithms for modular arithmetic appear in (3), (6). Fix N > 1. Define an A'-residue to be a residue class modulo N. Select a radix R coprime to N (possibly the machine word size or a power thereof) such that R > N and such that computations modulo R are inexpensive to process. Let R~l and N' be integers satisfying 0 N then return t - N else return t ■ To validate REDC, observe mN = TN'N = -Tmod R, so t is an integer. Also, tR = Tmod N so t = TR'X mod N. Thirdly, 0 < T + mN < RN + RN, so 0 < t < 2N. If R and N are large, then T + mN may exceed the largest double-precision value. One can circumvent this by adjusting m so -R < m < 0. Given two numbers x and y between 0 and N - 1 inclusive, let z = REDC(xy). Then z = (xy)R~x mod N, so (xR-l)(yR~x) = zRx mod N. Also, 0 < z < N, so z is the product of x and y in this representation. Other algorithms for operating on N-residues in this representation can be derived from the algorithms normally used. The addition algorithm is unchanged, since xR~x + yR~x = zR~x mod N if and only if x + y = z mod N. Also unchanged are
---
paper_title: New Modular Multiplication Algorithms for Fast Modular Exponentiation

paper_content:

A modular exponentiation is one of the most important operations in public-key cryptography. However, it takes much time because the modular exponentiation deals with very large operands as 512-bit integers. The modular exponentiation is composed of repetition of modular multiplications. Therefore, we can rcducc the execution time of it by reducing thc execution time of each modular multiplication. In this paper, we propose two fast modular multiplication algorithms. One is for modular multiplications between different integers, and the other is for modular squarings. These proposed algorithms require single-precision multiplications fewer than those of Montgomery modular multiplication algorithms by 1/2 and 1/3 times, respectively. Implementing on PC, proposed algorithms reduce execution times by 50% and 30% compared with Montgomery algorithms, respectively.
---
paper_title: New Directions in Cryptography

paper_content:

Two kinds of contemporary developments in cryptography are examined. Widening applications of teleprocessing have given rise to a need for new types of cryptographic systems, which minimize the need for secure key distribution channels and supply the equivalent of a written signature. This paper suggests ways to solve these currently open problems. It also discusses how the theories of communication and computation are beginning to provide the tools to solve cryptographic problems of long standing.
---
paper_title: Efficient exponentiation using precomputation and vector addition chains

paper_content:

An efficient algorithm for exponentiation with precomputation is proposed and analyzed. Due to the precomputations, it is mainly useful for (discrete log based) systems with a fixed base.
---
paper_title: On vectorial addition chains

paper_content:

Abstract We prove the equivalence between the problem of computing a multinominal x 1 n 1 · x 2 n 2 ··· x k n k , posed by R. E. Bellman ( Amer. Math. Monthly 70 1963, 765), and the problem of computing simultaneously the monomials x n 1 ,…, x n k , posed by D. E. Knuth (“Seminumerical Algorithms”, Sect. 4.6.3, Addison-Wesley, Reading, Mass 1969.
---
paper_title: Computing Sequences with Addition Chains

paper_content:

Given a sequence $n_1 , \cdots ,n_m $ of positive integers, what is the smallest number of additions needed to compute all m integers starting with 1? This generalization of the addition chain ($m = 1$) problem will be called the addition-sequence problem. We show that the sequence $\{ 2^0 ,2^1 , \cdots ,2^{n - 1} ,2^n - 1\} $ can be computed with $n + 2.13\sqrt n + \log n$ additions, and that $n + \sqrt n - 2$ is a lower bound. This lower bound result is applied to show that the addition-sequence problem is NP-complete.
---
paper_title: Fast exponentiation with precomputation: Algorithms and lower bounds

paper_content:

A cosmetic packaging device with aligning cap includes connection structures and/or a collar that facilitate easy alignment of the cap/applicator to the cosmetics packaging in order to achieve a desirable appearance in an easy manner to the user. Ramped edges on one or both of the collar on a bottle and/or a connecting structure of an applicator are designed to guide a tab into a slot as the applicator and cap are replaced on the cosmetics packaging, which may contain a cosmetic product such as a mascara, lip gloss or various other products.
---
paper_title: Speeding up Elliptic Cryptosystems by Using a Signed Binary Window Method

paper_content:

The basic operation in elliptic cryptosystems is the computation of a multiple d?P of a point P on the elliptic curve modulo n. We propose a fast and systematic method of reducing the number of operations over elliptic curves. The proposed method is based on pre-computation to generate an adequate addition-subtraction chain for multiplier the d. By increasing the average length of zero runs in a signed binary representation of d, we can speed up the window method. Formulating the time complexity of the proposed method makes clear that the proposed method is faster than other methods. For example, for d with length 512 bits, the proposed method requires 602.6 multiplications on average. Finally, we point out. that each addition/subtraction over the elliptic curve using homogeneous coordinates can be done in 3 multiplications if parallel processing is allowed.
---
paper_title: New Modular Multiplication Algorithms for Fast Modular Exponentiation

paper_content:

A modular exponentiation is one of the most important operations in public-key cryptography. However, it takes much time because the modular exponentiation deals with very large operands as 512-bit integers. The modular exponentiation is composed of repetition of modular multiplications. Therefore, we can rcducc the execution time of it by reducing thc execution time of each modular multiplication. In this paper, we propose two fast modular multiplication algorithms. One is for modular multiplications between different integers, and the other is for modular squarings. These proposed algorithms require single-precision multiplications fewer than those of Montgomery modular multiplication algorithms by 1/2 and 1/3 times, respectively. Implementing on PC, proposed algorithms reduce execution times by 50% and 30% compared with Montgomery algorithms, respectively.
---
paper_title: Addition Chain Heuristics

paper_content:

Much current research focuses on fast evaluation of RSA, which consists of computing powers modulo a large number n. While some try to increase the speed of multiplica- tions, here we consider reducing the number of multiplications. In particular, we present a precomputation method that reduces the number of multiplications for the computation of a given power.
---
paper_title: Addition Chain Heuristics

paper_content:

Much current research focuses on fast evaluation of RSA, which consists of computing powers modulo a large number n. While some try to increase the speed of multiplica- tions, here we consider reducing the number of multiplications. In particular, we present a precomputation method that reduces the number of multiplications for the computation of a given power.
---
paper_title: Speeding up Elliptic Cryptosystems by Using a Signed Binary Window Method

paper_content:

The basic operation in elliptic cryptosystems is the computation of a multiple d?P of a point P on the elliptic curve modulo n. We propose a fast and systematic method of reducing the number of operations over elliptic curves. The proposed method is based on pre-computation to generate an adequate addition-subtraction chain for multiplier the d. By increasing the average length of zero runs in a signed binary representation of d, we can speed up the window method. Formulating the time complexity of the proposed method makes clear that the proposed method is faster than other methods. For example, for d with length 512 bits, the proposed method requires 602.6 multiplications on average. Finally, we point out. that each addition/subtraction over the elliptic curve using homogeneous coordinates can be done in 3 multiplications if parallel processing is allowed.
---
paper_title: Efficient exponentiation in finite field

paper_content:

Optimal sequential and parallel algorithms for exponentiation in a finite field extension are presented, assuming that a normal basis over the ground field is given.<<ETX>>
---
paper_title: Some observations on parallel algorithms for fast exponentiation in GF(2 n )

paper_content:

A normal basis representation of $\operatorname{GF}(2^{n})$ allows squaring to be accomplished by a cyclic shift. Algorithms for multiplication in $\operatorname{GF}(2^{n})$ using a normal basis have been studied by several researchers. In this paper, algorithms for performing exponentiation in $\operatorname{GF}(2^{n})$ using a normal basis, and how they can be speeded up by using parallelization, are investigated.
---
paper_title: Reducing elliptic curve logarithms to logarithms in a finite field

paper_content:

Elliptic curve cryptosystems have the potential to provide relatively small block size, high-security public key schemes that can be efficiently implemented. As with other known public key schemes, such as RSA and discrete exponentiation in a finite field, some care must be exercised when selecting the parameters involved, in this case the elliptic curve and the underlying field. Specific classes of curves that give little or no advantage over previously known schemes are discussed. The main result of the paper is to demonstrate the reduction of the elliptic curve logarithm problem to the logarithm problem in the multiplicative group of an extension of the underlying finite field. For the class of supersingular elliptic curves, the reduction takes probabilistic polynomial time, thus providing a probabilistic subexponential time algorithm for the former problem. >
---
paper_title: Elliptic Curve Public Key Cryptosystems

paper_content:

Foreword. Preface. 1. Introduction to Public Key Cryptography. 2. Introduction to Elliptic Curves. 3. Isomorphism Classes of Elliptic Curves over Finite Fields. 4. The Discrete Logarithm Problem. 5. The Elliptic Curve Logarithm Problem. 6. Implementation of Elliptic Curve Cryptosystems. 7. Counting Points on Elliptic Curves over F2m. Bibliography. Index.
---
paper_title: An Improved Algorithm for Arithmetic on a Family of Elliptic Curves

paper_content:

It has become increasingly common to implement discrete-logarithm based public-key protocols on elliptic curves over finite fields. The basic operation is scalar multiplication: taking a given integer multiple of a given point on the curve. The cost of the protocols depends on that of the elliptic scalar multiplication operation. Koblitz introduced a family of curves which admit especially fast elliptic scalar multiplication. His algorithm was later modified by Meier and Staffelbach. We give an improved version of the algorithm which runs 50% faster than any previous version. It is based on a new kind of representation of an integer, analogous to certain kinds of binary expansions. We also outline further speedups using precomputation and storage.
---
paper_title: Efficient Multiplication on Certain Nonsupersingular Elliptic Curves

paper_content:

Elliptic curves defined over finite fields have been proposed for Diffie-Hellman type crypto systems. Koblitz has suggested to use "anomalous" elliptic curves in characteristic 2, as these are nonsupersingular and allow for efficient multiplication of points by an integer.For anomalous curves E defined over F2 and regarded as curves over the extension field F2n, a new algorithm for computing multiples of arbitrary points on E is developed. The algorithm is shown to be three times faster than double and add, is easy to implement and does not rely on precomputation or additional memory. The algorithm is used to generate efficient one-way permutations involving pairs of twisted elliptic curves by extending a construction of Kaliski to finite fields of characteristic 2.
---
paper_title: An Improved Algorithm for Arithmetic on a Family of Elliptic Curves

paper_content:

It has become increasingly common to implement discrete-logarithm based public-key protocols on elliptic curves over finite fields. The basic operation is scalar multiplication: taking a given integer multiple of a given point on the curve. The cost of the protocols depends on that of the elliptic scalar multiplication operation. Koblitz introduced a family of curves which admit especially fast elliptic scalar multiplication. His algorithm was later modified by Meier and Staffelbach. We give an improved version of the algorithm which runs 50% faster than any previous version. It is based on a new kind of representation of an integer, analogous to certain kinds of binary expansions. We also outline further speedups using precomputation and storage.
---
paper_title: Speeding up Elliptic Cryptosystems by Using a Signed Binary Window Method

paper_content:

The basic operation in elliptic cryptosystems is the computation of a multiple d?P of a point P on the elliptic curve modulo n. We propose a fast and systematic method of reducing the number of operations over elliptic curves. The proposed method is based on pre-computation to generate an adequate addition-subtraction chain for multiplier the d. By increasing the average length of zero runs in a signed binary representation of d, we can speed up the window method. Formulating the time complexity of the proposed method makes clear that the proposed method is faster than other methods. For example, for d with length 512 bits, the proposed method requires 602.6 multiplications on average. Finally, we point out. that each addition/subtraction over the elliptic curve using homogeneous coordinates can be done in 3 multiplications if parallel processing is allowed.
---
paper_title: Efficient exponentiation using precomputation and vector addition chains

paper_content:

An efficient algorithm for exponentiation with precomputation is proposed and analyzed. Due to the precomputations, it is mainly useful for (discrete log based) systems with a fixed base.
---
paper_title: More Flexible Exponentiation with Precomputation

paper_content:

A new precomputation method is presented for computing gR for a fixed element g and a randomly chosen exponent R in a given group. Our method is more efficient and flexible than the previously proposed methods, especially in the case where the amount of storage available is very small or quite large. It is also very efficient in computing gRyB for a small size E and variable number y, which occurs in the verification of Schnorr's identification scheme or its variants. Finally it is shown that our method is well-suited for parallel processing as well.
---
paper_title: Efficient and optimal exponentiation in finite fields

paper_content:

Optimal sequential and parallel algorithms for exponentiation in a finite field containing F q are presented, assuming thatqth powers can be computed for free.
---
paper_title: Some observations on parallel algorithms for fast exponentiation in GF(2 n )

paper_content:

A normal basis representation of $\operatorname{GF}(2^{n})$ allows squaring to be accomplished by a cyclic shift. Algorithms for multiplication in $\operatorname{GF}(2^{n})$ using a normal basis have been studied by several researchers. In this paper, algorithms for performing exponentiation in $\operatorname{GF}(2^{n})$ using a normal basis, and how they can be speeded up by using parallelization, are investigated.
---
paper_title: Fast exponentiation with precomputation: Algorithms and lower bounds

paper_content:

A cosmetic packaging device with aligning cap includes connection structures and/or a collar that facilitate easy alignment of the cap/applicator to the cosmetics packaging in order to achieve a desirable appearance in an easy manner to the user. Ramped edges on one or both of the collar on a bottle and/or a connecting structure of an applicator are designed to guide a tab into a slot as the applicator and cap are replaced on the cosmetics packaging, which may contain a cosmetic product such as a mascara, lip gloss or various other products.
---
paper_title: Computing Powers in Parallel

paper_content:

Fast parallel computations are presented for large powers modulo an element that has only small prime factors. They work for integers and polynomials over small finite fields.
---
paper_title: More Flexible Exponentiation with Precomputation

paper_content:

A new precomputation method is presented for computing gR for a fixed element g and a randomly chosen exponent R in a given group. Our method is more efficient and flexible than the previously proposed methods, especially in the case where the amount of storage available is very small or quite large. It is also very efficient in computing gRyB for a small size E and variable number y, which occurs in the verification of Schnorr's identification scheme or its variants. Finally it is shown that our method is well-suited for parallel processing as well.
---

Title: A Survey of Fast Exponentiation Methods

Section 1: Introduction
Description 1: This section introduces the fundamental concept of exponentiation in computational number theory and its importance in cryptography, discussing various applications and the motivation for fast exponentiation methods.

Section 2: Addition Chains
Description 2: This section explores the concept of addition chains and their role in minimizing the number of multiplications necessary for exponentiation.

Section 3: Addition-Subtraction Chains
Description 3: This section discusses how allowing subtraction operations can reduce the length of addition chains and improve efficiency, particularly with elliptic curves.

Section 4: Addition Sequences and Vector Addition Chains
Description 4: This section elaborates on generalizations of addition chains, focusing on addition sequences and vector addition chains used for computing multiple powers and their related algorithms.

Section 5: Binary Method
Description 5: This section details the binary method, also known as the "square and multiply" method, and its historical significance and computational efficiency.

Section 6: m-ary Method
Description 6: This section describes the m-ary method, a generalization of the binary method that uses bases larger than two, and analyzes its efficiency in exponentiation.

Section 7: Redundant Number Systems
Description 7: This section examines the use of redundant number systems, including nonadjacent form (NAF) representations, and their impact on reducing the number of multiplications.

Section 8: Window Methods
Description 8: This section introduces window methods, a generalization of the binary method, which optimize the computation by skipping strings of zeros and precomputing certain powers.

Section 9: Normal Bases
Description 9: This section discusses groups with added structure, such as GF(p^n), where normal bases allow for faster calculations, especially in fields like GF(2^n).

Section 10: Elliptic Curves
Description 10: This section covers the use of elliptic curves in cryptography, detailing specific methods for optimizing point addition and the use of special types of curves.

Section 11: The BGMW Method
Description 11: This section outlines the BGMW method for precomputing powers to speed up exponentiation, especially in scenarios like Diffie-Hellman key exchange.

Section 12: Precomputation with Vector Addition Chains
Description 12: This section explains the use of vector addition chains to improve precomputation methods, balancing storage requirements and computation time.

Section 13: Parallel Algorithms
Description 13: This section discusses parallel algorithms for exponentiation, their complexity, and the potential for parallel processor implementations to achieve faster computations.

Section 14: Conclusions
Description 14: This section summarizes the findings of the survey, presents general principles for selecting exponentiation methods, and offers recommendations for further optimization.