Crypto
페르마의 작은 정리(Fermat’s Little Theorem
어떤 정수 a에 대해, 그것이 어떤 소수 (Prime Number) p로 나누어 떨어지지 않는다면, a^p-1을 p로 나눈 나머지는 항상 1이다. 3^17 = 0 mod 17 3^16= 1 mod 17 3 * d ≡ 1 mod 13 에서 d를 구하는 법은 {(3**12) / 3} % 13 이다
Crypto
Crypto
정수론에서의 모듈러 연산
어떤 한 숫자를 다른 숫자로 나눈 나머지를 구하는 연산으로, 나머지 연산(mod)이라고 한다. 정수론에서 모듈러 연산(modular arithmetic)이란, 정수의 합과 곱을 어떤 주어진 수의 나머지에 대하여 정의하는 방법이다. Ex..) a ≡ b mod m 설명: a를 m 으로 나누었을때 나머지 b
Crypto
GCD 에 대해서
GCD Euclidean algorithm 일명: 유클리드 호제법 결론: 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지 를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다. 호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘 78696 ＝ 19332×4 ＋ 1368 19332 ＝ 1368×14 ＋ 180 1368 ＝ 180×7 ＋ 108 180 ＝ 108×1 ＋ 72 108 ＝ 72×1 ＋ 36 72 ＝ 36×2 ＋ 0 #;; 최대 공..
-
이전
- 1
-
다음
