[9장 암호수학] 소수, 소인수분해, CRT, 합동방정식

Positive integers

양의 정수는 1, 소수, 합성수로 이루어진다.

1: 숫자 1

소수: 1과 자기자신만을 약수로 갖음

합성수: 3개 이상의 약수를 갖는다.

 

서로 소(Relatively Prime)

- 두 개의 양의 정수가 gcd(a,b)=1를 만족할 때.

- 만약 p가 소수라면 1부터 p-1까지의 모든 정수는 p와 서로소가 된다.

 

소수판정

Q. 임의로 주어진 양의 정수 n이 소수인지 아닌지를 판단하는 법

A. 루트(n)보다 작은 모든 소수로 나누어 지는지 확인해본다.

ex) 97은 소수인가? 루트97은 9보다 크고 10보다는 작다. 9 이하의 소수는 2, 3, 5, 7이다.

2, 3, 5, 7 중 어느 소수도 97을 나누지 못하므로 97은 소수이다.

 

에라토스테네스의체-양의 정수로 된 모든 수 중 합성수를 빼본다.

 

오일러 함수-

페르마의 리틀 정리

오일러 정리

소수 생성

Mersenne소수: 2^p - 1

Fermat 소수: 2^(2^n)+1

 

소수판정

• 결정적 알고리즘: 100% 소수이다 판정 가능
  -나눔 알고리즘
  -AKS 알고리즘
• 확률적 알고리즘: 100%는 아닌데 합성수일 확률보다 소수일 확률이 높다.
  페르마 소수 검증
  제곱근 소수 검증
  밀러-라빈 소수 검증 

 

소인수분해

-전수 나눔 방법

-페르마 방법

-Pollard p-1 방법

-Pollard rho 방법

 

중국인의 나머지 정리

정의: 한 개의 변수와 서로소인 다른 모듈로를 갖는 합동 방정식의 해를 구할 수 있다.

--> 2차 합동을 풀 수 있다.

 

오일러 판정 기준

 

고속 지수 계산

모듈로 로그 계산?