Лабораторная работа № 7 Программная реализация алгоритма вычисления символа Лежандра

Цель работы: используя алгоритм для вычисления символа Лежандра, составить программу вычисления символа Лежандра.

1 Краткие теоретические сведения

Пусть a – целое число и p, p> 2, – простое число. Символ Лежандра L(a,p) определяется равенством

0, если a ≡ 0 mod p,

L(a,p) = 1, если a – квадратичный вычет по модулю p,

-1, если a – квадратичный невычет по модулю p.

Иными словами, L(a, p) =1, если сравнение x²≡a mod p имеет решений, и L(a,p) = -1, если данное сравнение не имеет решений. В литературе символ Лежандра часто обозначается через следующим образом

Далее будем рассматривать случай, когда p не делит a, т.е. L(a,p) ≠0

Пример.

L(3, 11) = 1, так как сравнение

x²≡3 mod 11

имеет два решения

x₁≡5 mod 11, x₂≡-5 mod 11.

L(6, 7) = -1, так как сравнение

x₂≡6 mod 7

не имеет решений.

Алгоритм вычисления символа Лежандра

1. Если число a отрицательно, то выделяем множитель L (-1, p);

2. Заменяем число a на остаток от деления числа a на p;

3. Раскладываем число a в произведение в простых сомножителей

a = a₁^α1a₂^α2...a_k^αk;

если число на простые множители не разлагается, то переходим на шаг

4. Переходим к разложению

L(a, p) = L(a₁, p)^α1... L(a_k, p)^αk;

5. Отбрасываем множители с четным значением показателя α_j, j ≤k ;

6. Вычисляем символ Лежандра L(a_j, p)^αj для a_j= 2;

7. Если все символы Лежандра в выражении

L(a, p) = L(a₁, p)α1... L(a_k, p)^αk

вычислены, то алгоритм вычисления L(a, p) завершаем. В противном случае для множителей L(a_j, p)^αj, у которых a_j≠2, применяем закон взаимности

L(p, q) = -1^{[(p-1)/2][(q-1)/2]}L(q, p).

Здесь полагается, что p= a_j.

8. Переходим к шагу 1

Примечание. На каждом шаге процесс вычисления символа Лежандра может быть завершено. Это произойдет в том случае, если на каком-то шаге алгоритма, все числа α_j, j≤k, окажутся равными 1, 2 или –1.

Пример. Вычислить L (68,113). Здесь a=68, p=113- простое число.

1. При a > 0 множитель L (-1, 113) отсутствует;

2. Так как 68 < 113, то остаток равен самому числу;

3. Раскладываем число а = 68 на простые множители 68 = 2²×17;

4. Имеем

L(68, 113)= L(2²×17, 113)= L(2², 113)L(17, 113)= [L(2, 113)]²L(17, 113);

5. Так как L(2², 113) = 1, то в разложении

L(68, 113)= [L(2, 113)]²L(17, 113)

отбрасываем множитель [L(2, 113)]²;

6. После выполнения шага 5 получаем

L(68, 113) = L(17, 113).

В полученном разложении отсутствует множитель L(2, 113);

7. Для множителя L(17, 113), применяя закон взаимности для a=17 и p=113, получаем

L(17, 113) = (-1)^8×56L(113, 17) = L(113, 17).

8. В итоге имеем L(68, 113) = L(113, 17).

Далее переходим на шаг 1 и начинаем вычислять L(113, 17). Здесь a= 113 и p

=17 – простое число.

Вычисляем L(113,17)

1. При a> 0 множитель L(-1, 17) отсутствует;

2. Остаток от деления числа 113 на 17 равен 11, поэтому получаем

L (113, 17) = L(11, 17);

3. Число 11 – простое на множители не разлагается;

4. Так как 11 простое число, то переходим к шагу 7;

7. Для множителя L(11, 17), применяя закон взаимности для a=11 и p=17. Получаем L(11, 17) = (-1)^5×8L (17, 11) = L(17, 11).

8. В итоге имеем L(113, 17) = L(17, 11).

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

L(17, 11), здесь a= 17 и p=11 – простое число

Вычисляем L(17, 11).

1. При a> 0 множитель L(-1, 11) отсутствует;

2. Остаток от деления числа 17 на 11 равен 6;

3. Разлагаем число 6 на простые множители 6 = 2×3;

4. Имеем

L(6, 11) = L(2,11)L(3,11)

5. В разложении L(6, 11) множители с четным значением показателей отсутствуют, поэтому переходим к шагу 6;

6. Вычисляем значение L(2,11)

L(2,11) = [-1]^(α-1)/8= [-1]¹⁵= -1,

где

α= p²= 11²= 121;

7. Для множителя L(3, 11), применяя закон взаимности для a=3 и p=11, получаем

L(3, 11) = (-1)^1×5L(11, 3) = -L(11, 3).

8. В итоге имеем L(17, 11) = (-1)×[-L(11, 3)] = L(11,3).

Далее переходим на шаг 1 и начинаем вычислять L(11, 3), здесь a= 11, p= 3 –простое число.

Вычисляем L(11, 3).

1. При a> 0 множитель L(-1, 3) отсутствует;

2. Остаток от деления числа 11 на 3 равен 2, поэтому получаем

L(11, 3) = L(2, 3)

3. Число 2 – простое, на множители не разлагается;

4. Имеем

L(11, 3) = L(2,3)

5. В разложении L(11, 3) множители с четным значением показателей отсутствуют, поэтому переходим к шагу 6;

6. Вычисляем значение L(2,3)

L(2, 3) = [-1]^(α-1)/8= [-1]¹= -1,

где α= p²= 3²= 9;

Окончательно получаем, что L(68, 113) = -1.

Тем самым вычисление символа Лежандра L(68, 113) завершено. Значение символа Лежандра L(68, 113) = -1позволяет сделать вывод, что сравнение x²≡68 mod 113 не имеет решений.

2 Задание на лабораторную работу

1. Составить программу, производящую вычисление символа Лежандра. Язык программирования выбирается произвольно.

2. Осуществить вывод на экран или принтер полученных результатов.

3. Результаты работы оформить в виде отчета.

4. Содержание отчета: описание используемого метода, описание исходных данных, текст программы, результаты работы программы и выводы.

3 Содержание отчёта

1. Титульный лист;

2. Цель работы;

3. Краткие теоретические сведения;

4. Текст программы;

5. Результаты работы программы;

6. Выводы.

4 Контрольные вопросы

1. Перечислить основные виды атак на протоколы .

2. Назвать протоколы обмена секретами.

3. Назначение протокола аутентификации.

4. Назначение протокола аутентификации сообщений.