아래 키 값은 RSA 알고리즘에서 사용하게 됩니다.
(그 일부분, 모듈러 연산만 간단히 풀이)
p 11 / q 3 / M 5
n= 33
10*2 = 20 = 0(n)
e = 3
d*3 = 1 mod 20
= 20*1+1
KU = {3,20} KR = {7,20}
큰 숫자에서는 유클리드확장법으로 계산하는 것이 편하다.
ex) d*5 = 1 mod 96
오른쪽변: 어떤 숫자를 96으로 나누었을때 나머지가 1
96*1+1 = 97
96*2+1 = 194
96*3+1 = 289
96*4+1 = 385
여기서 나온 값이 왼쪽변을 만족해야한다.
왼쪽변: 97/5 = 19.4
194/5 = 38.8
289/5 = 57.8
385/5 = 77 이게 바로 d 이다.