Алгоритм Ферма - Лекция, раздел Математика, Материалы лекций Математические основы криптологии
Алгоритм Ферма Похож На Алгоритм Бухштаба И Является Эффектив...
Алгоритм Ферма похож на алгоритм Бухштаба и является эффективным, если у раскладываемого числа n есть делитель (который
может и не быть простым числом), незначительно превосходящий n .
Пусть число n является нечетным. Алгоритм заключается в том, чтобы представить число n в виде
n = x2 − y2 = (x − y)(x + y),
где x, y - неотрицательные целые числа. Если числа x и y найдены, то
(x − y) и (x + y) являются простыми делителями числа n.
Если число y = 0, то делителем числа n является n .
Если известно y и y > 0, можно вычислить число x как x =
n +y2 ;
полученное x будет больше n .
Описание алгоритма.
На вход подается нечетное натуральное число n.
На выходе ожидается: 2 сомножителя числа n или сообщение о невозможности разложить число n с помощью алгоритма.
1. Пусть x = ] n [, где ]…[ - операция взятия целой части от аргумента. Если n = x2, то x является делителем числа n; выход.
2. Выполнить x = x + 1.
3. Если выполняется равенство
раскладывается на множители, выход.
x =(n +1) , то число n - простое и не
2
4. Вычислить y =
x 2 -n .
5. Если ] y2[ = (x2 - n), то n раскладывается на множители (x − y) и
(x + y), выход.
6. Иначе перейти к шагу 2.
Покажем истинность шага 3 алгоритма Ферма. Предположим, что число n можно представить в виде произведения n = ab, где a ≤ b. Алгоритм
ищет такие целые числа x и y, которые удовлетворяют равенству
n = ab = (x2−y2) =
= (x−y)(x+y).
Так как a = (x-y), b = (x+y) и a ≤ b, то (x-y) ≤ (x+y). Выразим неизвестные
x и y из системы
ìa =x -y
í
îb =x +y
ìx =(b +a) / 2
=> í
îy =(b -a) / 2
. Действительно, подставляя
значения x и y в выражение (x2 - y2), получим
0.25(b + a)2 + 0.25(b - a)2 = 0.25(b 2+ 2ab + a 2- b 2+ 2ab - a 2) = ab , что равно
n.
Если число n - нечетное (так как предположительно n - простое), то его
2 сомножителя a и b также являются нечетными числами. Так как сумма и разность двух нечетных чисел являются четными, то числа (a + b) и (a − b) - четные.
Если n является простым числом, то единственными его сомножителями являются числа a = 1 и b = n. Тогда x = (a + b)/2 = (n + 1)/2 и
y = (n − 1)/2.
Так как (x2-y2) = n, то y2 = x2 - n или y =
x 2 -n . Покажем, что при
указанных условиях нацело извлекается квадратный корень, если
x = (n + 1)/2:
y = x 2 -n =
0.25(n +1)2 -n =0.5
n2 +2n +1 -4n =
=0.5
n2 -2n +1 =0.5
(n -1)2
=0.5(n -1) .
Пример 1.6. Разложим число n = 1472861 на множители.
Присвоим x = ] n [ = 1213. При этом x2 < n, то есть
12132 = 1471369 < 1472861. Увеличим x на единицу. Данный процесс будет
продолжен до тех пор, пока число y =
x 2 -n
не станет целым или не
выполнится равенство
x =(n +1) . Выражение
2
(n + 1)
2
равно 736431.
Шаги работы алгоритма представим в виде трассировочной табл. 1.6.
Таблица 1.6. Трассировочная таблица
|
№ шага
|
x
| x =(n +1)
|
y = x 2 - n
|
y ÎZ?
|
|
|
| нет
| 9351/2 ≈ 30.57
| нет
|
|
|
| нет
|
| да
|
На втором шаге было получено целое число y. Искомыми числами x и y
являются 1215 и 58. Тогда множителями числа n являются числа
(x − y) = 1157 и (x + y) = 1273.
Дополнительные примеры для решения (решить обоими способами):
1. Разложите число n = 391 на 2 сомножителя. (n1=17 и n2=23).
3. Разложите число n = 111 на 2 сомножителя. (n1=3 и n2=37).
4. Разложите число n = 115 на 2 сомножителя. (n1=5 и n2=23).
5. Рассмотрите примеры 1.4-1.6 с помощью алгоритма Ферма. Вопросы для самопроверки.
1. В чем заключается идея алгоритма Бухштаба?
2. В чем заключается идея алгоритма Ферма?
3. Какие общие арифметические операции присутствуют в обоих алгоритмах?
4. Поясните, для чего используется арифметическая прогрессия в алгоритме
Бухштаба?
5. Почему, при выполнении равенства простое?
x = (n + 1) / 2 , принимается, что число n -
6. Для каких чисел применимы алгоритмы?
7. В каких диапазонах ищутся результаты разложения?
Все темы данного раздела:
Лекция№1
Криптология состоит из двух направлений: криптографии и криптоанализа.
Криптография – наука о способах преобразования (шифрования)
Асимметричное шифрование.
Алгоритм RSA (Revest, Shamir, Adelman) 1978г.
e, n
А, М В
Алгоритм передачи секретного ключа по открытому каналу
В середине 70-х годов произошел настоящий прорыв в современной
криптографии – появление асимметричных криптосистем, которые не требовали передачи секретного ключа между сторонами. Здесь от
Алгоритм Евклида
Алгоритм Евклида дает правило вычисления наибольшего общего делителя
(НОД) 2-х натуральных чисел. (a,b)= d , где d – НОД НОК – наименьшее общее кратное
Алгоритм РАЕ Кнута
Свойства делимости целых чисел
Два числа a и b называются взаимно простыми если их НОД = 1
(a1,a2,….,an)= НОД
(a1,a2) = d1
(a3,d1) = d2
Свойства делимости целых чисел
Свойства приведены без доказательства.
1)Свойство дистрибутивности
Пусть заданны три натуральных числа a,b,
Простые числа
1)- каноническое разложение
&nb
Получение простых чисел.
По мере того как мы будем изучать курс «Математические основы криптологии» мы будем возвращаться к этой теме.
Задача получение простых чисел во многом зависит от того как с
Проверка простоты чисел Мерсенна
Числами Мерсенна называются числа вида М(p) = 2p - 1, pÎN.
Задача для чисел Мерсенна - поиск в ряду э
Sp-2 mod M(p) ≡ 0, т.е. остаток равен 0.
Поясним, каким образом задается ряд Sk. Члены последовательности
Алгоритм Бухштаба
Данный алгоритм приведен из книги Бухштаба А.А. "Теория чисел" [4]. Пусть задано натуральное нечетное число n, n ≥ 9, которое необходимо разложить на 2
Функция Эйлера
Имеется целое, положительное число m. Оно может быть как составным, так и простым.
Функцию Эйлера принято обозначать, практически во всех учебниках как:
Мультипликативная функция
Имеем два натуральных числа a и b, если они взаимно просты, то мультипликативная функция устанавливает число взаимно простых чисел, для произведение двух взаимно простых чисел по фо
Числовая функция
Это функция устанавливающая целую часть от некоторого рационального числа
[a] – обозначение
может быть как положительное, так и отрицательное число
Для возведение натуральных чисел по модулю в большие степени
Функция Эйлера может быть использована для возведение больших чисел в большую степень по модулю.
Имеется целое число
Возведение натуральных чисел по модулю в большие степени по схеме Горнера
Пусть задано выражение вида
y = a x mod m , (1.1)
где a ÎN - основание степени,
Сравнимость по модулю. Модулярная арифметика
Понятие «модулярная арифметика» ввел немецкий ученый Гаусс.
Модульная арифметика аналогична обычной арифметике: она коммутативна, ассоциатив
Свойства операций сравнения
В криптографии существуют шифры и по простому модулю и по составному модулю.
Нужно знать когда применять простой модуль, а когда состав
Доказательство теоремы Эйлера
Пусть даны m и φ(m)=k
Имеем число a, причем (a,m)=1
Берем ряд натуральных чисел:
a1
Модулярная арифметика (продолжение) Квадратичные вычеты Степенные вычеты
Продолжим исследовать вычеты.
Широкое применение в криптографии нашла формула:
xn ≡ a mod m, n=2
xn ≡ a mod p – квадратичный выч
ЭЛЕМЕНТЫ ТЕОРИИ КОНЕЧНОГО ПОЛЯ Простейшие алгебраические структуры
Под алгебраической структурой будем понимать некоторое множество
S с одной или несколькими операциями на нем.
Пусть S х S обозначае
Кольца и поля
Алгебраические структуры с двумя бинарными операциями - сложение и умножение.
Определение 1.7. Множество S называется кольцом, е
Характеристика поля
Определение 1.12. Если в поле Fq все ненулевые элементы имеют аддитивный порядок k, то говорят, что поле Fq имеет характеристику k. Обозначение. р - простое число.
Вычисление обратных элементов
В арифметике действительных чисел просто вычислить обратную величину a−1 для ненулевого a:
a-1 = 1/a или a? a-1 = 1.
Многочлены над конечным полем
Onределенuе 1.13. Многочленом (относительно х) над полем GF(p)
m
Для любого простого р и nÎN существует хотя бы один неприводимый над полем GF(p) многочлен степени n [9].
Любой неприводимый над полем GF(p) многочлен степени п делит
многочлен
x pm - x
(также и мног
Алrебраические структуры над множеством многочленов
Кольцо многочленов над полем GF(p)
Определение 1.17. Кольцо, образованное многочленами над полем GF(p), называется кольцом многочлен
Расширение полей
Рассмотрим, какова связь полей GF(p) и GF( p n ).
Пусть F - поле. Подмножество К поля Р, которое само является полем относительно операций поля Р, на
Системы уравнений сравнений
Общий вид:
x ≡ c1 mod m1
x ≡ c2 mod m2
Pound; b£ n-1
Если для каждого простого делителя p числа n-1 справедливы следующие утверждения:
(1) bn-1≡ 1(mod n),
Числа Кармайкла
Может ли составное нечетное число n быть псевдопростым по всем взаимно-простым с ним основаниям b? Забегая вперед, скачем, что «да».
Заметим
Процедура получения устойчивых простых чисел
1. Генерируются простые числа s,t
2. Получаем простое число r такое что, (r-1) делит t без остатка: r-1|t
На основе этих двух операций получаем про
М-последовательности. ГПСЧ типа ЛРС1
Опр ед ел ени е. Последовательностью над полем
GF ( p)
будем
назы
M - последовательности на основе произведения многочленов
Рассмотрим способ построения схемы линейного регистра сдвига на основе характеристического многочлена, задаваемого как произведение
многочленов, при
&nbs
Произведения многочленов
Рассмотрим следующие свойства ЛРП, порождаемой схемой ГПСП,
изображенной на рис. 2.1, при
a0 =1.
ЛЕКЦИЧ 16
Способы представления элементов поля GF(2n)
Для представления элементов в полях Галуа вида GF(2n) существуют ра
Алгоритм получения элементов поля GF(2n) в стандартном базисе
Для построения элементов поля GF(2n) в стандартном базисе существует следующий алгоритм, использующий сдвиговыерегистры.
На входе: поле GF(2n
Заданными в стандартном базисе
Алгоритм асимметричного шифрования RSA
Алгоритм RSA предложили в 1978 г. 3 автора: Райвест (Rivest), Шамир (Shamir) и Адлеман (Adleman). RSA является алгоритмом с открытым ключом, работающим в режимах шифрования данных и
Математическая модель алгоритма RIJNDAEL
Байты можно рассматривать как элементы конечного поля GF(28) -
многочлены степени не более 7
а7х7 + а6х
Раунд преобразования алгоритма RIJNDAEL
RIJNDAEL выполняет серию однотипных раундов преобразования шифруемого блока. Шифруемый блок и его промежуточные состояния в ходе преобразования представляются в виде квадратной матр
Новости и инфо для студентов