[기초 알고리즘] 수학: 모듈러

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) 이므로 

 

확장 유클리드 알고리즘 

• ax + by  = 1
• ax = 1 (mod b)
  • 두 수가 서로소여야 모듈러 역원이 존재
  • 결과값이 1이 아니라면 모듈러 연산을 반복해도 1을 얻을 수 없음

 

 

출처

• wiki - 모듈로