Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9 | Следующая страница реферата



b и определим r1,r2,…,rn - последовательность делителей, появляющихся в процессе выполнения шага 1 алгоритма Евклида. Тогда r1 = b,…, 0 ( ri+1 < ri, i = 0,1,…,n - 1.
Пусть также u0 = 1, u1 = 1, uk+1 = uk+uk-1, k ( 1, - последовательность
Фибоначчи. Индукцией по i от i = n - 1 до i = 0 легко доказывается неравенство ri+1 ( un-i. А так как un ( 10(n-1)/5, то имеем неравенства 10p
> b = r1 ( un ( 10(n-1)/5 и n < 5p+1.

Немного подправив алгоритм Евклида, можно достаточно быстро решать сравнения ax ( 1 (mod m) при условии, что (a,b) = 1. Эта задача равносильна поиску целых решений уравнения ax + by = 1.

2.4 Алгоритм решения уравнения ax + by = 1

0. Определим матрицу E =

1. Вычислим r – остаток от деления числа a на b, a = bq + r, 0 ( r < b.

2. Если r = 0, то второй столбец матрицы Е даёт вектор (x y) решений уравнения.

3. Если r ( 0, то заменим матрицу Е матрицей

4. Заменим пару чисел (a,b) парой (b,r) и перейдём к шагу 1.

Если обозначить через Еk матрицу Е, возникающую в процессе работы алгоритма перед шагом 2 после k делений с остатком (шаг 1), то в обозначениях из доказательства теоремы 1 в этот момент выполняется векторное равенство (a,b)(Ek = (rk-1,rk). Его легко доказать индукцией по k. Поскольку числа a и b взаимно просты, имеем rn = 1, и это доказывает, что алгоритм действительно даёт решение уравнения ax + by = 1. Буквой n мы обозначили количество делений с остатком, которое в точности такое же, как и в алгоритме Евклида.

Полиномиальные алгоритмы в теории чисел – большая редкость. Да и оценки сложности алгоритмов чаще всего опираются на какие-либо не доказанные, но правдоподобные гипотезы, обычно относящиеся к аналитической теории чисел.

Для некоторых задач эффективные алгоритмы вообще не известны. Иногда в таких случаях всё же можно предложить последовательность действий, которая,
«если повезёт», быстро приводит к требуемому результату. Существует класс так называемых вероятностных алгоритмов, которые дают правильный результат, но имеют вероятностную оценку времени работы. Обычно работа этих алгоритмов зависит от одного или нескольких параметров. В худшем случае они работают достаточно долго. Но удачный выбор параметра определяет быстрое завершение работы. Такие алгоритмы, если множество «хороших» значений параметров велико, на практике работают достаточно эффективно, хотя и не имеют хороших оценок сложности.

3. Полиномиальная арифметика

Рассмотрим вероятностный алгоритм, позволяющий эффективно находить решения полиномиальных сравнений по простому модулю. Пусть p – простое число, которое предполагается большим, и f(x)(Z[x] – многочлен, степень которого предполагается ограниченной. Задача состоит в отыскании решений сравнения f(x) ( 0 (mod p). (1)
Например, речь может идти о решении квадратичных сравнений, если степень многочлена f(x) равна 2. Другими словами, мы должны отыскать в поле Fp =
Z/pZ все элементы, удовлетворяющие уравнению f(x) = 0.

Согласно малой теореме Ферма, все элементы поля Fp являются однократными корнями многочлена xp - x. Поэтому, вычислив наибольший общий делитель d(x)
= (xp - x, f(x)), мы найдём многочлен d(x), множество корней которого в поле Fp совпадает с множеством корней многочлена f(x), причём все эти корни однократны. Если окажется, что многочлен d(x) имеет нулевую степень, т. е. лежит в поле Fp, это будет означать, что сравнение (1) не имеет решений.

Для вычисления многочлена d(x) удобно сначала вычислить многочлен c(x)(xp (mod f(x)), пользуясь алгоритмом, подобным описанному выше алгоритму возведения в степень (напомним, что число p предполагается большим). А затем с помощью аналога алгоритма Евклида вычислить d(x) =
(c(x) – x, f(x)). Всё это выполняется за полиномиальное количество арифметических операций.

Таким образом, обсуждая далее задачу нахождения решений сравнения (1) мы можем предполагать, что в кольце многочленов Fp[x] справедливо равенство f(x) = (x – a1)(…((x – an), ai(Fp, ai ( aj.

3. 1 Алгоритм нахождения делителей многочлена f(x) в кольце Fp[x]
1. Выберем каким-либо способом элемент ( ( Fp.
2. Вычислим наибольший общий делитель g(x) = ( f(x), (x + ()(p-1)/2 – 1).
3. Если многочлен g(x) окажется собственным делителем f(x), то многочлен f(x) распадается на два множителя и с каждым из них независимо нужно будет проделать все операции, предписываемые настоящим алгоритмом для многочлена f(x).
4. Если окажется, что g(x) = 1 или g(x) = f(x), следует перейти к шагу 1 и, выбрав новое значение (, продолжить выполнение алгоритма.

Количество операций на шаге 2 оценивается величиной O(ln p), если вычисления проводить так, как это указывалось выше при нахождении d(x).
Выясним теперь, сколь долго придётся выбирать числа (, пока на шаге 2 не будет найден собственный делитель f(x).

Количество решений уравнения (t + a1)(p – 1)/2 = (t + a2)(p – 1)/2 в поле Fp не превосходит (p-3)/2. Это означает, что подмножество D ( Fp, состоящее из элементов (, удовлетворяющих условиям

(( + a1)(p – 1)/ 2 ( (( + a2)(p – 1)/ 2, ( ( -a1, ( ( -a2, состоит не менее чем (p – 1)/2 из элементов. Учитывая теперь, что каждый ненулевой элемент b(Fp удовлетворяет одному из равенств b(p – 1)/2 = 1, либо b(p – 1)/2 = –1, заключаем, что для ( ( D одно из чисел a1, a2 будет корнем многочлена (x + () (p – 1)/2 – 1, а другое – нет. Для таких элементов ( многочлен, определённый на шаге 2 алгоритма, будет собственным делителем многочлена f(x).

Итак, существует не менее (p –1)/2 «удачных» выборов элемента (, при которых на шаге 2 алгоритма многочлен f(x) распадается на два собственных множителя. Следовательно, при «случайном» выборе элемента ( ( Fp, вероятность того, что многочлен не разложится на множители после k повторений шагов алгоритма 1-4, не превосходит 2-k. Вероятность с ростом k убывает очень быстро. И действительно, на практике этот алгоритм работает достаточно эффективно.

Заметим, что при оценке вероятности мы использовали только два корня многочлена f(x). При n > 2 эта вероятность, конечно, ещё меньше. Более тонкий анализ с использованием оценок А. Вейля для сумм характеров показывает, что вероятность для многочлена f(x) не распасться на множители при однократном проходе шагов алгоритма 1-4 не превосходит 2-n + O(p-1/2).
Здесь постоянная в O(.) зависит от n. В настоящее время известно элементарное доказательство оценки А. Вейля.

Если в сравнении (1) заменить простой модуль p составным модулем m, то задача нахождения решений соответствующего сравнения становится намного более сложной. Известные алгоритмы её решения основаны на сведении сравнения к совокупности сравнений (1) по простым модулям – делителям m, и, следовательно, они требуют разложения числа m на простые сомножители, что, как уже указывалось, является достаточно трудоёмкой задачей.

3.2 Произведение и возведение в степень многочленов, заданных массивами

Условимся представлять многочлены массивами, индексированными, начиная с 0, в которых элемент с индексом i означает коэффициент многочлена степени i

Рекомендуем скачать другие рефераты по теме: доклад 6 класс, здоровый образ жизни реферат.

Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9 | Следующая страница реферата