Вычисления в конечных полях

Существуют следующие алгоритмы вычисления НОД. 1. Разложение обоих чисел. Если числа а и b заданы, то можно найти все их положительные простые делители. Входящий в оба множества наибольший делитель будет наибольшим общим дели­ телем. Данная процедура проста, но из-за отсутствия простого ал­ горитма разложения целых чисел на простые множители она неэф­ фективна при больших а и h, 2. Двоичный алгоритм Евклида, в котором на каждом шаге числа а п b делятся на 2. 3. Алгоритм Евклида. Разделим а на b с остатком; назовем этот остаток Г]. Если Г| Ф О, то разделим b на г\ с остатком; пусть vi - остаток второго деления. Аналогично, если п Ф О, то разделим Г| на гг и получим новый остаток г^. Таким образом, г'-й цикл алго­ ритма состоит из одного деления с остатком, причем делимое равно остатку, полученному в (/'-2)-м цикле, а делитель - остатку, полу­ ченному в (/-1)-м цикле. Цикл повторяется до тех пор, пока не по­ лучим нулевого остатка; ненулевой наюменьшнй остаток является НОД чисел а и Ь. Для вычисления НОД по алгоритму Евклида необходимо вы­ полнить несколько делений с остатком. Алгоритм Евклида конечен (в последовательности остатков всегда появится нуль), так как; - возможьюе значение остатка при каясдом делении, по крайней мере, на единицу меньше значения остатка предыдущего деления; - значения остатков стремятся к нулю; - ряд конечен: ряд остатков состоит из целых чиеел в интер­ вале [О, Ь]. Алгоритм Евклида обладает следующими особенностями: - максимальное число шагов - rnin(a, /?); - используются только операции деления с остатком; - применим для больших чисел а и /;; - отсутствует необходимость хранения массивов промежу­ точных результатов. 6