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) 확장 ..

약수어떤 수를 나누어 떨어지게 하는 수 입니다.약수끼리 곱이 N이 되게끔 짝을 지을 수 있습니다. 최대공약수 (GCD)두 개 이상의 정수의 공통된 약수 중에서 가장 큰 수를 뜻합니다. 구현유클리드 알고리즘 (구현)두 수의 최대공약수는 작은수와 두 수를 나눈 나머지의 최대공약수와 같음더보기더보기더보기int gcd(int a, int b) { return b == 0 ? a : gcd(b, a%b);} 재귀적 구현이 가능합니다.가장 효율적입니다. 고급베주 항등식ax + by = gcd(a, b)위 식을 만족하는 x, y쌍이 항상 존재 (1개 이상)