[研学] 质因数分解及素性判定

时间：2018.10 ~ 2019.3

参加成员：Modem_  Lagoon   _Qijia   mnihyc

感觉这个是人生巅峰了， Lagoon 上清华，剩下我们三也退役了，摆在这留作纪念ww  拿濑户口的话来说，就是萌新那会才是最辉煌的时期www

• 【序言】

质数的研究一直是数学与信息学领域中的重要课题，质数的判定与质因数分解在现代通讯保密领域中更是发挥着重要的作用，本课题小组将通过此次研学机会对不同规模下自然数素性判定及质因数分解的有效算法进行探究，加深对该领域的了解和理解。

• 【1.0】素数的定义

素数，又称质数。一个数 $n$ 是素数当且仅当它是大于 $1$ 的自然数且它的因数有且仅有 $1$ 与 $n$ 。

• 【1.1】记号与规定

1. 1. 记 $\displaystyle\mathbb{R}$ 表示实数集，$\displaystyle\mathbb{N}$ 表示自然数集，$P$ 表示素数集。
   2. 勒让德符号 $\displaystyle\left( {\frac{n}{p}} \right)$。设 $\displaystyle p \in P,n \in \mathbb{N}$。

• 【1.2】素数的一些性质

  • $P$ 是无限集。
  • 对于任意大于 $1$ 的自然数，它要么是个素数，要么可以分解为若干素数之积，并且在忽略顺序的情况下，这样的分解是唯一的。
  • 小于 $n$ 的质数大约有 $\ln n$ 个。
  • 一个合数 $n$ 最小的素因数因数一定小于 $\sqrt n$。
  • 费马小定理：设 $p$ 是大于 $2$ 的素数，则对于任意正整数 $n$ 均有 $\displaystyle \begin{array}{*{20}{c}}{{n^{p – 1}} \equiv 1}&{(\bmod p)}\end{array}$。
  • Mertens’ second theorem。

• 【2.0】素性判定

因为素数集为无限集，并且素数的分布没有规律，所以我们需要实现一个算法来判定一个数是否为素数。而素性判定算法正是这样一类算法：输入一个整数，返回这个数是“素数”还是“合数”。…