[암호] 오일러의 p 함수

1707~1783 년

 

레온하르트 오일러가 만든 함수로,

 

p(n) 는

1 부터 n 까지의 정수중 n 과 서로소인 정수의 개수를 뜻한다.

 

---

 

ex)

p(4) = 2        :    1 3 자신과의 서로소 1 ,3  -> 2개

 

 

n이 소수일때 아래의 공식이 성립

 

p(n^x) : n^x  -  n^(x-1)

 

 

만약 p(20) 과 같은 소수가 아닌 수가 나올 경우.

p(2^2) * p(5) 처럼 소수로 바꾸면 공식을 사용할 수 있어, 보다 더 쉽고 빠르게 풀 수 있다.

 

 

ex) 

 

p(2^2) = 2^2 - 2 = 2

 

p(7) = 7^1 - 7^0 = 6

 

p(252) = p(2^2) * p(3^2) * p(7) = ( 4 - 2 ) * ( 9 - 3 ) * ( 7 - 1 ) = 72