Квадратичні лишки (реферат)

Реферат на тему:

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

Означення. Число a * називається квадратичним лишком або квадратом за модулем n, якщо існує таке x *, що x2 (mod n). Якщо такого x не існує, то число a називається квадратичним нелишком. Множина усіх квадратичних лишків за модулем n позначається через Qn, нелишків — через $${\stackrel{}{Q}}_n$$. За означенням 0 Zn*, отже 0 та 0 $${\stackrel{}{Q}}_n$$ .

Теорема. Нехай 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) (mod p). Оскільки 2k (mod p — 1) = i — парне число, то звідси і випливає твердження про те що квадрат довільного елемента a * представляється у вигляді gi (mod p) лише для парного i.

Наслідок. | Qp | = (p — 1) / 2, | $$\stackrel{}{Q_p}$$ | = (p — 1) / 2.

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

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

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

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

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

2, 4: 2 * 4 = 8.

2, 5 g alt="" src="data:image/*-base64,AQAJAAADyQAAAAMAFQAAAAAABQAAAAkCAAAAAAQAAAACAQEABQAAAAEC////AAQAAAAuARgABQAAADECAQAAAAUAAAALAgAAAAAFAAAADAKAAkACEgAAACYGDwAaAP////8AABAAAADA////rv///wACAAAuAgAACwAAACYGDwAMAE1hdGhUeXBlAABgAAkAAAD6AgAAEAAAAAAAAAAiAAQAAAAtAQAABQAAABQCWgBAAAUAAAATAloAPAEVAAAA+wLg/gAAAAAAAJABAAAAAAQCABBUaW1lcyBOZXcgUm9tYW4AOQAEAAAALQEBAAgAAAAyCioCYwEBAAAANwAVAAAA+wKA/gAAAAAAAJABAAAAAAQCABBUaW1lcyBOZXcgUm9tYW4AvOMEAAAALQECAAQAAADwAQEACAAAADIKwAE0AAEAAABRAAoAAAAmBg8ACgD/////AQAAAAAAEAAAAPsCEAAHAAAAAAC8AgAAAAABAgIiU3lzdGVtAG4EAAAALQEBAAQAAADwAQIAAwAAAAAA" >: 2 * 5 = 10 mg alt="" src="data:image/*-base64,AQAJAAADyQAAAAMAFQAAAAAABQAAAAkCAAAAAAQAAAACAQEABQAAAAEC////AAQAAAAuARgABQAAADECAQAAAAUAAAALAgAAAAAFAAAADAKAAkACEgAAACYGDwAaAP////8AABAAAADA////rv///wACAAAuAgAACwAAACYGDwAMAE1hdGhUeXBlAABgAAkAAAD6AgAAEAAAAAAAAAAiAAQAAAAtAQAABQAAABQCWgBAAAUAAAATAloAPAEVAAAA+wLg/gAAAAAAAJABAAAAAAQCABBUaW1lcyBOZXcgUm9tYW4AOQAEAAAALQEBAAgAAAAyCioCYwEBAAAANwAVAAAA+wKA/gAAAAAAAJABAAAAAAQCABBUaW1lcyBOZXcgUm9tYW4AvOMEAAAALQECAAQAAADwAQEACAAAADIKwAE0AAEAAABRAAoAAAAmBg8ACgD/////AQAAAAAAEAAAAPsCEAAHAAAAAAC8AgAAAAABAgIiU3lzdGVtAG4EAAAALQEBAAQAAADwAQIAAwAAAAAA" >

5 mg alt="" src="data:image/*-base64,AQAJAAADyQAAAAMAFQAAAAAABQAAAAkCAAAAAAQAAAACAQEABQAAAAEC////AAQAAAAuARgABQAAADECAQAAAAUAAAALAgAAAAAFAAAADAKAAkACEgAAACYGDwAaAP////8AABAAAADA////rv///wACAAAuAgAACwAAACYGDwAMAE1hdGhUeXBlAABgAAkAAAD6AgAAEAAAAAAAAAAiAAQAAAAtAQAABQAAABQCWgBAAAUAAAATAloAPAEVAAAA+wLg/gAAAAAAAJABAAAAAAQCABBUaW1lcyBOZXcgUm9tYW4AOQAEAAAALQEBAAgAAAAyCioCYwEBAAAANwAVAAAA+wKA/gAAAAAAAJABAAAAAAQCABBUaW1lcyBOZXcgUm9tYW4AvOMEAAAALQECAAQAAADwAQEACAAAADIKwAE0AAEAAABRAAoAAAAmBg8ACgD/////AQAAAAAAEAAAAPsCEAAHAAAAAAC8AgAAAAABAgIiU3lzdGVtAG4EAAAALQEBAAQAAADwAQIAAwAAAAAA" >, 6 g alt="" src="data:image/*-base64,AQAJAAADyQAAAAMAFQAAAAAABQAAAAkCAAAAAAQAAAACAQEABQAAAAEC////AAQAAAAuARgABQAAADECAQAAAAUAAAALAgAAAAAFAAAADAKAAkACEgAAACYGDwAaAP////8AABAAAADA////rv///wACAAAuAgAACwAAACYGDwAMAE1hdGhUeXBlAABgAAkAAAD6AgAAEAAAAAAAAAAiAAQAAAAtAQAABQAAABQCWgBAAAUAAAATAloAPAEVAAAA+wLg/gAAAAAAAJABAAAAAAQCABBUaW1lcyBOZXcgUm9tYW4AOQAEAAAALQEBAAgAAAAyCioCYwEBAAAANwAVAAAA+wKA/gAAAAAAAJABAAAAAAQCABBUaW1lcyBOZXcgUm9tYW4AvOMEAAAALQECAAQAAADwAQEACAAAADIKwAE0AAEAAABRAAoAAAAmBg8ACgD/////AQAAAAAAEAAAAPsCEAAHAAAAAAC8AgAAAAABAgIiU3lzdGVtAG4EAAAALQEBAAQAAADwAQIAAwAAAAAA" >: 5 * 6 = 30.

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

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

| $${\stackrel{}{Q}}_{\text{21}}$$ | =. (3 * 2 * 6) / 4 = 9, $${\stackrel{}{Q}}_{\text{21}}$$ = {2, 5, 8, 10, 11, 13, 17, 19, 20}.

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

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

x2 (mod p).

будуть числа r таr, де r = $$a^{\frac{p+1}{4}}$$ (mod p).

Доведення. r2 math xmlns="http://www.w3.org/1998/Math/MathML" display="block" >ap+12 (mod p) math xmlns="http://www.w3.org/1998/Math/MathML" display="block" >ap+1 (mod p) math xmlns="http://www.w3.org/1998/Math/MathML" display="block" >ap-1a2 (mod p) math xmlns="http://www.w3.org/1998/Math/MathML" display="block" >1a2 (mod p) (mod p), оскільки за теоремою Ферма ap-1 (mod p) 1.

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

$$\left(\frac{a}{p}\right)$$ math xmlns="http://www.w3.org/1998/Math/MathML" display="block" >ap-12 (mod p) = 1.

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

$$a^{m+1}$$ ath xmlns="http://www.w3.org/1998/Math/MathML" display="block" >a (mod p).

Приклад. Обчислити $$\sqrt{5}$$ та $$\sqrt{3}$$ в Z11*.

p = 11 — просте, p (mod 4), $$\frac{p+1}{4}$$ = 3.

$$\sqrt{5}$$: 53 (mod 11) -4 (mod 11).

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

$$\sqrt{3}$$: 33 (mod 11) -5 (mod 11).

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

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

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

Приклад. Нехай n = 21 = 3 * 7. а 1 та, а .

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}.