У вас вопросы?
У нас ответы:) SamZan.net

Число ~ Zn називається квадратичним лишком або квадратом за модулем n якщо існує таке x ~ Zn що x2 mod n

Работа добавлена на сайт samzan.net: 2016-03-30

Поможем написать учебную работу

Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.

Предоплата всего

от 25%

Подписываем

договор

Выберите тип работы:

Скидка 25% при заказе до 5.4.2025

Квадратичні лишки

Означення. Число a Î Zn* називається квадратичним лишком або квадратом за модулем n, якщо існує таке x Î Zn*, що x2 º a (mod n). Якщо такого x не існує, то число a називається квадратичним нелишком. Множина усіх квадратичних лишків за модулем n позначається через Qn, нелишків – через . За означенням 0 Ï Zn*, отже 0 Ï Qn та  0 Ï .

Теорема. Нехай p – непарне просте число, g – генератор Zp*. Тоді число a є квадратичним лишком за модулем p тоді і тільки тоді, коли a = gi (mod p), де i – парне ціле.

Доведення. Якщо a = g2k (mod p), то a = b2 (mod p), де b = gk (mod p).

Нехай a = gk (mod p) – елемент Zp*. Піднесемо його до квадрату:

a2 = g2k (mod p) º gi (mod p). Оскільки 2k (mod p – 1) = i – парне число, то звідси і випливає твердження про те що квадрат довільного елемента a Î Zp* представляється у вигляді gi (mod p) лише для парного i.

Наслідок. | Qp | = (p - 1) / 2, || = (p - 1) / 2.

Тобто половина елементів Zp* є квадратичними лишками, а половина – ні.

Приклад. Число a = 3 є генератором Z7*. Степені a наведені у наступній таблиці

I

0

1

2

3

4

5

6

ai mod 7

1

3

2

6

4

5

1

Звідси Q7 = {1, 2, 4},  = {3, 5, 6}.

Схема множення кважратичних лишків та нелишків аналогічна схемі додавання парних та непарних цілих чисел:

лишок * лишок = лишок

лишок * нелишок = нелишок

нелишок * нелишок = лишок

Приклад. Дослідимо операції множення лишків та нелишків в групі Z7*.

2 Î Q7, 4 Î Q7 : 2 * 4  = 8 º 1 Î Q7

2 Î Q7, 5 Î : 2 * 5  = 10 º 3 Π

5 Î , 6 Î : 5 * 6  = 30 º 2 Î Q7

Твердження. Нехай  n – добуток двох різних простих чисел p та q, n = p * q. Тоді число a Î Zn* є квадратичним лишком за модулем n тоді і тільки тоді, коли a Î Qp та a Î Qq. Звідси |Qn|  = |Qp| * |Qq| = (p - 1)(q - 1) / 4 та || = 3 (p - 1)(q - 1) / 4.

Приклад. Нехай n = 21. Тоді |Q21| = (2 * 6) / 4 = 3, Q21 = {1, 4, 16},

|| =. (3 * 2 * 6) / 4 = 9,  = {2, 5, 8, 10, 11, 13, 17, 19, 20}.

Означення. Нехай a Î Qn. Якщо x Î Zn* задовольняє x2 º a (mod n), то x називається квадратним коренем числа a за модулем n.

Теорема. Нехай p – просте, p º 3 (mod 4), a Î Qp. Тоді розв’язком рівняння

x2 º a (mod p)

будуть числа r та -r, де r =  (mod p).

Доведення. r2 º  (mod p) º  (mod p) º  (mod p) º  (mod p) º a (mod p), оскільки за теоремою Ферма ap-1 (mod p) º 1.

Доведення теореми можна провести, використовуючи критерій Ейлера. Оскільки a – квадратичний лишок за модулем p, то

 º (mod p) = 1

Враховуючи що число p можна подати у вигляді p = 4m + 3 для деякого натурального m, то  = 2m + 1. Тобто  =  º 1(mod p) , º a (mod p). Візьмемо квадратний корінь лівої та правої частини останньої рівності:

º ± (mod p)

Приклад. Обчислити  та  в Z11*.

p = 11 – просте, p º 3 (mod 4), = 3.

: 53 (mod 11) º 4. –4 º 7 (mod 11).

Перевірка: 42 (mod 11) º 5, 72 (mod 11) º 5.

: 33 (mod 11) º 5. –5 º 6 (mod 11).

Перевірка: 52 (mod 11) º 3, 62 (mod 11) º 3.

Теорема. Нехай n = p * q, де p, q – непарні прості числа. Число а Î Zn*  є квадратичним лишком за модулем n тоді і тільки тоді, коли а є квадратичним лишком за модулем p та q. Тобто

а Î Qn Û  а Î Qp та а Î Qq

Звідси |Qn| = |Qp| * |Qq| = (p – 1)(q – 1) / 4.

Приклад. Нехай n = 21 = 3 * 7. а Î Q21 Û  а Î Q3 та а Î Q7.

Q3 = {1}, поширимо остачі до 21 за модулем 3: {1, 4, 7, 10, 13, 16, 19}.

Q7 = {1, 2, 4}, поширимо остачі до 21 за модулем 7: {1, 2, 4, 8, 9, 11, 15,16,18}.

|Q21| = |Q3| * |Q7| = 1 * 3 = 3. Числа, спільні в двох множинах поширених остач, і є квадратичними лишками за модулем 21.

Q21 = {1, 4, 16}.




1. Тема- Создание графических изображений в векторном редакторе встроенном в Word 1Векторные изображения фор
2. Дизайн экспозиции
3. разбрасываются по порядковой шкале от первой до последней
4. Методика аудиторской проверки основных средств
5. Влияние схемы шлифования как динамического фактора процесса резания на дефектность и прочность изделий из ситаллов
6.  единою судьбой Мы связаны навек друг мой
7. Тема- Удаление зубных отложений
8. Корпоративный подоходный налог
9. на тему Основные фонды предприятия и их структура Работа выполнена студентом группы 10501 Скворцовым
10. Архитектурные памятники Крыма