Biblio

This research aims to implement different modular exponentiation algorithms and evaluate the average complexity and compare it to the theoretical value. We use the library GMP to implement seven modular exponentiation algorithms. They are Left-to-right Square and Multiply, Right-to-left Square and Multiply, Left-to-right Signed Digit Square, and Multiply Left-to-right Square and Multiply Always Right-to-left Square and Multiply Always, Montgomery Ladder and Joye Ladder. For some exponent bit length, we choose 1024 bits and execute each algorithm on many exponent values and count the average numbers of squares and the average number of multiplications. Whenever relevant, our programs will check the consistency relations between the registers at the end of the exponentiation.