群论的起源及如何判断一个数是否为素数

luyuanhong

群论的起源及如何判断一个数是否为素数

原创 Adam0505 爱数学之家 2023-12-17 09:30 发表于广东

1. 群论的起源

群论的起源可以追溯到 19 世纪初，当时数学家们开始研究多项式方程的解。他们发现有些方程无法用根式表示出来，这激发了他们对方程解的性质和对称性的进一步研究。

早期的数学家主要关注方程的可解性，即是否存在能够通过根式求解的通用公式。奥古斯特·考迪沃是第一个研究方程根式解之间变换的数学家。他引入了置换群（permutation group）的概念，用于描述方程根之间的变换。

然而，真正推动群论发展的是埃瓦里斯特·伽罗华的工作。在研究五次及以上的方程时，伽罗华发现了方程解无法通过根式求解的限制。他证明了不存在一个通用公式可以用根式求解五次及以上的方程。伽罗华的工作被认为是群论的重大突破之一，开创了群论作为一个独立数学分支的先河。

随后，其他数学家如亚伯拉罕·库莱瓦、费利克斯·克莱因和埃米·诺特等人进一步发展了群论的理论和应用。他们研究了各种类型的群，如有限群、无限群、交换群和李群等，并提出了许多重要的概念和定理。

群论的发展推动了抽象代数学的兴起。与过去只关注方程解的性质不同，群论将焦点转移到了代数结构的共同性质和变换规律上。这使得数学家能够更好地理解和描述代数结构中的对称性。

群论广泛应用于几何学、物理学、密码学、计算机科学和量子力学等众多领域。在几何学中，群论被用于研究对称性和变换。在物理学中，群论为描述粒子的对称性和相互作用提供了基础。在密码学和计算机科学中，群论被用于设计和分析加密算法。在量子力学中，群论是描述粒子行为和对称性的重要工具。

2. 群论的在数论中的几个简单应用

1）原根和剩余类群：在数论中，原根是与模 n 互质的数 a ，使得对于任意 b ，存在一个整数 k ，使得 a^k ≡ b (mod n) 。原根的性质可以通过群论来解释和证明。具体而言，剩余类群（residue class group）是模 n 的整数取模 n 后所形成的群，由模 n 的互质的整数关于乘法运算组成。原根可以看作是剩余类群的生成元。

2）素数的分布：群论方法也可用于研究素数的分布。例如，对于给定的素数 p ，可以研究模 p 的剩余类群，并探究其中的子群、阶数等特征。这种方法经常被应用于素数定理的证明和其他数论问题的研究。

3） 模方程的求解：群论提供了一种有效的方法来解决模方程的求解问题。通过研究模方程的解集构成的群以及其子群，可以确定模方程是否有解以及解的数量。

4）离散对数问题：离散对数问题是数论和密码学中的一个重要问题。群论提供了求解离散对数问题的算法，如 Baby-Step Giant-Step 算法、Pohlig-Hellman 算法和 Index Calculus 算法等。

3. 判断某个数是否为素数

使用群论来证明某个数是质数是一种特定的方法，称为基于群论的素性测试。这种方法利用了群论中的性质和定理来判断一个数是否为质数。

一个常用的基于群论的素性测试方法是费马小定理。费马小定理指出，如果 p 是一个质数，且 a 是与 p 互质的整数，则 a^(p-1) ≡ 1 (mod p) 。这可以通过群论的概念来解释：a 的所有乘方模 p 的结果形成了一个剩余类群，而费马小定理表明，对于任意与 p 互质的 a ，其乘方的结果是在这个群中等于 1 的元素。



因此，可以使用费马小定理来进行素性测试。给定一个数 n ，选择一个与 n 互质的数 a ，并计算 a^(n-1) mod n 的值。如果结果不等于 1 ，则 n 一定不是质数。否则，n 可能是质数，但还需要进一步检查。这个测试并不能确定 n 是否是质数，只能提供部分信息。

尽管基于群论的素性测试方法简单、高效，但并不是完全可靠的。存在一些伪质数（pseudoprime），它们通过费马小定理的测试但实际上不是质数。因此，在实际应用中，为了确保准确性，通常需要结合其他的素性测试方法。

ysr

大整数的素性测试（就是判断质数），我们有的是快速和确定性的方法，可惜人家没有人重视，用得着啥伪素数（伪质数）？除了合数和1就是素数（也叫质数）哪里有啥伪质数（就是伪素数）了？

ysr

12345678911~12345679819之间的素数有35个：（用时9.523438秒）
12345678923  12345678929  12345678949  12345679007  12345679109  12345679127  12345679133  12345679187  12345679193  12345679201
12345679219  12345679253  12345679261  12345679301  12345679319  12345679321  12345679397  12345679403  12345679499  12345679501
12345679519  12345679547  12345679579  12345679597  12345679607  12345679637  12345679649  12345679657  12345679669  12345679679
12345679681  12345679747  12345679783  12345679793  12345679817  

代码如下：
'这个代码可以快速判断大素数而且是确定性的
Private Sub Command1_Click()
Dim a, n
n = Trim(Text1)
n3 = n
m = Trim(Text2)
Do While MBJC(Trim(n), 3) < 0
If MBJC(Trim(n), 2) = 0 Then
m1 = m1 & n & "  "
s = s + 1
Else
m1 = m1
End If
n = n + 1
Loop
If Right(n, 1) Mod 2 = 0 Then
n = MPC1(Trim(n), 1)
Else
n = n
End If
Do While MBJC(Trim(n), Trim(m)) <= 0
If Len(n) < 11 Then
a1 = fenjieyinzi(Trim(n))
If InStr(a1, "*") = 0 Then
s = s + 1
If s Mod 10 = 0 Then
m1 = m1 & n & vbCrLf
Else
m1 = m1 & n & "  "
End If
Else
m1 = m1
End If
Else
n1 = MPC(Trim(n), 1)
a = 123
'a为明文
a1 = zzxc(Trim(n), Trim(a))
If Val(a1) > 1 Then
m1 = m1
Else
c = 999
'c为公约
Do While zzxc(Trim(n1), Trim(c)) > 1
c = Val(c - 1)
Loop
d = qniyuan(Trim(c), Trim(n1))
'd为逆元为私钥
a2 = qksmimo(Trim(a), Trim(c), Trim(n))
'a2为密文
a3 = qksmimo(Trim(a2), Trim(d), Trim(n))
If MBJC(Trim(a3), Trim(a)) = 0 Then
s = s + 1
If s Mod 10 = 0 Then
m1 = m1 & n & vbCrLf
Else
m1 = m1 & n & "  "
End If
Else
m1 = m1
End If
End If
End If
n = MPC1(Trim(n), 2)
Loop
Text3 = n3 & "~" & m & "之间的素数有" & s & "个：" & vbCrLf & m1
End Sub

Private Sub Command2_Click()
Text1 = ""
Text2 = ""
Text3 = ""
End Sub

单位的电脑上的压缩软件被删掉了，传不上来可执行程序，如下文章的第四页有个可执行程序，双击程序图标，解压缩后就可以打开并运行了：

http://www.mathchina.com/bbs/for ... p;extra=&page=4

ysr

vb语言编的程序速度提不起来，希望高手能把这个快速判断大素数的程序，编程python语言版的程序！