Квадратичные вычеты по простому модулю

Revision ru10, by EJIC_B_KEDAX, 2024-07-22 02:23:16

Привет Codeforces!

Сегодня я расскажу о непопулярной технике в теории чисел.

Определение и элементарные свойства

Опр. Пусть $$$p > 2$$$ простое число, тогда квадратичным вычетом по модулю $$$p$$$ назовём все $$$1 \le x \le p - 1$$$, такие, что уравнение $$$a^2 \equiv x \pmod{p}$$$ имеет решения и квадратичным невычетом иначе. Обратите внимание, что $$$0$$$ не является ни квадратичным вычетом, ни квадратичным невычетом.

Теорема: Квадратичных вычетов и крадратичных невычетов поровну.

Доказательство

Теорема: Обозначим за $$$B$$$ квадратичный вычет, а за $$$H$$$ квадратичный невычет, тогда:

$$$B \cdot B = B$$$
$$$H \cdot B = H$$$
$$$H \cdot H = B$$$
Доказательство

С помощью этих двух теорем уже можно решить 103428K - Tiny Stars.

Как проверить, число вычет или невычет?

Есть несколько способов проветь является ли число квадратичным вычетом. В этом блоге мы рассмотрим только один из них, вы можете почитать про лемму Гаусса и квадратичный закон взаимности.

Критерий Эйлера

$$$a$$$ является квадратичным вычетом по модулю $$$p$$$ тогда и только тогда, когда $$$a^{\frac{p - 1}{2}} \equiv 1 \pmod{p}$$$, и квадратичным невычетом тогда и только тогда, когда $$$a^{\frac{p - 1}{2}} \equiv -1 \pmod{p}$$$.

Доказательство

Следствие: $$$-1$$$ является квадратичным вычетом тогда и только тогда, когда $$$p = 4k + 1$$$, для какого-то натурального $$$k$$$, и квадратичным невычетом тогда и только тогда, когда $$$p = 4k + 3$$$, для какого-то натурального $$$k$$$.

Очевидно, что сложность проверки числа $$$O(\log_2p)$$$.

Код

Нахождение $$$i$$$ по модулю $$$p$$$

Опр. $$$i$$$ это такое число, что $$$i^2 = -1$$$ $$$\implies$$$ $$$i$$$ по модулю $$$p$$$ назовём такое число, что $$$i ^ 2 \equiv -1 \pmod{p}$$$.

Алгоритм: Если $$$p = 4k + 3$$$ для какого-то натурального $$$k$$$, то такого $$$i$$$ не существует. Если $$$p = 2$$$, то $$$i = 1$$$. Иначе рассмотрим квадратичный невычет $$$a$$$, по критерию Эйлера нам известно, что $$$a^{\frac{p - 1}{2}} \equiv -1 \pmod{p}$$$, тогда $$$a^{\frac{p - 1}{4}} \equiv i \pmod{p}$$$. Осталось лишь найти квадратичный невычет, для этого возьмём случайное $$$1 \le a \le p - 1$$$ и проверим его за $$$O(\log_2p)$$$, если это квадратичный вычет, то берём другое случайное $$$a$$$, так как вычетов и невычетов поровну то нам понадобится $$$O(1)$$$ таких проверок, а значит итоговая сложность алгоритма $$$O(\log_2p)$$$.

Код
Tags математика, теория чисел

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en11 English EJIC_B_KEDAX 2024-07-30 15:37:55 0 (published)
ru16 Russian EJIC_B_KEDAX 2024-07-30 15:37:29 0 (опубликовано)
en10 English EJIC_B_KEDAX 2024-07-30 15:21:42 8
ru15 Russian EJIC_B_KEDAX 2024-07-30 15:14:38 11
en9 English EJIC_B_KEDAX 2024-07-30 15:14:09 74
en8 English EJIC_B_KEDAX 2024-07-29 01:34:33 29 Tiny change: 's, so the total complexity of the al' -> 's, so the expected running time of the al'
ru14 Russian EJIC_B_KEDAX 2024-07-29 01:34:09 26
en7 English EJIC_B_KEDAX 2024-07-29 01:32:56 96
en6 English EJIC_B_KEDAX 2024-07-29 01:30:19 1 Tiny change: 'y="Proof">.\nFirst, l' -> 'y="Proof">\nFirst, l'
en5 English EJIC_B_KEDAX 2024-07-29 01:29:57 117
en4 English EJIC_B_KEDAX 2024-07-29 01:26:48 424
ru13 Russian EJIC_B_KEDAX 2024-07-29 01:19:13 55
en3 English EJIC_B_KEDAX 2024-07-29 01:18:47 97 Tiny change: 's's lemma](https://en' -> 's's lemma] https://en'
en2 English EJIC_B_KEDAX 2024-07-29 01:09:44 23
en1 English EJIC_B_KEDAX 2024-07-29 00:54:10 6734 Initial revision for English translation (saved to drafts)
ru12 Russian EJIC_B_KEDAX 2024-07-29 00:46:05 1 Мелкая правка: 'Привет Codeforce' -> 'Привет, Codeforce'
ru11 Russian EJIC_B_KEDAX 2024-07-22 02:26:00 5
ru10 Russian EJIC_B_KEDAX 2024-07-22 02:23:16 1674 Мелкая правка: 'ществует. Иначе ра' -> 'ществует. Если $p = 2$, то $i = 1$. Иначе ра'
ru9 Russian EJIC_B_KEDAX 2024-07-22 01:53:33 2378 Мелкая правка: 'oiler>\n\n' -> 'oiler>\n\nНахождение $i$ по модулю $p$\n------------------'
ru8 Russian EJIC_B_KEDAX 2024-07-22 00:46:55 17 Мелкая правка: ' while (x) {\n ' -> ' while (x != 0) {\n '
ru7 Russian EJIC_B_KEDAX 2024-07-22 00:20:46 2467 Мелкая правка: '428K].\n\nКак пров' -> '428K].\n\n==================\nКак пров'
ru6 Russian EJIC_B_KEDAX 2024-07-21 22:58:36 18
ru5 Russian EJIC_B_KEDAX 2024-07-21 22:46:10 73 Мелкая правка: '**Опр.** П' -> '[problem:103428K]**Опр.** П'
ru4 Russian EJIC_B_KEDAX 2024-07-21 22:40:56 1656 Мелкая правка: 'd{p}$.\n\n$$H \c' -> 'd{p}$.\n\n\n$$H \c'
ru3 Russian EJIC_B_KEDAX 2024-07-21 21:39:52 325 Мелкая правка: 'oiler>\n\n' -> 'oiler>\n\n\n'
ru2 Russian EJIC_B_KEDAX 2024-07-21 21:30:49 482 Мелкая правка: 'n**Теорема**: Квадратич' -> 'n**Теорема:** Квадратич'
ru1 Russian EJIC_B_KEDAX 2024-07-21 21:12:13 344 Первая редакция (сохранено в черновиках)