Основы криптографии
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
ета ровно четыре квадратных корня.
Символ Лежандра
Символ Лежандра, L(a,p), определен, если а - это любое целое число, a p - простое число, большее, чем 2. Он равен 0, 1 или - 1 .
L(a,p)= 0, если а делится на р.
L(a,p)= 1, если а - квадратичный вычет по модулю р.
L(a,p) = -1, если а не является квадратичным вычетом по модулю р.
L(a,p) можно расiитать следующим образом: L(a,p) = a(p-1)/2 mod p Или можно воспользоваться следующим алгоритмом:
. Если а = 1, то L(a,p) = 1
- Если а четно, то L(a,p) = L(a/2,p) * (-l)^2-'>78
- Если а нечетно (и * 1), то L(a,p)= Цр mod а,^)*(-1)(3*3-1)/8
Обратите внимание, что этот метод также является эффективным способом определить, является ли a квадратичным вычетом по модулю p (для простого числа p).
Символ Якоби
Символ Якоби, J(a,n), представляет собой обобщение символа Лежандра на составные модули, он определяется для любого целого a и любого нечетного целого п. Функция удобна при проверке на простоту. Символ Якoби является функцией на множестве полученных вычетов делителей n и может быть вычислен по различным формулам.Вот один из способов:
Определение 1 : J(a,n) определен, только если n нечетно.
Определение 2: J(0,n) = 0.
Определение 3: Если n - простое число, то символ Якоби ](a,n) = 0, если а делится на п.
Определение 4: Если n - простое число, то символ Якоби J(a,n) = 1, если а - квадратичный вычет по модулю п.
Определение 5: Если n - простое число, то символ Якоби ](a,n) = -1, если а не является
квадратичным вычетом по модулю п.
Определение 6: Если n - составное число, то символ Якоби J(a,n) = J(a,p1)* ... * J(a,pm), где p1тАжpm - это разложение n на простые сомножители.
Следующий алгоритм рекурсивно расiитывает символ Якоби:
Правило 1: J(l,n) = 1
Правило 2: J(a*b,n} = J(a,n)* J(b,n)
Правило 3: J(2,n) =, если (n2-1) /8 нечетно, и -1 в противном случае
Правило 4: J(a,n)= J((a mod n),n)
Правило 5: J(a, bi*b2) = J(a, b1)* J(a, b2)
Правило 6: Если наибольший общий делитель a и b = 1, а также a и b нечетны:
Правило 6а: J(a,b)= J(b, a), если (a - 1)(b - l)/4 четно
Правило 6b: J(a,b)= -J(b, a), если (a - 1)(b - l)/4 нечетно
Алгоритм на языке С: (кажется уже начал объяснять сам С)
int jacobi(int a, int b) {g;(odd(b)); (а >= b) a %= b; /* по правилу 4 */
if (а == 0) return 0; /* по определению 1 */
if (а == 1) return 1; /* по правилу 1 */
if (а < 0)
if ((b-l)/2 % 2 == 0)
return jacobi(-a,b); else
return -jacobi(-a,b); if (а % 2 == 0) /* а четно */
if (((b*b -1)/8) % 2 == 0)
return +jacobi(a/2,b); else
return -jacobi(a/2,b); /* по правилам 3 и 2 */ g = gcd(a,b);(odd(a)); /* это обеспечивается проверкой (а % 2 == 0) */ if (g == а) /* b делится на а */
return 0; /* по правилу 5 */ else if (g '= 1)
return jacobi(g,b)*jacobi(a/g,b); /* по правилу 2 */ else if (((a-l)*(b-l)/4) % 2 == 0)
return +jacobi(b,a); /* по правилу 6a */ else
return -jacobi(b,a); /* по правилу 6b */ }
Если заранее известно, что n - простое число, вместо использования предыдущего алгоритма просто вычиcлите a((n-l)/2) mod n, в этом случае J(a,n) эквивалентен символу Лежандра.
Символ Якоби нельзя использовать для определения того, является ли a квадратичным вычетом по модулю n (если, конечно, n не является простым числом). Обратите внимание, что если J( a,n) = 1 и n - составное число, то утверждение, что а является квадратичным вычетом по модулю и, не обязательно будет истиной. Например:
J(7,143) = J(7,11)* J(7,13) = (-1)(-1) = 1
Однако не существует таких целых чисел x, что x2 = 1 (mod 143).
Целые числа Блюма
Если p и q - два простых числа, конгруэнтных 3 по модулю 4, то n = pq иногда называют целым числом Блюма. Если n - это целое число Блюма, у каждого квадратичного вычета ровно четыре квадратных корня, один из которых также является квадратом - это главный квадратный корень. Например, главный квадратный корень 139 mod 437 - это 24. Остальные три корня - это 185, 252 и 413.
Вычисление в поле Галуа
Не тревожьтесь, все это мы уже делали. Если n - простое число или степень большого простого числа, то мы получаем то, что математики называют конечным полем. В честь этого мы используем p вместо п. В действительности этот тип конечного поля настолько замечателен, что математики дали ему собственное имя - поле Галуа, обозначаемое как GF(p). в честь Эвариста Галуа, французского математика, жившего в девятнадцатом веке и успевшего значительно продвинуть теорию чисел, прежде чем в 20 лет он был убит на дуэли.)
В поле Галуа определены сложение, вычитание, умножение и деление на ненулевые элементы. Существует нейтральный элемент для сложения - 0 - и для умножения - 1. Для каждого ненулевого числа существует единственное обратное число (это не было бы так, если бы p не было бы простым числом). Выполняются коммутативный, ассоциативный и дистрибутивный законы.
Арифметика поля Галуа широко используется в криптографии. В нем работает вся теория чисел, поле с o-держит числа только конечного размера, при делении отсутствуют ошибки округления. Многие криптосистемы основаны на GF(p), где з - это большое простое число.
Чтобы еще более усложнить вопрос, криптографы также используют арифметику по модулю неприводимых многочленов степени n, коэффициентами которых являются целые числа по модулю q, где q - это простое число. Эти поля называются GF(qт). Используется арифметика по модулю p(x), где р(х) - это неприводимый многочлен степени п.
При обсуждении полиномов термин "простое число" заменяется термином " неприводимый многочлен". Пoлином называется неприводимым, если его нельзя представить в виде двух других полиномов (конечно же, кроме 1 и самого полинома). Полином x2 + 1 неприводим над целыми числами, а полином x3 + 2 x2 + x не является неприводимым, он может быть представлен как
x(x + l)(x + 1).
Полином, который в данном поле является ге