Дипломная работа: Теория остатков

525|

462 |

63

3

231

2

Запись того же самого в виде цепочки равенств:

525 = 231 · 2 + 63

231 = 63 · 3 + 42

63 = 42 · 1 + 21

42 = 21 · 2

Таким образом, (525, 231) = 21. Линейное представление наибольшего общего делителя:

21 = 63 - 42 · 1 = 63 - (231 - 63 · 3) · 1 =

= 525 - 231 · 2 - (231 - (525 - 231 · 2) · 3) =

= 525 · 4 - 231 · 9,

и наши пресловутые u и v из Z равны, соответственно, 4 и - 9.

Приступим теперь к исполнению второй части названия этого пункта - анализу алгоритма Евклида. Нас будет интересовать наихудший случай - когда алгоритм работает особенно долго? Спросим точнее: какие два наименьших числа надо засунуть в алгоритм Евклида, чтобы он работал в точности заданное число шагов? Ответ на этот вопрос дает

Теорема (Ламэ, 1845 г.). Пусть n N , и пусть a > b > 0 такие, что алгоритму Евклида для обработки а и b необходимо выполнить точно n шагов (делений с остатком), причем а - наименьшее с таким свойством. Тогда а = _{n +2} , b = _{n +1} , где _k - k- ое число Фибоначчи.

Следствие. Если натуральные числа a и b не превосходят N N , то число шагов (операций деления с остатком), необходимых алгоритму Евклида для обработки a и b не превышает log _Ф ( 5 N ) - 2, где - верхнее целое , = (1 + 5)/2 - больший корень характеристического уравнения последовательности Фибоначчи.

Доказательство. Максимальное число шагов n достигается при а = _{n +2} , b = _{n +1} , где n - наибольший номер такой, что _{n +2} < N . Рассматривая формулу для n -ого члена последовательности Фибоначчи, легко понять, что _{n +2} - ближайшее целое к (1/ 5) ^{n +2} . Значит (1/ 5) ^{n +2} < N , следовательно, n +2 < log _Ф ( 5 N ), откуда моментально даже n < log _Ф ( 5 N ) - 3 (именно "минус три", ведь рассматривается верхнее целое).

log _Ф ( 5 N ) 4,785 · lg N + 1,672, поэтому, например, с любой парой чисел, меньших миллиона, алгоритм Евклида разбирается не более, чем за 4,785 · 6 + 1,672 - 3 = 31 - 3 = 28 шагов.

Листинг алгоритма Евклида на языке С

// ?????????? ???????? ??????? ??? ?????? ??????????? ?????? // ???????? gcd = ???(u,v) ????? ????????????? ????? u ? v // ? ????????????? a ? b ????????? a*u + b*v = gcd// ??? ????? ?????????? ???? long // ??????????? ?????????? ?????? ????????? ??????#define isEven(x) ((x & 0x01L) == 0) // x - ???????#define isOdd(x) ((x & 0x01L)) // x - ?????????#define swap(x,y) (x ^= y, y ^= x, x ^= y) // ????? ???????? x ? y void GenEuclid(long *u, long *v, long *a, long *b, long *gcd){int k; // ???????? ??????long a1, b1, g1; // ??????????????? ?????????? // ???????? ????????????, ??? u > v, ???? u < v, ?? ??? ??????????????if (*u < *v) swap(*u, *v);// ???? u = n * 2^k1 ??? v = m * 2^k2, ?? ????? ??????? ???// ?????????? ?????????? u = u/(2^k), v = v/(2^k),// ??? k - ??????????? ?? k1, k2. ?????????? k ??????????.for (k = 0; isEven(*u) && isEven(*v); ++k){ *u >>= 1; *v >>= 1;}// ??????? ????????? ????????*a = 1; *b = 0; *gcd = *u; a1 = *v; b1 = *u - 1; g1 = *v;do { do { if (isEven(*gcd)){ if (isOdd(*a) || isOdd(*b)){ *a += *v; *b += *u; } *a >>= 1; *b >>= 1; *gcd >>= 1; } if (isEven(g1) || *gcd < g1){ swap(*a, a1); swap(*b, b1); swap(*gcd, g1); } } while (isEven(*gcd)); while(*a < a1 || *b < b1){ *a += *v; *b += *u; } *a -= a1; *b -= b1; *gcd -= g1;} while (g1 > 0);while (*a >= *v && *b >= *u){ *a -= *v; *b -= *u;}// ?????????? ????????? ????????????? ????????? // ?? ??????????? ????? ????????? 2^k*a <<= k; *b <<= k; *gcd <<= k;}

Расширенный алгоритм Евклида и соотношение Безу

Формулы для r_i могут быть переписаны следующим образом:

r ₁ = a + b ( - q ₀ )

r ₂ = b − r ₁ q ₁ = a ( − q ₁ ) + b (1 + q ₁ q ₀ )

(a ,b ) = r_n = as + bt

здесь s и t целые. Это представление наибольшего общего делителя называется соотношением Безу , а числа s и t — коэффициентами Безу . Соотношение Безу является ключевым в доказательстве основной теоремы арифметики.

1.3 Применения алгоритма Евклида