저는 CLR 알고리즘 책을 읽음으로써 RSA 암호학에 대한 숫자 이론을 배우려고합니다. 나는 1 + 로그의 한계를 주장하는 운동 31.2-5를보고 있었다. Φ (b/gcd (a, b)).Euclid의 GCD 알고리즘 실행 시간은 어떻게됩니까?
전체 질문은 :
만약> B> = 0, 호출 EUCLID(a,b)는 최대 1 +는 재귀 호출 b를 Φ를 기록 할 수 있음을 보여준다. 이 바운드를 1 + 로그 Φ (b/gcd (a, b))로 개선하십시오.
누구든지 이것을 표시하는 방법을 알고 있습니까? 이미이 사이트에는 유클리드 알고리즘에 대한 몇 가지 다른 질문과 답변이 있지만이 정확한 대답은없는 것으로 보입니다.
에서 도널드 크 누스에 의해 유클리드 알고리즘의 분석을 참조하십시오. 나는 여전히 두 번째 작업을하고있다.
Euclid 알고리즘의 런타임은 관련된 단계의 수 (책의 pg)이다. k는 필요한 재귀 단계의 수라하자. 케이 찾을 로그 촬영 따라서 B> = F K + 1> = φ의 K -1 B> = φ의 K -1 우리가 로그 φ의 B> = K-1 1 + 로그 φ B> = K 이에 따라 실행 시간이 O (1 + 로그 φ b)
쇼하다 Euclid(a,b) 다음 F(i) 피보나치 번호 번째 i이다 a>=F(n+1) 및 b>=F(n) 이상 N 단계가 걸리는 경우.
이것은 쉽게 유도로 수행 할 수 있습니다.
쇼 유도에 의해 다시 F(n) ≥ φ N-1, 즉. 1 단계 및 2
사용한 결과, 우리는 로그 φ B ≥ N-1 F(n) ≥ φ N-1 양쪽 대수 촬영
≥ ㄴ있다.
따라서 입증 N + 1 ≤ 로그 φ B의 두 번째 부분은 사소 다음
.
EUCLID(ka,kb)의 재귀 호출 수는 EUCLID(a,b)과 동일하며, k은 정수입니다. 따라서, 결합은 1 + log φ (b/gcd (a, b))로 개선된다.
작업의 첫 번째 또는 두 번째 부분에 문제가 있습니까? –
또한 위크 (euclid) 알고리즘은 - 나누기와 나머지가있는 알고리즘 또는 빼기가있는 알고리즘? –
메모리가 작동하면 Knuth (볼륨 2?)는 Euclid의 GCD 알고리즘의 복잡성에 대해 폭넓게 공개합니다. –