IT LAB

3. 모듈러컴퓨팅에서 한 숫자를 다른 숫자로 나눈 후, 나머지를 반환한 값 a mod n(유클리드 나눗셈의) 나머지a: 피제수n: 제수a mod b = a - b * (a/b) 성질덧셈 법칙뺄셈 법칙곱셈 법칙분배 법칙 응용큰 수 연산암호학해시 함수: 데이터를 고정된 크기의 값으로 매핑할 떄 사용됨주기성 확인: 반복되는 패턴을 찾는 데 사용됨 고급페르마의 소정리소수로 모듈러 연산하였을 때 결과를 구하는 공식소수 p와 p에 나누어 떨어지지 않는 정수 a가 있을 때a^(p) = a (mod p)a^(p-1) = 1  (mod p)a^(p-2) = 1/a  (mod p)a^(p-2)는 a의 모듈러 역원a * a^(p-2) = 1 (mod p) 이므로 a^-1 (mod p) = a^(p-2) (mod p) 확장 ..

1. 약수어떤 수를 나누어 떨어지게 하는 수 입니다.약수끼리 곱이 N이 되게끔 짝을 지을 수 있습니다. 2. 소인수주어진 자연수를 나누어 떨어뜨리는 약수중에서 소수인 약수​ 소인수분해합성수를 소인수들만의 곱으로 나타내는 것\[n = p_1^{a_1} \,\cdot\, p_2^{a_2} \,\cdot\, \cdots \,\cdot\, p_k^{a_k}\] 약수의 합n의 모든 양의 약수를 더한 값✅ 소인수분해 형태로 표현\[1 + p + p^2 + \cdots + p^a = \frac{p^{a+1} - 1}{p - 1}\]\[\sigma(n) = \prod_{i=1}^{k} \frac{p_i^{\,a_i + 1} - 1}{p_i - 1}\] 3. 최대공약수 (GCD)두 개 이상의 정수의 공통된 약수 중에서..