每日小记：Fermat素数
2022.4.13 数学课上学到的一个定理，在IDEA分组密码中会用到
F e r m a t Fermat Fermat素数
定义 形如 F n = 2 2 n + 1 F_n=2^{2^n} +1 Fn=22n+1的数称为 F e r m a t Fermat Fermat数，若 F n F_n Fn是素数，则称其 为 F e r m a t Fermat Fermat素数.
- Fermat 称形如 F n = 2 2 n + 1 , n ∈ N F_n=2^{2^n}+1,n\in N Fn=22n+1,n∈N 的数总是素 数(1630 ∼ 1640)，容易验证 F 0 , F 1 , F 2 , F 3 , F 4 F_0,F_1,F_2,F_3,F_4 F0,F1,F2,F3,F4都是素数.
- 1732 年，Euler 把 F 5 = 4294967297 F_5 = 4294967297 F5=4294967297分解为 641 × 6700417 641 \times 6700417 641×6700417.
- 1750 年，Euler 发表了 “THEOREMATA CIRCA DIVISORSES NVMERORVM”, 一文，文中公开了分解 F 5 F_5 F5 的方法.
欧拉的方法
素因子的形式
如果 ( a , b ) = 1 (a,b)=1 (a,b)=1，则
- a 2 + b 2 a^2+b^2 a2+b2 的素因子具有形式 4 k + 1 4k+1 4k+1
- a 4 + b 4 a^4+b^4 a4+b4 的素因子具有形式 8 k + 1 8k+1 8k+1
- a 8 + b 8 a^8+b^8 a8+b8 的素因子具有形式 16 k + 1 16k+1 16k+1
- a 16 + b 16 a^{16}+b^{16} a16+b16 的素因子具有形式 32 k + 1 32k+1 32k+1
- a 32 + b 32 a^{32}+b^{32} a32+b32 的素因子具有形式 64 k + 1 64k+1 64k+1
穷举
测试 64 × 1 + 1 , 64 × 2 + 1 , . . . , 64 \times 1 + 1,64 \times 2 + 1,... , 64×1+1,64×2+1,..., 不久就能发现 641 641 641
一个验证：
a
=
2
,
b
=
1
,
(
1
,
2
)
=
1
a=2,b =1,(1,2)=1
a=2,b=1,(1,2)=1
由于
5
4
+
2
4
=
641
5^4 + 2^4=641
54+24=641，则
2
32
+
1
(
m
o
d
641
)
=
2
4
×
2
28
+
1
(
m
o
d
641
)
=
−
5
4
×
2
28
+
1
(
m
o
d
641
)
=
−
(
5
×
2
7
)
4
+
1
(
m
o
d
641
)
−
64
0
4
+
1
(
m
o
d
641
)
=
−
(
−
1
)
4
+
1
(
m
o
d
641
)
=
0
2^{32}+1 \pmod {641}=2^4 \times 2^{28} + 1 \pmod{641} =-5^4 \times 2^{28} + 1 \pmod{641} =-(5 \times 2^7)^4+1\pmod{641} -640^4 + 1\pmod{641}=-(-1)^4+1\pmod{641}=0
232+1(mod641)=24×228+1(mod641)=−54×228+1(mod641)=−(5×27)4+1(mod641)−6404+1(mod641)=−(−1)4+1(mod641)=0
Fermat 猜想是错的，但 Fermat 其实比较冤枉。他并非不够谨 慎，事实上他验证了前 5 个 Fermat 数， F 0 , F 1 , F 2 , F 3 , F 4 F_0,F_1,F_2,F_3,F_4 F0,F1,F2,F3,F4，它们 都是素的。而其它的 Fermat 数，个头实在有点大，难以验 证。更冤的是， F 0 , F 1 , F 2 , F 3 , F 4 F_0,F_1,F_2,F_3,F_4 F0,F1,F2,F3,F4 实际上是全部已知的 Fermat
素数，现在倾向于认为几乎全部 Fermat 数都不是素的， 而 Fermat 选的样本刚好就覆盖了全部已知的素的情形！但 是，Fermat 的冤情实在不仅这些，将来我们会学习著名 的 Fermat 小定理，用这个 Fermat 自己提出来的定理，只要花
上一点耐心和体力，就可以计算出 F 5 F_5 F5 其实是个合数！
2022.4.13于B110实验室