RSA Principle 1

History

In 1977, three mathematician Rivest Shamir and Adleman designed the RSA algorithm.

Coprime relation

If two positive integer no other common elements except 1,
then these two number be called have coprime relation.

• any two coprime number compose to coprime relation
• one coprime another is not multiple with the privous one then coprime relation.
• if the bigger one in two number is coprime number, then these two compose to coprime relation.
• 1 with any nature number is coprime relation.
• p is integer bigger than 1, p and p-1 is coprime relation.
• p is odd number bigger than 1, p and p-2 is coprime relation.

Euler formula(function)

Condition 1

$$\phi(1) = 1$$

1 with any nature number is coprime relation.

Condition 2

$$\phi(n) = n - 1$$

If n is coprime number than every number lower than n is coprime relation with n.

Condition 3

$$\phi(p^k) = p^k - p^{k-1} = p^k(1-\frac{1}{p})$$

If number n is some coprime number’s times square than.

For example:

$$\varphi(16) = \varphi(2^4) = 2^4 - 2^3 = 8$$

In 1 -> 16 totle 2^3 is multiple with 2.
So the number coprime relation with 16 is 8;
1 3 5 7 9 11 13 15

Condition 4

If number can be separate into
two number that have coprime relation.

$$n = p1 \times p2$$

Then:

$$\phi(n) = \phi(p1) \times \phi(p2)$$

For example:

$$\varphi(72) = \varphi(9) \times \varphi(8) = 32$$

Condition 5

Any positive integer can be separate into
a series of coprime number’s accumulate.

$$n = p_{1}^{k1} p_{2}^{k2}... p_{r}^{kr}$$

based on proposition 4 ->

$$\phi(n) = \phi(p_{1}^{k1}) \phi(p_{2}^{k2})... \phi(p_{r}^{kr})$$

based on proposition 3->

$$\phi(n) = p_{1}^{k1} p_{2}^{k2}... p_{r}^{kr}(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_r})$$

then ->

$$\phi(n) = n(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_r})$$

This is the Euler’s common formula , for example

$$\varphi(11025) = \varphi(7^2 \times 5^2 \times 3^2) = 11025 \times (1-\frac{1}{7}) \times (1-\frac{1}{5}) \times (1-\frac{1}{3}) = 720$$

Euler proposition

$$a^{\phi(n)} \equiv 1 \quad ( mod \quad n)$$

Special Condition
If p is a coprime number than:

$$a^{p-1} \equiv 1 \quad ( mod \quad p)$$

• Fermat little theorem
• Fermat euler theorem

Mod inverse element

If two number a and n is coprime relation
than definitely could find a number b that $ab \quad mod \quad n = 1$

Call b is a’s mod reserve element

For example:
3 and 5 is coprime relation , set a=3, n=5, then a’s mod reserve element is 7.
7 {+-} kn[-4, 7, 12, 17] is all a’s mod reserve element.

---

Euler proposition proves mod reserve element definitely exists.

$$a^{\phi(n)} = a \times a^{\phi(n)-1} \equiv 1 \quad ( mod \quad n)$$ $$a^{\phi(n)-1} $$ is a's mod reserve element Like above a=3 and n=5, a's mod reserve elementis$$

a^{\phi(5)-1} = 3^3 = 27

$$