이것은 연구 질문보다 “역사적 질문”이지만, Peter Shor가 처음 발견 한 인수 분해에 대한 Shor의 알고리즘에서 주문을 찾기위한 고전적인 축소입니까, 아니면 이전에 알려졌습니까? 쇼어 이전의 감축을 설명하는 논문이 있습니까, 아니면 간단히 “민간 결과”입니까? 아니면 같은 논문에서 또 다른 획기적인 것일까 요?
답변
나는 정말로 답을 모른다는 것을 인정해야합니다 (소리가 놀랍습니다). 나는이 축소를 스스로 발견하거나 재발견했다.
나는 이산 로그 알고리즘을 먼저 발견하고 팩토링 알고리즘을 두 번째로 발견했기 때문에 이산 로그에서 주기성이 유용하다는 것을 알았습니다. 나는 인수 분해가 동일한 제곱 (mod N)을 가진 두 개의 같지 않은 숫자를 찾는 것과 동등하다는 것을 알고있었습니다. 이것은 2 차 체 알고리즘의 기초입니다. 또한 Euler 함수 를 찾는 팩토링이 줄어드는 것을 보았습니다 .
ϕ주문 찾기에 대한이 질문의 축소를 생각해 냈지만 어렵지는 않습니다. 따라서이 축소에 대해 설명하는 다른 논문이 있으면 놀랍지 않습니다. 그러나 이것이 널리 알려진 “민속 결과”라고 생각하지 않습니다. 누군가가 그것을 발견 했더라도, 양자 컴퓨팅 이전에 왜 누군가가 주문 찾기 (고전의 컴퓨터에서 기하 급수적으로)의 문제에 대한 팩터링을 줄이는 것에 관심이 있을까요?
편집 : 주문 찾기는 오라클 환경에서만 기하 급수적으로 증가합니다. 위해 찾는 모듈 인수 분해에 해당 , 다른 대답이 지적 하듯이, 헤더 WOLL에 의해 이전에 증명되었다.
NN
답변
인수 분해에서 주문 찾기 (mod N) 로의 무작위 감소는 1970 년대 후반과 1980 년대 초에 수 이론 알고리즘에서 일하는 사람들에게 매우 잘 알려져있었습니다. 실제로, 그것은 헤더 월 (Herhead Woll)의 논문, 수 이론 문제, 정보 및 계산 72 (1987) 167-179 , 에릭 바흐 (Eric Bach ) 중 축소 , 그리고 그 전에 그것을 알고있었습니다.
Peter Shor가 주문 검색이 “고전 컴퓨터에서 기하 급수적으로 증가 할 것”이라고 말한 이유가 궁금합니다. N의 인수 분해와 (서브 지수 시간으로 계산할 수있는)를 알고 하나의 주 전력마다 모듈로 작동하면 순서를 찾을 수 있습니다.
φ(N)