[일반] rsa 질문

[익명(220.79)]

rsa에서

두 소수의 곱 n이 주어졌을때 n을 소인수분해하지 않고 phi(n)을 계산하기 어려운 이유가 뭔가요?

n이 소인수분해되면 phi(n)은 계산 되고

phi(n)이 계산되면 n의 소인수 p,q를 찾을 수 있다는 설명이 있는데

이게 왜

n을 소인수분해하지 않고 phi(n)을 계산하기 어렵다는 것의 근거가 되는지 궁금해요

[ㅇ?(223.38)]

그게 근거라고 써져있을리는 절대없고 별개로 그냥 phi(n)자체 계산이 어려운거 아님?

[익명(27.35)]

1부터 n까지 n과 서로소인 거 무식하게 다 세봐야 돼서 그런 게 아닐까

[ns(qwer2357)]

phi(n)을 쉽게 구하는 알고리즘이 있으면 그 뒤에다 책의 알고리즘을 덧붙이면 n이 소인수분해되잖아. 그럼 우리다 n을 빠르게 소인수분해 못한다면 phi(n)도 빠르게 못구하는거.

[익명(118.235)]

정확하게는 phi(n)을 구하는거랑 소인수분해하는거랑 동등하게 어려운 문제라는거임 그니까 [소인수분해를 해야만 phi(n)을 계산할수있다] 이게 아니라 [phi(n)을 구하면 소인수분해를 할 수 있다]는거

[익명(220.79)]

감사합니다