Элементы теории чисел
При больших значениях т задача факторизации является трудноразрешимой. Этот факт используется для обоснования стойкости ряда криптографических схем, включая схему асимметричного шифрования RSA. В следующей главе мы приведем примеры подобных схем, а позднее, в главе 13, рассмотрим некоторые методы решения задачи факторизации. Для дальнейшего изложения нам потребуются некоторые сведения… Читать ещё >
Элементы теории чисел (реферат, курсовая, диплом, контрольная)
В результате изучения данной главы студент должен: знать
- •основы теории чисел;
- •основные теоретико-числовые алгоритмы;
- •основные теоретико-числовые функции; уметь
- •применять алгоритм Эвклида;
- •решать сравнения первой степени; владеть
- •методами решения сравнений;
- •основными методами применения эллиптических кривых.
Для дальнейшего изложения нам потребуются некоторые сведения из элементарной теории чисел. Мы вынесли эти сведения в отдельную главу и сформулировали ряд определений, утверждений и теорем, доказательства которых хорошо известны и могут быть найдены, например, в книгах [ 1, 2, 3].
Определение 9.1. Натуральное число р > 1 называется простым, если оно не имеет других натуральных делителей, отличных от 1 и р.
Натуральное число т называется составным, если оно имеет делитель, отличный от 1 и т.
В качестве простого упражнения читателю предлагается доказать следующее утверждение.
Лемма 9.1. Наименьший отличный от единицы натуральный делитель р составного числа т > 1 есть простое число, удовлетворяющее неравенству р ^ у/т.
Важную роль играет следующее утверждение, которое принято называть основной теоремой арифметики.
Теорема 9.1 (см. [1, гл. 2]). Пусть т > 1 — натуральное число. Можно представить т. в виде произведения простых сомножителей единственным образом, с точностью до перестановки сомножителей, то есть 
где pi,… , рг — различные простые числа, а а,…, аг — некоторые натуральные числа.
Определение 9.2. Равенство (9.1) называется каноническим разложением натурального числа т > 1 на простые сомножители.
Задача нахождения для заданного составного числа т его канонического разложения на простые сомножители называется задачей факторизации.
При больших значениях т задача факторизации является трудноразрешимой. Этот факт используется для обоснования стойкости ряда криптографических схем, включая схему асимметричного шифрования RSA. В следующей главе мы приведем примеры подобных схем, а позднее, в главе 13, рассмотрим некоторые методы решения задачи факторизации.