Основы криптографии
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
значение a по модулю и? Существует два пути. Обратное значение а по модулю n можно вычислить с помощью алгоритма Эвклида. Иногда это называется расширенным алгоритмом Эвклида.
Вот этот алгоритм на языке С++:
#define isEven(x) ((x & 0x01) == 0)
#define isOdd(x) (x& 0x01)
#define swap(x,y) (x^= у, y^= x, x^= у)
void ExtBinEuclid(int *u, int *v, int *ul, int *u2, int *u3) {
// предупреждение: u и v будут переставлены, если u<v int k, tl, t2, t3;
if (*u < *v) swap(*u<,*v);
for (k = 0; isEven(*u) && isEven(*v); ++k) {
*u>>=l; *v 1;
}
*ul = 1; *u2 = 0; *u3 = *u; tl = *v; t2 = *u - 1; t3 = *v;
do {
do {
if (isEven(*u3)) {
if (isOdd(*ul) || isOdd(*u2)) {
*ul += *v; *u2 += *u;
} *ul * 1; *u2 = 1; *u3 = 1;
}
if (isEven(t3) II *u3 < t3) { swap(*ul,tl); smap(*u2,t2); smap(*u3,t3);
}
} while (isEven(*u3)); while (*ul < tl || *u2 < t2) { *ul += *v; *u2 += *u; }
ul -= tl; *u2 -= t2; *u3 -= t3; } while (t3 > 0) ;
while (*ul >= *v && *u2 >= *u) { *ul>l -= *v; *u2 -= *u;
}
*u = k; *v = k; *u3 k; }
main(int argc, char **argv) { int a, b, gcd; if (argc < 3) {
cerr "как использовать: xeuclid u v" endl; return -1;
}
int u = atoi(argv[l]); int v = atoi(argv[2]); if (u <= 0 || v <= 0 ) {
cerr "Аргумент должен быть положителен'" endl; return -2;
}
// предупреждение: u и v будут переставлены если u < v
ExtBinEuclid(&u, &v, &a, &b, &gcd); cout а " * " u " + (-" b ") * " v " = " gcd endl; if (gcd == 1) "Обратное значение " v " mod " u " is: u - b endl;
return 0;
Я не собираюсь доказывать, что это работает, или приводить теоретическое обоснование.
Алгоритм итеративен и для больших чисел может работать медленно.
Решение для коэффициентов
Алгоритм Эвклида можно использовать и для решения следующих проблем: дан массив из т переменных
Xi, х2,..., хт, найти массив т коэффициентов, u\, и2,..., ит, таких что
Mi * Xi+...+ Um * Хт, = 1
Малая теорема Ферма
Если т - простое число, и а не кратно т, то малая теорема Ферма утверждает атЛ = 1 (mod m)
(Пьер де Ферма (Pierre de Fermat), французский математик, жил с 1601 по 1665 год. Эта теорема не имеет ничего общего с его знаменитой теоремой.)
Функция Эйлера
Существует другой способ вычислить обратное значение по модулю n, но его не всегда возможно использoвать. Приведенным множеством остатков mod n называется подмножество полного множества остатков, члeны которого взаимно просты с п. Например, приведенное множество остатков mod 12 - это {1, 5, 7, 11}. Если n -простое число, то приведенное множество остатков mod n - это множество всех чисел от 1 до n-\. Для любого n, не равного 1,число 0 никогда не входит в приведенное множество остатков.
Функция Эйлера, которую также называют функцией фи Эйлера и записывают как ф(n), - это количество элементов в приведенном множестве остатков по модулю п. Иными словами, ф(n) - это количество положительных целых чисел, меньших n и взаимно простых с n (для любого и, большего
Если n - простое число, то ф(n) = n-\. Если n =pq, где р и q -простые числа, то ф(n)= (p - \)(q - 1). Эти числа появляются в некоторых алгоритмах с открытыми ключами, и вот почему. В соответствии с обобщением Эйлepa малой теоремы Ферма, если НОД(а,n) = 1, то
a ф(n) mod n = 1
Теперь легко вычислить а-1 mod n:
x = a ф(n)-1 mod n
Например, какое число является обратным для 5 по модулю 7? Так как 7 - простое число, ф(7) = 7 - 1 = 6. Итак, число, обратное к 5 по модулю 7, равно
6'1 mod 7 = 55 mod 7 = 3
Эти методы вычисления обратных значений можно расширить для более общей проблемы нахождения x (если НОД(а,n)= 1):
(a*x) mod n = b
Используя обобщение Эйлера, решаем
x = (b* a ф(n)-1 ) mod n
Используя алгоритм Эвклида, находим
x = (b* (a-1 modn)) mod n
В общем случае для вычисления обратных значений алгоритм Эвклида быстрее, чем обобщение Эйлера, особенно для чисел длиной порядка 500 бит. Если НОД(а,и) Ф 1, не все потеряно. В этом общем случае (a*x) mod n=b, может иметь или несколько решений, или ни одного.
Квадратичные вычеты
Если p - простое число, и а больше 0, но меньше p, то а представляет собой квадратичный вычет по модулю p, если x2 = a (mod p), для некоторых x Не все значения а соответствуют этому требованию. Чтобы а было квадратичным вычетом по n, оно должно быть квадратичным вычетом по модулю всех простых сомножителей п. Например, если p = 7, квадратичными вычетами являются числа 1, 2, и 4:
12 = 1 = 1 (mod 7)
2 = 4 = 4 (mod 7)
2 = 9 = 2 (mod 7)
2=16 = 2(mod7)
2 = 25 = 4 (mod 7) 62 = 3
6 = 1 (mod 7)
Заметьте, что каждый квадратичный вычет дважды появляется в этом списке. Значений x, удовлетворяющих любому из следующих уравнений, не существует:
x2 = 3 (mod 7)
x2 = 5 (mod 7)
x2 = 6 (mod 7)
Эти числа - 3, 5 и 6 - не являются квадратичными вычетами по модулю 7.
Хотя я этого и не делаю, несложно доказать, что когда p нечетно, существует в точности (p - l)/2 квадратичных вычетов по модулю p, и столько же чисел, не являющихся квадратичными вычетами по модулю р. Кроме того, если а - это квадратичный вычет по модулю p, то у а в точности два квадратных корня, один между 0 и (p-l)/2, а второй - между (p - l)/2 и (p - 1). Один из этих квадратных корней одновременно является квадратичным остатком по модулю p, он называется главным квадратным корнем
Если n является произведением двух простых чисел, p и q, то существует ровно (p - 1)(q - l)/4 квадратичных вычетов по модулю п. Квадратичный вычет по модулю n является совершенным квадратом по модулю и, потому что для того, чтобы быть квадратом по модулю и, вычет должен быть квадратом по модулю p и квадратом по модулю q. Например, существует одиннадцать квадратичных остатков mod 35: 1, 4, 9, 11, 15, 16, 21, 25, 29 и 30. У каждого квадратичного выч