Авторы

Альхалиди А.М.

Аннотация

Задача: вычисления наибольшего общего делителя НОД натуральных чисел представляет собой одну из наиболее распространённых задач, решаемых в современной вычислительной математике и ее приложениях.

В данной статье представлен анализ особенностей реализации и результаты тестирования скорости работы трех алгоритмов вычисления НОД: классического алгоритма Евклида, k-арного алгоритма Соренсона и аппроксимирующего k-арного алгоритма, разработанного вторым из авторов,  выполненные в среде Microsoft Visual Studio на языке C#. Получены качественные и количественные данные об эффективности этих алгоритмов по времени и числу шагов внутри главного цикла.

В заключительной части статьи содержится анализ полученных результатов, их представление на диаграммах, даны рекомендации о выборе параметров методов.

Статья

УДК​​ 511.1

 

ЭФФЕКТИВНЫЕ АЛГОРИТМЫ РАСЧЕТА НОД ДЛЯ ДЛИННЫХ НАТУРАЛЬНЫХ ЧИСЕЛ

 

Альхалиди​​ А.М.​​ 

 

Казанский федеральный университет

 

Задача: вычисления наибольшего общего делителя НОД натуральных чисел представляет собой одну из наиболее распространённых задач, решаемых в современной вычислительной математике и ее приложениях.

В данной статье представлен анализ особенностей реализации и результаты тестирования скорости работы трех алгоритмов вычисления НОД: классического алгоритма Евклида, k-арного алгоритма Соренсона и аппроксимирующего k-арного алгоритма, разработанного вторым из авторов, ​​ выполненные в среде Microsoft Visual Studio на языке C#. Получены качественные и количественные данные об эффективности этих алгоритмов по времени и числу шагов внутри главного цикла.

В заключительной части статьи содержится анализ полученных результатов, их представление на диаграммах, даны рекомендации о выборе параметров методов.

 

1.​​ Введение

 

Как правило, современные криптографические системы работают с длинными числами и предусматривают процедуру вычисления их наибольшего общего делителя НОД [1], [2]. Наиболее распространённой из таких процедур является классический алгоритм Евклида. Однако известны и другие алгоритмы, общей целью создания которых было стремление уменьшить сложность вычисления НОД, сократить время его поиска.

Одним из самых перспективных таких алгоритмов является k-арный алгоритм поиска НОД, опубликованный в 1990-х годах Джонатаном Соренсоном [3]-[5]. По сравнению с классическим алгоритмом Евклида данный алгоритм позволяет заметно снизить сложность вычислений при аккуратном выборе параметра k. В дальнейшем самим Соренсоном и другими учёными было предложено несколько вариантов улучшения и модификации k-арного алгоритма ([6]-[8]).

Одним из них является аппроксимирующий k-арный алгоритм, предложенный Ш.Т. Ишмухаметовым[9].

Целью данной работы является реализация и изучение трех упомянутых алгоритмов вычисления НОД. В трёх последующих разделах рассматривается классический алгоритм Евклида, оригинальная версия k-арного алгоритма и его модификация – аппроксимирующий k-арный алгоритм. Для каждого из алгоритмов приведено теоретическое обоснование, ​​ указана оценка сложности и выполнена реализация алгоритма на языке программирования С#. Далее представлены результаты тестирования каждого из алгоритмов по времени выполнения на числах различной длины. В заключительной части работы проводится сравнение алгоритмов по эффективности времени работы и числу шагов внутри главного цикла.

 

2. Классический алгоритм Евклида

 

На вход алгоритму передаются натуральные числа​​ А и В, A>B. Классический алгоритм Евклида поиска НОД основывается на следующем рекуррентном равенстве:

GCDA,B=GCDB,A mod B.

 

Алгоритм выполняется по шагам, называемым итерациями, в ходе каждой из которых вычисляется остаток​​ С=AmodB, происходит переход к новой паре​​ B, C​​ и вычисление продолжается с новой парой. Вычисление останавливается, когда второй аргумент пары становится равным 0, тогда первый аргумент и есть искомый НОД. Сам алгоритм может быть записан на языке программирования С# следующим образом:

 

publicBigInteger​​ Method(BigInteger​​ number1,​​ BigInteger​​ number2)

{  ​​​​ if​​ (number1 <= 1 || number2 <= 1)​​ 

return​​ 1;

BigInteger​​ R;​​ 

if​​ (number2 > number1) ​​ {  ​​ ​​​​ R = number1;

number1 = number2;

number2 = R;  ​​​​ }

while​​ (number2 != 0)

{ ​​ R = number1 % number2;

number1 = number2;

number2 =​​ R;  ​​​​ }

return​​ number1;  ​​​​ }

 

Оценивая сложность данного алгоритма, заметим, что за каждые две итерации цикла делимое уменьшается, по меньшей мере, в два раза. Это означает, что количество итераций есть​​ O(n), где​​ n​​ – длина входных чисел. Наихудшая оценка достигается на соседних числах ряда Фибоначчи, а среднее числа итераций оценивается величиной ​​ (Dixon[10]):

 

Number of iteration12π2log2B

 

Операцию вычисления остатка​​ A mod B​​ можно выполнить за время​​ O(nlog2n), так что общая производительность алгоритма оценивается величиной​​ O(n2log2n).​​ 

 

3. К-арный алгоритм соренсона

 

Для начала рассмотрим бинарный алгоритм вычисления НОД для пары натуральных чисел. Входными данными этого алгоритма являются нечётные натуральные числа. Обозначим их​​ u,v.​​ Бинарный алгоритм можно представить следующим образом:

 

while (u!= 0) and (v!=0) do:

 ​​ ​​ ​​ ​​​​ if ​​ (u is even) ​​ u:=u/2

 ​​ ​​ ​​ ​​​​ else  ​​ ​​ ​​ ​​ ​​​​ if ​​ (v is even) v:=v/2

 ​​ ​​ ​​ ​​ ​​ ​​ ​​ ​​ ​​ ​​ ​​ ​​ ​​ ​​ ​​ ​​ ​​​​ else ​​ t:= abs(u - v)/2;

if ​​ (u > v) ​​ then ​​ u:=t  ​​​​ else ​​ v:=t;

if ​​ (u = = 0) ​​ then ​​ t:=v  ​​​​ else t:=u;

output(t);

 

Обобщая этот алгоритм, получим​​ k-арный алгоритм поиска НОД. Главная идея итерации​​ k-арного алгоритма состоит в поиске для заданной пары чисел​​ (A,B)​​ целых чисел​​ x,y​​ при небольшом фиксированном​​ k:

 

0<x<k ​​​​ -k<y<k,

 

таких, что выполняется тождество​​ ux+vy0 mod k.​​ Тогда на шаге алгоритма можно перейти от пары​​ (u,v)​​ к новой паре​​ v, w,​​ где​​ ​​ 

(также необходимо сократить​​ w​​ на делители​​ k).

В статье [3] Соренсон предложил выполнять​​ k-арный алгоритм в четыре этапа: этап предварительных вычислений, первое «пробное» деление, основная часть, второе «пробное» деление. Основная часть алгоритма выполняется следующим образом:

 

while(v!= 0){

if ​​​​ (gcd(u,k) > 1)​​ u=u/gcd(u,k);

else ​​ (if ​​ gcd(v,k) > 1) v=v/ gcd(v,k);

else

find integers x, y, ux + vy ≡0 (modk);

w= | ux+ vy|/k;

if ( v > w){u=v ;v=w ;} ​​ else ​​ u= w;

}

return u ;

 

При попытке реализовать​​ k-арный алгоритм становится ясно, что способ выбора целых чисел​​ x​​ и​​ y​​ во многом влияет на его быстродействие. Согласно теореме Соренсона, коэффициенты​​ x​​ и​​ y​​ можно выбрать​​ 0<x+y2k.

Для максимального быстродействия алгоритма выгодно также выбрать число​​ 

x​​ малым и положительным, число​​ y​​ достаточно большим отрицательным.

 

Этап предварительных вычислений:​​ если основание алгоритма​​ k​​ уже выбрано, то для всех натуральных чисел, меньших​​ k, алгоритм предусматривает вычисление их наибольшего общего с числом​​ k​​ делителя и поиск обратного элемента по модулю​​ k​​ (соответствующие таблицы обозначим буквами​​ G,​​ I).

Помимо этого составляется специальная таблица​​ A​​ для быстрого вычисления чисел​​ x​​ и​​ y​​ и таблица для хранения некоторых малых общих делителей чисел​​ u​​ и​​ v, которые отсекаются на стадии пробного деления. Все эти вычисления не зависят от переданных алгоритму чисел​​ u​​ и​​ v, а потому могут быть выполнены заранее и только один раз.

 

Первое «пробное» деление:​​ как было упомянуто ранее, на этой стадии в первую очередь отсекаются все общие делители данных чисел​​ u​​ и​​ v. В дальнейшем они хранятся в отдельной таблице​​ P​​ вплоть до стадии второго пробного деления. Также на этой стадии отсекаются те числа, которые, являясь делителем одного из чисел​​ u​​ и​​ v, не являются делителем другого. Такие делители не участвуют в образовании НОД, поэтому сохранять их не нужно.

Далее выполняется основной цикл, в ходе которого вычисляется число​​ M.​​ Это число не обязательно равно искомому НОД, но равно их кратному, то есть может содержать посторонние множители. Чтобы исключить их, выполняется второе пробное деление.

 

Второе пробное деление:​​ эта стадия алгоритма является завершающей и использует результат, полученный после выполнения основной части алгоритма. ​​ Чтобы избавиться от посторонних множителей, делим​​ M  на все малые делители, находящиеся в заранее составленной таблице, а затем​​ M  умножается на результат первого пробного деления. В итоге получим НОД заданных чисел​​ u​​ и​​ v.

Наиболее значимая часть алгоритма заключается в главном цикле, который представляет основную стадию алгоритма. На языке программирования С# ​​ он может быть записан следующим образом:

 

privatevoidMainLoop(){​​ 

int​​ u1, v1;

int​​ a, b, x;

BigInteger​​ t;

while​​ ((u != 0) && (v != 0))

{  ​​​​ u1 = (int)(u % k); ​​ v1 = (int)(v % k);

if​​ (G[u1] > 1)  ​​​​ u /= G[u1];

else

{ ​​ if​​ (G[v1] > 1)  ​​​​ v /= G[v1];

else

{ ​​ x = (u1 * I[v1]) % k;

if​​ (x < 0)  ​​​​ x += k;

a = A[x];

b = ((-1) * a * x) % k;

t =​​ BigInteger.Abs(a * u + b * v) / k;

if​​ (u > v)  ​​ ​​​​ u = t;

else ​​​​ v = t;  ​​ ​​​​ }}}

}

 

Переменные​​ G,​​ I,​​ A​​ обозначают массивы, размерность которых равна основанию («арности») алгоритма “k”. Эти массивы реализуют таблицы предварительных вычислений.

Добавим реализацию этапов первого и второго пробных делений и получим функцию, реализующую​​ k-арный алгоритм:

 

//​​ Первоепробноеделение

privatevoidTrialDivision1(){ ​​ 

BigIntegerg = 1;

for​​ (inti =1; i<P.Length; i++)

while​​ (u % P[i] == 0 &&v % P[i] == 0)

{  ​​ ​​​​ u /= P[i];v /= P[i];g *= P[i];  ​​ ​​ ​​ ​​​​ }

}

 

//Второепробноеделение

privatevoidTrialDivision2(){

BigInteger​​ t;

if​​ (v == 0)  ​​ ​​​​ t = u;

else ​​ ​​ ​​ ​​​​ t = v;

for​​ (inti = 0; i<P.Length; i++)

while​​ (t % P[i] == 0)

t /= P[i];

g = t * g;  ​​ ​​ ​​ ​​ ​​ ​​​​ 

}

 

// k-арныйалгоритм

publicBigInteger​​ Method(BigInteger​​ number1,​​ BigInteger​​ number2){

if​​ (number1 <= 1 || number2 <= 1)  ​​ ​​​​ return​​ 1;

TrialDivision1();

MainLoop();

TrialDivision2();

returnGetGCD();  ​​ ​​ ​​ ​​ ​​ ​​​​ 

}

 

Сложность​​ k-арного алгоритма для чисел​​ u​​ и​​ v​​ длиной​​ n​​ бит в оптимальном случае выбора параметра​​ k​​ равна согласно оценке Соренсона​​ logk).

 

Список​​ литературы

 

  • Ishmukhametov S.T. ​​ Factorization methods of ​​ natural numbers // Kazan Federal University, Kazan (rus), 2011, P. 189​​ 

  • Ishmukhametov S., Mubarakov B., Mochalov A. ​​ Euclidian algorithm for recurrent sequences, Applied Discrete Mathematics and Heuristic Algorithms // International Scientific Journal. – Samara . – 2015. –V.​​ 1​​ (2). – P. 57–62

  • Sorenson J. An analysis of the generalized binary GCD algorithm / J. Sorenson, A. van derPoorten, A. Stein (Eds.), High Primes and Misdemeanors// Lectures in Honour of Hugh Cowie Williams. – Banff, Alberta, Canada. – AMS Math. Review. – 2004. – V.​​ 41.​​ P. 254–258.

  • Sorenson J. The k-ary GCD algorithm //Computer Sciences Technical Report. – 1990. – 20 p.

  • Sorenson J. Two fast GCD Algorithms // Journal of Algorithms. – 1994. – V.​​ 16(1). – P. 110–144.

  • Weber K. The accelerated integer GCD algorithm, ACM Trans.Math.Software, 21, №1, 1–12 (1995).

  • Jebelean T. A Generalization of the Binary GCD Algorithm, Proc. ofIntern.Symp.onSymb.and Algebra, Comp.(ISSAC’93), 111-116 (1993).

  • Wang X., Pan V. Acceleration of Euclidian Algorithm and rational number reconstruction. Siam J. Comp,v.32 No2, 548-556 (2003).

  • Ishmukhametov S.T. An approximating k-ary GCD Algorithm, Lobachevskii Journal of Mathematics, 2016, Volume 37, Issue 6, pp 723-728

  • DixonJ. ThenumberofstepsintheEuclidean algorithm // Journal of Number Theory. – 1970. – V.2. – P. 414–422.

  • Hardy G. H., Wright E. M. An introduction to the theory of numbers, 4th ed. (Oxford, Calrendon Press, 1959).

©​​ А.М. Альхалиди,​​ 2019

 

 

Скачать PDF

Выходные данные

Альхалиди А.М. Эффективные алгоритмы расчета НОД для длинных натуральных чисел [Электронный ресурс] // Вестник современных исследований. — Электрон. журн. — 2019. — № 8. — Режим доступа: https://orcacenter.ru

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *