42、计算数论基础

计算数论基础

在计算数论领域，质数与合数的相关知识是许多特定构造示例的基础。下面将详细介绍质数与合数的结构和算法相关内容。

1. 质数

质数是指除了 1 和它自身外，不能被其他自然数整除的自然数，规定 1 不是质数。

对于质数 (P)，有以下两个重要的群：
- 模 (P) 的加法群 (Z_P)：由集合 ({0, \ldots, P - 1}) 和模 (P) 的加法运算组成。除单位元 0 外，所有元素的阶都是 (P)。
- 模 (P) 的乘法群 (Z_P^*)：由集合 ({1, \ldots, P - 1}) 和模 (P) 的乘法运算组成，该群是循环群。至少有 (1 / \log_2 P) 的元素的阶为 (P - 1)，这些元素被称为本原元。

1.1 模质数的二次剩余

模质数 (P) 的二次剩余是指存在 (r \in Z_P^*)，使得 (s \equiv r^2 (\bmod P)) 的整数 (s)，所以 (s) 与 (P) 必须互质。
- 若 (r) 是 (s) 模 (P) 的平方根，那么 (-r) 也是，因为 ((-r)^2 \equiv r^2)。
- 若方程 (x^2 \equiv s (\bmod P)) 有解，则恰好有两个解。
模 (P) 的二次剩余构成模 (P) 乘法群的一个子群，该子群包含乘法群一半的元素。模 (P) 的平方运算是群到子群的 2 对 1 映射。当 (P \equiv 3 (\bmod 4)) 时，每个映射的像在子群中有一个原像（二次剩余），在子群外有一个原像（非二次剩余）。

1.2 模质数开平方根

一般情况下，可