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 RivestShamirAdleman (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 ...

Get Discrete Algebraic Methods now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.