Begreper & formler

Finner $x,y$ slik at $ax+by=\gcd (a,b)$.

For $a,b$ der $\gcd (a,m)=1$, finnes $a^{-1}$ slik at $a\cdot a^{-1}\equiv 1(\mathrm{mod}m)$.

Beregner $a^b\mathrm{mod}m$ effektivt i $O(\log b)$ tid.

Basert på vanskeligheten av å faktorisere store tall: $c=m^e\mathrm{mod}n$, $m=c^d\mathrm{mod}n$.