Euclid호제법 썸네일형 리스트형 'Euclid 호제법'을 이용한 역원 구하기 'Euclid 호제법'은 두 수에 대한 최대공약수를 구하기 위해 사용하는 알고리즘 입니다. 해당 알고리즘을 이용하여 곱셈에 대한 역원 값을 구할 수 있습니다. 먼저 호제법을 시작할 때 두 수가 역원이 존재하는지를 확인해야 합니다. '3 mod 26' 을 계산한다고 가정하여 진행 합니다. [26 * x + 7 * y = 1]의 형태를 만들어야 합니다. 26 = 7 * 3 + 5 7 = 5 * 1 + 2 5 = 2 * 2 +1 - 두 수가 역원이 존재 하는지 점검합니다. 식의 마지막 부분이 1이 나올 때 까지 진행하고 만약 마지막까지 진행 하였을때 1이 아닌 수가 나오면 역원이 존재하지 않는 수 입니다. 5 = 7 - 5 * 1 * 2 + 1 더보기 이전 1 다음