Алгоритмы нахождения НОД и мультипликативного обратного по модулю.
Алгоритм Евклида.
Алгоритм А. (Алгоритм Евклида в современной редакции). По данным неотрицательным целым числам u и v этот алгоритм находит их наибольший общий делитель.
A1. [v = 0?] Если v = 0, то выполнение алгоритма заканчивается, а в качестве результата возвращается число u.
A2. [Взять u mod v.] Присвоить r u mod v, u v, v r и вернуться к шагу A1. (В результате выполняемых на этом шаге операций значение v уменьшается, значение НОД(u, v) остается неизменным.)
Бинарный алгоритм НОД.
Алгоритм B. (Бинарный алгоритм нахождения наибольшего общего делителя). По данным неотрицательным целым числам u и v этот алгоритм находит их наибольший общий делитель. (Использует знаковое представление чисел).
B1. [Найти степень 2.] Присвоить k 0, затем повторно присваивать kk + 1, u u / 2, v v / 2 нуль или более раз до тех пор, пока одно или оба числа u и v станут нечетными.
B2. [Начальная установка.] (Исходные значения чисел u и v уже разделены на 2k, и по крайней мере одно из текущих значений нечетно.) Если нечетно u, то присвоить t - v и перейти к шагу B4. В противном случае присвоить tu.
B3. [Уменьшить t наполовину.] (Здесь t четно и не нуль.) Присвоить tt / 2.
B4. [t четно?] Если t четно, то вернуться к шагу B3.
В5. [Установить max(u, v) заново.] Если t > 0, то присвоить u t, в противном случае присвоить v - t. (Большее из чисел u и v заменяется на |t| за исключением, возможно, первого выполнения этого шага.)
B6. [Вычесть.] Присвоить t u – v. Если t ¹ 0, то вернуться к шагу B3. В противном случае алгоритм останавливает выполнение, а на выходе будет u · 2k.
Рис.33. Бинарный алгоритм НОД.
Расширенный алгоритм Евклида.
Алгоритм X. (Обобщенный алгоритм Евклида). Для заданных целых чисел u и v этот алгоритм определяет вектор (u1, u2, u3), такой, что uu1 + vu2 = u3 = НОД(u, v). В процессе вычисления используются вспомогательные векторы (v1, v2, v3), (t1, t2, t3); действия производятся таким образом, что в течение всего процесса вычисления выполняются соотношения
ut1 + vt2 = t3 uu1 + vu2 = u3 uv1 + vv2 = v3.
X1. [Начальная установка.] Присвоить (u1, u2, u3) (1, 0, u), (v1, v2, v3) (0, 1, v).
X2. [v3 = 0?] Если v3 = 0, то выполнение алгоритма заканчивается.
X3. [Разделить и вычесть.] Присвоить , затем присвоить
(t1, t2, t3) (u1, u2, u3) – (v1, v2, v3) · q,
(u1, u2, u3) (v1, v2, v3),
(v1, v2, v3) (t1, t2, t3).
Возвратиться к шагу X2.
Расширенный бинарный алгоритм НОД.
Алгоритм Y. Модификация алгоритма X с использованием принципов алгоритма B. Для заданных целых чисел u и v этот алгоритм определяет вектор (u1, u2, u3), такой, что uu1 + vu2 = u3 = НОД(u, v). В процессе вычисления используются вспомогательные векторы (v1, v2, v3), (t1, t2, t3); в течение всего процесса вычисления так же, как и в X выполняются соотношения
ut1 + vt2 = t3 uu1 + vu2 = u3 uv1 + vv2 = v3.
(Использует знаковое представление чисел).
Y1. [Найти степень 2.] То же, что в шаге B1.
Y2. [Начальная установка.] Присвоить (u1, u2, u3) (1, 0, u), (v1, v2, v3) (v, 1 – u, v). Если число u нечетно, присвоить (t1, t2, t3) (0, –1, –v) и прейти к шагу Y4. В противном случае присвоить (t1, t2, t3) (1, 0, u).
Y3. [Выполнить половинное деление t3.] Если t1 и t2 четны, присвоить (t1, t2, t3) (t1, t2, t3)/2; иначе присвоить (t1, t2, t3) (t1 + v, t2 – u, t3)/2. (В последнем случае t1 + v и t2 – u будут оба четными.)
Y4. [t3 четно?] Если t3 четно, вернуться к шагу Y3.
Y5. [Переустановить max(u3 v3).] Если t3 положительно, присвоить (u1, u2, u3) (t1, t2, t3); иначе присвоить (v1, v2, v3) (v – t1, – u – t2, – t3).
Y6. [Вычесть.] Присвоить (t1, t2, t3) (u1, u2, u3) – (v1, v2, v3). Затем, если t1 £ 0, присвоить (t1, t2) (t1+ v –, t2 – u). Если t3 ¹ 0, вернуться к шагу Y3. В противном случае закончить выполнение алгоритма с результатом, равным (u1, u2, u3 · 2k).
Дата добавления: 2016-02-13; просмотров: 2322;