Description:
Karatsuba algorithm for multiplication is a recursive algorithm running in a time proportional to n which offers an asymptotic advantage over classical paper-and-pencil algorithm of n^2 complexity (n is the number of bits of the operands). Your task is to implement both classical and Karatsuba algorithms in software and find out what is the minimum operand length for which Karatsuba algorithm runs faster.
Literature:
Description:
Barett algorithm for modular reduction of large integers is based on a very simple idea, similar to the way you perform calculations using your calculator. When efficiently implemented this algorithm can work significantly faster than classical algorithm based on trial divisions. Your task is to implement both algorithms, find out the regions of superiority of one of the algorithms (as a function of the operand length), and assess how big can be the performance advantage of the Barett algorithm over classical algorithm for different operand lengths.
Literature:
Description:
Montgomery method is considered as a fastest algorithm for modular multiplication reported in the open literature. (At the ramp session of the last CRYPTO'95 Josh Benaloh announced that a faster algorithm was developed in Microsoft, but the details were not revealed, and the algorithm remains proprietary.) The idea of Montgomery algorithm is similar to multiplication using Fast Fourier Transform. We want to compute C=A*B mod N. The arguments A and B are first transformed to other domain by computing A'=A*2^n mod N, and B'=B*2^n mod N. In this new domain modular multiplication can be performed significantly faster than in the original domain. This is achieved by computing C'=A' * B' * 2^-n mod N = (A*B) * 2^n mod N = C*2^n mod N. The return to original domain is equivalent to multiplication by 1 in a new domain (C=1*C' * 2^-n mod N). Modular exponentiation is a basic transformation of majority of public key cryptoalgorithms. In exponentiation, a long sequence of modular multiplications is performed. For such sequence, input and output transformations are performed only once. Switching to other domain can therefore significantly speed-up the whole exponentiation. Knowledge of Montgomery algorithm is crucial for designers of majority of today's software and hardware public-key-cryptosystem implementations. Your task is to develop the efficient implementation of Montgomery algorithm, and compare your implementation with implementations of modular multiplication available in public domain (RSAREF, PGP, or PEM).
Literature: