梅森素数和Lucas-Lehmer Primality素性检验

梅森素数

$M_m=2^m-1$为梅森数

若$p$为素数且$M_p=2^p-1$为素数，则$M_p$为梅森素数

LLT

设$p$为素数 $r_k=r_{k-1}^{2}-2\left(\mod M_p\right),0\leq r_k\leq M_p$，其中$r_1=4,k\geq 2$ $r_{p-1}\equiv0\left(\mod M_p\right)\Longleftrightarrow M_p$