Modular Multiplicative Inverse
A modular multiplicative inverse of an integer $a$ is an integer $x$ such that,
[Read More]
Linear Congruence
When can you divide a congruence?
[Read More]
Fermat's Little Theorem
I have a truly marvelous subtitle for this post which this margin is too narrow to contain.
Statement:
[Read More]
Extended Euclidean Algorithm
For two integers, $a$ and $b$, extended euclidean algorithm computes $\gcd(a,b)$ and coefficients $x,y \in \mathbb{Z}$ such that,
[Read More]
Exponentiation By Squaring
Finding $ a^{n}~\rm{mod}~m $ in $ \mathcal{O}(\lg~n) $ time
Given a base $a$, an exponent $n$ and a mod $m$, we have to compute $a^n ~\textrm{mod}~m$.
[Read More]