무차별 대입과 GCD를 찾는 유클리드 알고리즘의 차이

Question

GCD가 무차별 공격으로 간주되지만 유클리드 알고리즘이 아닌 연속 정수 검사 알고리즘이 왜 그렇습니까? 나는 그저 혼란 스럽다. 우리가 하나 하나씩 확인하고 있기 때문입니까?

Answer 1

무차별 강제 검색은 모든 (합리적) 가능성을 시도하는 것을 포함합니다. Euclid의 알고리즘은 이러한 가능성의 아주 작은 부분 만 검사합니다.

Answer 2

알고리즘 브루트 - 힘 알고리즘은 시도 할 수있는 모든 후보 솔루션을 시도하고 어느 것이 적합한 지 확인한 다음 그 결과를 해답으로 반환합니다. 예를 들어, 무차별 대입 GCD 알고리즘은 두 숫자 중 작은 숫자로 시작하여 1까지 계속 진행하면서 모든 가능성을 하나씩 검토하면서 진행합니다.

반면에, 유클리드 알고리즘은 하나씩 나아 가지 않습니다. 점프가 일어나기도하고 때로는 중요한 점도 있습니다. 또한 각 단계에서 GCD 문제에 대한 해결책이 될 가능성이있는 각 번호를 확인하지는 않습니다. 종료 조건은 현재 후보가 문제의 해결책인지 확인하는 일반적인 무차별 대치 솔루션과는 다소 다르지만, 대답이 "예"일 때 중지하십시오. 유클리드 알고리즘은 다른 조건, 즉 b != 0을 검사하여 계속할지 여부를 결정합니다.

유클리드 알고리즘과 무차별 알고리즘은이 두 가지 차이 (큰 단계와 다른 정지 조건)로 인해 서로 다릅니다.