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

[pic].
Пусть также [pic], [pic], [pic], [pic], - последовательность Фибоначчи.
Индукцией по [pic] от [pic] до [pic] легко доказывается неравенство [pic].
А так как [pic], то имеем неравенства [pic] и [pic].

Немного подправив алгоритм Евклида, можно достаточно быстро решать сравнения [pic] при условии, что [pic]. Эта задача равносильна поиску целых решений уравнения [pic].

2.2.3. Алгоритм решения уравнения [pic]

0) Определим матрицу [pic].

1) Вычислим [pic] - остаток от деления числа [pic] на [pic], [pic],
[pic].
Если [pic], то второй столбец матрицы [pic] даёт вектор [pic]

решений уравнения.
3) Если [pic], то заменим матрицу [pic] матрицей [pic].
4) Заменим пару чисел [pic] парой [pic] и перейдем к шагу 1.

Если обозначить через [pic] матрицу [pic], возникающую в процессе работы алгоритма перед шагом 2 после [pic] делений с остатком (шаг 1), то в обозначениях из доказательства теоремы 1 в этот момент выполняется векторное равенство [pic]. Поскольку числа [pic] и [pic] взаимно просты, имеем [pic], и это доказывает, что алгоритм действительно даёт решение уравнения [pic]. Буквой [pic] мы обозначили количество делений с остатком, которое в точности такое же, как и в алгоритме Евклида.

Три приведённых выше алгоритма относятся к разряду так называемых полиномиальных алгоритмов. Это название носят алгоритмы, сложность которых оценивается сверху степенным образом в зависимости от длины записи входящих чисел. Если наибольшее из чисел, подаваемых на вход алгоритма, не превосходит [pic], то сложность алгоритмов этого типа оценивается величиной
[pic], где [pic] - некоторая абсолютная постоянная. Во всех приведённых выше примерах [pic].

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

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

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

Как пример, рассмотрим вероятностный алгоритм, позволяющий эффективно находить решения полиномиальных сравнений по простому модулю. Пусть [pic] — простое число, которое предполагается большим, и [pic] - многочлен, степень которого предполагается ограниченной. Задача состоит в отыскании решений сравнения

[pic].

(8)
Например, речь может идти о решении квадратичных сравнений, если степень многочлена [pic] равна 2. Другими словами, мы должны отыскать в поле [pic] все элементы, удовлетворяющие уравнению [pic].

Согласно малой теореме Ферма, все элементы поля [pic] являются однократными корнями многочлена [pic]. Поэтому, вычислив наибольший общий делитель [pic], мы найдем многочлен [pic], множество корней которого в поле
[pic] совпадает с множеством корней многочлена [pic], причем все эти корни однократны. Если окажется, что многочлен [pic] имеет нулевую степень, т. е. лежит в поле [pic], это будет означать, что сравнение (8) не имеет решений.

Для вычисления многочлена [pic] удобно сначала вычислить многочлен
[pic], пользуясь алгоритмом, подобным описанному выше алгоритму возведения в степень (напомним, что число [pic] предполагается большим). А затем с помощью аналога алгоритма Евклида вычислить [pic]. Всё это выполняется за полиномиальное количество арифметических операций.

Таким образом, обсуждая далее задачу нахождения решений сравнения
(8), мы можем предполагать, что в кольце многочленов [pic] справедливо равенство

[pic]

2.2.4. Алгоритм нахождения делителей многочлена [pic] в кольце [pic]

1) Выберем каким-либо способом элемент [pic].
2) Вычислим наибольший общий делитель [pic].
3) Если многочлен [pic] окажется собственным делителем [pic], то многочлен

[pic] распадётся на два множителя и с каждым из них независимо нужно будет проделать все операции, предписываемые настоящим алгоритмом для многочлена [pic].

4) Если окажется, что [pic] или [pic], следует перейти к шагу 1 и. выбрав новое значение [pic], продолжить выполнение алгоритма.

Количество операций на шаге 2 оценивается величиной [pic], если вычисления проводить так, как это указывалось выше при нахождении [pic].
Выясним теперь, сколь долго придётся выбирать числа [pic], пока на шаге 2 не будет найден собственный делитель [pic].
Количество решений уравнения [pic] в поле [pic] не превосходит [pic]. Это означает, что подмножество [pic] элементов [pic], удовлетворяющих условиям

[pic], состоит не менее, чем из [pic] элементов. Учитывая теперь, что каждый ненулевой элемент [pic] удовлетворяет одному из равенств [pic], либо [pic], заключаем, что для [pic] одно из чисел [pic] будет корнем многочлена [pic], а другое - нет. Для таких элементов [pic] многочлен [pic], определённый на шаге 2 алгоритма, будет собственным делителем многочлена [pic].

Итак, существует не менее [pic] «удачных» выборов элемента [pic], при которых на шаге 2 алгоритма многочлен [pic] распадётся на два собственных множителя. Следовательно, при «случайном» выборе элемента [pic], вероятность того, что многочлен не разложится на множители после [pic] повторений шагов алгоритма 1-4. не превосходит [pic]. Вероятность с ростом
[pic] убывает очень быстро. И действительно, на практике этот алгоритм работает достаточно эффективно.

Рекомендуем скачать другие рефераты по теме: оценка реферата, диплом на тему.





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