辗转相除法
gcd(a,b) = s*a + t*b = {{gcdab}} = {{results[results.length-1].s1}}*{{results[0].r1}} + {{results[results.length-1].t1}}*{{results[0].r2}}
multiplicative inverse of b (mod a) = {{results[0].r2}}^-1 (mod {{results[0].r1}}) = {{binverse}}
a:
b:
- a
- b
- q
- r
- s1
- s2
- t1
- t2
- {{each.r1}}
- {{each.r2}}
- {{each.q}}
- {{each.r}}
- {{each.s1}}
- {{each.s2}}
- {{each.t1}}
- {{each.t2}}
RSA
choose p: should be
prime
choose q: should be
prime
n=p*q={{this.pq}}
φ(n)=(p-1)*(q-1)={{this.p1q1}}
choose e:
gcd(e,φ(n))={{this.gcdeyn}}, should be 1
d=e^-1 mod φ(n)
choose d:
or
{{this.lastd}}+{{this.p1q1}}*k
ed mod φ(n) = {{computeedmodyn()}}, should be 1
plaintext m: should
< n
encryption c=(m^e)%n=({{this.m}}^{{this.e}})%{{this.p*this.q}}={{this.c}}
ciphertext c: should < n
decryption
m=(c^d)%n=({{this.ct}}^{{this.d}})%{{this.pq}}={{(BigInt(this.ct)**BigInt(this.d))%this.pq}}