현재 라고 하자. 이면 의 마지막 이진 비트는 이고 이전 쌍은 이다. 이면 마지막 비트는 이고 이전 쌍은 이다.
한 번씩 빼면 값이 매우 큰 경우 느리다. 일 때 만큼 한 번에 빼면 뒤의 비트 개를 제거한 것과 같다. 도 대칭적으로 처리한다. 서로소이므로 과정은 에서 끝난다.
제거한 비트 구간을 역순으로 붙인다. 현재 값이 일 때 을 개 붙이면 , 을 개 붙이면 이 된다. 모든 연산은 으로 나눈 나머지로 계산한다. 유클리드 알고리즘과 같은 횟수의 단계만 필요하므로 시간 복잡도는 이다.
