Главная | Обратная связь

Элементы теории чисел

Каноническим разложением числа называется разложение его на простые сомножители в виде , где - все различные простые делители числа , а - целые положительные числа.

Функцией Эйлера называется, отображение ,

- каноническое разложение .

Например, , , .

Числа и называются взаимно простыми, если у них нет общих делителей больших 1, т.е. .

Функция Эйлера от числа равна числу чисел меньших и взаимно простых с m [6].

Для взаимно простых и верно равенство [6].

Число примитивных многочленов степени над полем равно [12].

Теорема Эйлера-Ферма¹⁾. Для взаимно простых и имеет место соотношение .

Для решения уравнения , где , можно использовать теорему Эйлера-Ферма, т.е. , но это весьма трудоемкий способ. Получим решения искомого уравнения через формулу для решения эквивалентного уравнения .

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

Для чисел и последовательность шагов алгоритма Евклида выглядит как

где - остатки. Разложение в цепную дробь по последовательности частных

имеет вид

Обозначим за дробь, получаемую из приведенной цепной дроби отбрасыванием членов с индексами, большими . Например, , и т.д. Числитель, , и знаменатель, , можно вычислять рекуррентно по следующим формулам:

По определению и . Кроме того,

или

что означает

т.е. и .

Процесс получения числителей и знаменателей удобно оформить в виде таблицы:

Таким образом, корни уравнения вычисляются по формуле .

Пример. Решить уравнение . Сначала по алгоритму Евклида получается следующая цепочка соотношений:

Затем составляется таблица для вычисления

Таким образом, искомый равен 151925.

Гипотеза. Задача разложения целого числа с заданным числом разрядов на множители является труднорешаемой

Задача называется труднорешаемой, если время ее решения зависит от объема входных данных по экспоненциальному закону и не может быть сведено к полиномиальному}.

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

Эта гипотеза лежит в основе методов Диффи-Хеллмана.