Алгоритмы нахождения НОД и мультипликативного обратного по модулю.

Алгоритм Евклида.

Алгоритм А. (Алгоритм Евклида в современной редакции). По данным неотрицательным целым числам 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 uv. Если 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, t2u, t3)/2. (В последнем случае t1 + v и t2 – u будут оба четными.)

Y4. [t3 четно?] Если t3 четно, вернуться к шагу Y3.

Y5. [Переустановить max(u3 v3).] Если t3 положительно, присвоить (u1, u2, u3) (t1, t2, t3); иначе присвоить (v1, v2, v3) (vt1, – 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; просмотров: 2334;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.006 сек.