群论的起源及如何判断一个数是否为素数
群论的起源及如何判断一个数是否为素数原创 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），它们通过费马小定理的测试但实际上不是质数。因此，在实际应用中，为了确保准确性，通常需要结合其他的素性测试方法。 大整数的素性测试（就是判断质数），我们有的是快速和确定性的方法，可惜人家没有人重视，用得着啥伪素数（伪质数）？除了合数和1就是素数（也叫质数）哪里有啥伪质数（就是伪素数）了？ 本帖最后由 ysr 于 2023-12-21 05:45 编辑
12345678911~12345679819之间的素数有35个：（用时9.523438秒）
12345678923123456789291234567894912345679007123456791091234567912712345679133123456791871234567919312345679201
12345679219123456792531234567926112345679301123456793191234567932112345679397123456794031234567949912345679501
12345679519123456795471234567957912345679597123456796071234567963712345679649123456796571234567966912345679679
1234567968112345679747123456797831234567979312345679817
代码如下：
'这个代码可以快速判断大素数而且是确定性的
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/forum.php?mod=viewthread&tid=2043350&extra=&page=4 vb语言编的程序速度提不起来，希望高手能把这个快速判断大素数的程序，编程python语言版的程序！
页:
[1]