나는 정말로 답을 모른다는 것을 인정해야합니다 (소리가 놀랍습니다). 나는이 축소를 스스로 발견하거나 재발견했다.

나는 이산 로그 알고리즘을 먼저 발견하고 팩토링 알고리즘을 두 번째로 발견했기 때문에 이산 로그에서 주기성이 유용하다는 것을 알았습니다. 나는 인수 분해가 동일한 제곱 (mod N)을 가진 두 개의 같지 않은 숫자를 찾는 것과 동등하다는 것을 알고있었습니다. 이것은 2 차 체 알고리즘의 기초입니다. 또한 Euler 함수 를 찾는 팩토링이 줄어드는 것을 보았습니다 .ϕ

$\phi$

주문 찾기에 대한이 질문의 축소를 생각해 냈지만 어렵지는 않습니다. 따라서이 축소에 대해 설명하는 다른 논문이 있으면 놀랍지 않습니다. 그러나 이것이 널리 알려진 “민속 결과”라고 생각하지 않습니다. 누군가가 그것을 발견 했더라도, 양자 컴퓨팅 이전에 왜 누군가가 주문 찾기 (고전의 컴퓨터에서 기하 급수적으로)의 문제에 대한 팩터링을 줄이는 것에 관심이 있을까요?

편집 : 주문 찾기는 오라클 환경에서만 기하 급수적으로 증가합니다. 위해 찾는 모듈 인수 분해에 해당 , 다른 대답이 지적 하듯이, 헤더 WOLL에 의해 이전에 증명되었다.N

$N$N

$N$

답변