from top to down

  1. RSA process

    flowchart TD
    A("Start"):::softPink --> B("Select p and q"):::softYellow
    B --> C("Calculate n = p * q"):::softYellow
    C --> D("Calculate φ(n) = (p-1) * (q-1)"):::softYellow
    D --> E["Choose public key e:
    1. 1 < e < φ(n)
    2. gcd(e,φ(n)) = 1
    3. Typically use 65537"]:::softYellow
    E --> F["Calculate private key d:
    1. d * e ≡ 1 mod φ(n)
    2. Extended Euclidean Algorithm
    3. d is the multiplicative inverse of e"]:::softYellow
    F --> G("Keys Generated"):::softBlue
    G --> H("Encryption: C ≡ M^e mod n"):::softPink
    G --> I("Decryption: M ≡ C^d mod n"):::softBlue


    classDef softPink fill:#FFE6E6,stroke:#666,stroke-width:1px
    classDef softBlue fill:#E6E6FF,stroke:#666,stroke-width:1px
    classDef softYellow fill:#FFFFF0,stroke:#666,stroke-width:1px

    1. basic princle for this algorithm

      • decryptable

        as above

        we have plaintext M, keys (d,e,n)

        sending memod  nm^e\mod n

        recieve C, and decoding Cdmod  nC^d\mod n

        that is proof: M≡cdmod  nM \equiv c^d \mod n

        proof

        proof_2

      • modular

        a mod b:= r => a = qb+r a,b∈Z,b>0a,b \in Z,b>0

        not that a <0 could have similar way to find it

        -40 mod 11= ?

        q*11 +40 = r

        basic properties

        (1)a+bmod  n=(amod  n+bmod  n)mod  n(2)a−bmod  n=(amod  n−bmod  n)mod  n(3)a×bmod  n=((amod  n)×(bmod  n))mod  n\begin{align*} &(1) \quad a + b \mod n = (a \mod n + b \mod n) \mod n \\ &(2) \quad a - b \mod n = (a \mod n - b \mod n) \mod n \\ &(3) \quad a \times b \mod n = ((a \mod n) \times (b \mod n)) \mod n \end{align*}

        this improvement is quick simple, I’d like to using visualization as below.

        list

        Also, if you like a formal proof

        To prove:a+bmod  n=(amod  n)+(bmod  n)mod  nAssume:r=a+bmod  n,r1=a−k1n,r2=b−k2nSubstitute:r=a+b  ⟹  r=r1+k1n+r2+k2n=(k1+k2)n+r1+r2Thus, we have:r≡r1+r2 (mod n)Conclusion:Clearly, r≡r1+r2 (mod n),Quod Erat Demonstrandum\text{To prove:} \quad a + b \mod n = (a \mod n) + (b \mod n) \mod n \\ \text{Assume:} \quad r = a + b \mod n, \quad r_1 = a - k_1 n, \quad r_2 = b - k_2 n \\ \text{Substitute:} \quad r = a + b \implies r = r_1 + k_1 n + r_2 + k_2 n = (k_1 + k_2)n + r_1 + r_2 \\ \text{Thus, we have:} \quad r \equiv r_1 + r_2 \ (\text{mod} \ n) \\ \text{Conclusion:} \quad \text{Clearly,} \ r \equiv r_1 + r_2 \ (\text{mod} \ n), \quad \text{Quod Erat Demonstrandum}

        Note that, Do not using divided into this function, a straight-forward way:

        (1)9≡3(mod6)(2)9÷3≡3÷3(mod6)(3)obviously it does not satisfy(4)3≢1(mod6)\begin{align*} &(1) \quad 9 \equiv 3 \pmod{6} \\ &(2) \quad 9 \div 3 \equiv 3 \div 3 \pmod{6} \\ &(3) \quad \textit{obviously it does not satisfy} \\ &(4) \quad 3 \not\equiv 1 \pmod{6} \end{align*}

        Because 3 and 6 are not coprime (互质), division does not hold in modular arithmetic. This is one of the most critical points to note when working with congruences（同余）

      • modular inverse(模逆元)

        This concecption is too signicant to expression my second language. I have to finish it with my bilingual.

        这个概念特别重要，我需要使用双语来完成相关的描述。

        For a normal inverse like matrx inverse and The notation $$a^{-1}$$ should not be confused with the reciprocal in regular arithmetic.When we write $$a^{-1}$$, we mean the number that when multiplied by $$a$$ gives 1 in modular arithmetic

        我们通常将 e−1mod  me^{-1} \mod m 等价于(m+1)÷x=d,d∈(0,m,R)(m+1)\div x =d,d\in(0,m,R) 这种情况下，我们说d是e的乘法逆元

        值得一提，我们通常直接会将这个负一次幂保留，而去理解成他的逆元（或者是他的等价式子）千万不要当到倒数去理解（这是在不用模下面的倒数）

        • Application(应用)：
          The main application is to enable division in modular arithmetic by converting division into multiplication:

          上节我们知道，模运算不支持除法等价性，这时候我们能够将其同时呈上对应的乘法逆元，就能拿使用对应的性质

          $ \quad a \times b^{-1} \mod n = ((a \mod n) \times (b^{-1} \mod n)) \mod n
          $

          ab−1≡cb−1→a≡c\quad ab^-1\equiv cb^{-1}\rightarrow a\equiv c

        • Existence Property(存在性)：

          A modular multiplicative inverse of $$a$$ modulo $$m$$ exists if and only if $$a$$ and $$m$$ are coprime.That is, if $$\gcd(a,m) = 1$$, then there exists a unique $$b$$ in $$[0,m-1]$$ such that:

          如果a与c互素，那么其一定存在乘法逆元b−1如果a与c互素，那么其一定存在乘法逆元b^-1

          换句话说，互质的两个数具有除法消去性

    2. Euler’s Theorem and proof

      1. Euler’s totient funtcion

        ϕ(n)\phi_{(n)} conclude all the numbers which are prime to n in range(0,n).

        Specially, If n is a prime number, ϕ(n)=n−1\phi_{(n)}=n-1

      2. Euler’s Theorem

        If a,n are prime numbers,Asgcd⁡(a,n)=1Then: aϕ(n)≡1(modn)\begin{align*} &\text{If } a, n \text{ are prime numbers,As} \gcd(a,n) = 1 \\ &\text{Then: } a^{\phi(n)} \equiv 1 \pmod{n} \end{align*}

        Proof:

        since this proof represent a constructing way, I’d like to demo it a little

        Assume R={r1,r2,...,rϕ(n)} is a simple coprime set of nSince a is prime to n, we can conclude a⋅R is also in a set  which isanother coprime set,written as R2. (demo below)Therefore:R≡R2(modn)→r1r2...rϕ(n)≡a1a2...aϕ(n)(modn)Remove r1,r2,r3,...,rϕ(n) from both sides:→1≡aϕ(n)(modn)\begin{align*} &\text{Assume } R = \{r_1, r_2, ..., r_{\phi(n)}\} \text{ is a simple coprime set of } n \\ &\text{Since } a \text{ is prime to } n, \text{ we can conclude } a \cdot R \text{ is also in a set } \text{ which is} \\ &\text{another coprime set,written as R2. (demo below)} \\[1em] &\text{Therefore:} \\ &R \equiv R_2 \pmod{n} \\ &\rightarrow r_1r_2...r_{\phi(n)} \equiv a_1a_2...a_{\phi(n)} \pmod{n} \\[1em] &\text{Remove } r_1, r_2, r_3, ..., r_{\phi(n)} \text{ from both sides:} \\ &\rightarrow 1 \equiv a^{\phi(n)} \pmod{n} \end{align*}

        e.g

        congruence set{1,3,5,7} for 8 ,ϕ(8)=4\phi_{(8)}=4

        meanwhile a in {1,3,5,7}

        try a =3

        you can get {3,9,15,21} while the rest set is {3,1,7,5}

      so far, you have to remeber

      1. RSA algorithm in math is actually a mod inverse computing anti decryption
      2. set, group, class begin