All articles

• Chinese remainder theorem

  The Chinese remainder theorem can be used to solve systems of congruences like:

  $$\begin{aligned} x \equiv a_1& \pmod{m_1} \\ &\vdots \\ x \equiv a_k& \pmod{m_n} \\ \end{aligned}$$

• Euler’s theorem

  Euler’s theorem may be used to compute modular inverses. According to the theorem, if $a$ is coprime to $m$, that is, $\gcd(a, m) = 1$, then

  $$a^{\varphi …$$

• Euler’s totient function

  Euler’s totient function counts the number of positive integers up to a given integer $n$ that are coprime to $n$. In other word, the number of integers $k$ in the range $1 \le k \le n$ for …

• Modular exponentiation

  The purpose of modular exponentiation is to compute the value $c$ in equations of the form

  $$c \equiv b^e \pmod{n}$$

  when $b$, $e$ and $m$ are known (large …

• RSA

  RSA is a public-key encryption and signature system and makes use of large prime numbers. The asymmetry is based on the fact that computing a product is fast, but factoring takes much longer.

  Operation

  The RSA algorithm involves the steps key generation, encryption and decryption. It can also be used …