[일반] 오일러 피 함수의 값을 구하는게 소인수분해보다 어려움?

[익명(49.174)]

ㅇㅇ

[익명(183.102)]

소인수분해를 해야 구하지

[익명(49.174)]

그냥 다른 방법 없나싶어서

[익명(183.102)]

n보다 작은 정수 a중에 ab == 1 mod n인 b가 존재하는지 구하면됨 그게그거지만

[수갤러 2(118.235)]

N=pq에 대해서 소인수분해 알면 phi(N)=N-p-q+1을 알수있고 반대로 p+q를 알면 p,q를 구할수있지

[히닝(privacy9962)]

0. 먼저 어렵다는 것이 뭐인지부터 정의해야할텐데, "poly-time algorithm의 존재"라고 해보죠. 이 경우에, 문제 A를 푸는 알고리즘이 주어졌을 때, 이 알고리즘을 가지고 문제 B를 푸는 효율적인 알고리즘을 설계할 수 있으면 (그러니까 poly-time reduction이 존재하면), 문제 B가 문제 A보다 어렵지 않다고 이야기할 수 있겠죠. 1. 쉬운방향: 소인수분해가 주어지면 phi함수 쉽게 계산할 수 있음. => phi함수계산이 소인수분해보다 어렵지 않다. 2. 반대방향의 쉽고 중요한 경우: Semi-prime의 경우는 위에서 이야기한대로 phi함수계산이 소인수분해보다 쉽지 않아서 둘이 동치입니다. 암호학에서 RSA문제와 관련있어서 중요한 케이스라고 할 수 있겠습니다.

[히닝(privacy9962)]

3. 반대방향의 일반적인 경우: Probabilistic Poly-time reduction의 경우 Shoup(
https://shoup.net/ntb/)의
Section 10.4를 참고하세요.
4. Extended Riemann Hypothesis를 가정할 경우에는 Deterministic Poly-time reduction이 존재합니다. Miller의 76년 논문 (
https://www.cs.cmu.edu/~glmiller/Publications/Papers/Mi76.pdf)
5.
요약하자면, phi함수계산과 소인수분해는 (일반적인 n에 대해서도) probabilistic poly-time reduction하에 동치입니다. 즉, 똑같이 어렵습니다.