Discrete Algebraic Methods

3 Number theoretic algorithms

Many cryptosystems rely on fast arithmetic in various algebraic structures. For instance, when creating the private and the public key for Rivest–Shamir–Adleman (RSA), you have to find large prime numbers p and q, as well as to invert modulo (p − 1)(q − 1); then, a fast algorithm for exponentiation is required for encryption and decryption. In addition, we want fast algorithms for multiplication and division for the elementary operations of computing the product of two numbers modulo n. On the other hand, the security of many cryptosystems relies on the difficulty of some number theoretic problems. For instance, RSA is secure only as long as there is no efficient algorithm for integer factorization. It is therefore ...