数论是纯粹数学的分支之一，主要研究整数的性质。

定义

线性筛用于在\(O(n)\)的时间复杂度内求出\(1\ldots n\)的积性函数值。

定义

BSGS 算法用于求解关于\(x\)的方程\(a^x\equiv b\pmod p\)的解。

定义

对于整数 \(a\) 和奇素数 \(p\)，若存在整数 \(x\) 使 \(x^2 \equiv a \pmod p\)，则称 \(a\) 是模 \(p\) 的二次剩余；否则称 \(a\) 是模 \(p\) 的二次非剩余。

定义

素数筛用于求出\([2,n]\)范围内的质数。

定义

Pollard Rho 算法是一种快速分解大整数的随机化算法。

定义

Miller-Rabin 算法是一种随机化素数测试算法。

定义

给出一个线性同余方程组：\(\begin{cases}x\equiv a_1\pmod{m_1}\\x\equiv a_2\pmod{m_2}\\ \ldots \\x\equiv a_n\pmod{m_n}\end{cases}\)，其中\(m_i\)两两互质，中国剩余定理用于求这样的方程组的解。

定义

乘法逆元通常用于在同余式中进行除法运算，其内容为：若\(ax\equiv 1\pmod p\)， 则称\(a\)在模\(p\)意义下的乘法逆元为\(x\)。

莫比乌斯函数

定义

根据唯一分解定理，\(n=\prod_{i=1}^{k} p_i^{a_i}\)。 \(\mu\)定义为 \[\mu(n)=\begin{cases}\mu(1)=1\\ \mu(n)=(-1)^k,\quad \forall a_i=1\\ \mu(n)=0,\quad \exists a_i>1\end{cases} \]