Cryptography

A few algorithms of number theory

• Euclidean Algorithm: compute the greatest common divisor of two positive integers a and b
• Extended Euclidean Algorithm: take two integers a and b as input and compute integers r, s and t such that r=gcd(a,b) and s⋅a+t⋅b=r
• Square and Multiply Algorithm: compute modular exponentiations for large number in RSA cryptosystem
• Solovay-Strassen Algorithm: evaluate Jacobi symbol without factoring n
• Chinese Remainder Theorem: solve simultaneous congruence x=a₁ mod m₁, x=a₂ mod m₂, ..., x=a_n mod m_n
• Fast Exponentiation: exponentiation performed over a modulus