想做一个大素数的检测程序

simpley

好多年前写过大数的相乘和乘方程序，现在很无聊，想写个大素数的检测程序，不知道现在的软件一般都能检测到多少位的数。

ysr

如下代码可以判断任意位的整数（只是时间长而已，是我的程序效率低，其他程序或者会其他语言的程序员编的可能就快了，省略了大数的+-*除法运算的自编代码）：

Private Function fenjieyinzi(sa As String) As String
Dim x, A, B
x = sa
B = Int(Sqr(Val(x)) / 2)
If x = 3 Or x = 2 Then
A = True
Else
If x Mod 2 = 0 Then
A = False
Else

For I = 3 To 2 * B + 1 Step 2
If x Mod I = 0 Then
A = False
Exit For

Else: A = True

End If
Next
End If
End If
If A = True Then
fenjieyinzi = "这是个素数"
Else
fenjieyinzi = "2*2"
End If

End Function

Private Function fenjieyinzi0(sa As String) As String
Dim A, n
n = Trim(sa)
If Len(n) < 6 Then
fenjieyinzi0 = fenjieyinzi(Trim(n))
Else
n1 = MPC(Trim(n), 1)
A = 123
'a为明文
a1 = zzxc(Trim(n), Trim(A))
If Val(a1) > 1 Then
fenjieyinzi0 = a1 & "*"
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
fenjieyinzi0 = "这是素数有"
Else
fenjieyinzi0 = "2*2"
End If
End If
End If


End Function

ysr

如下可调用程序，是关于辗转相除法，快速幂模运算和求模的逆元的运算：

Private Function zzxc(sa As String, sb As String) As String
Dim A, B, c, d, r
  A = Trim(sa)
  B = Trim(sb)
  If Len(A) < 10 And Len(B) < 10 Then
  
  If Val(A) > Val(B) Then
     c = A
     d = B
  Else
     c = B
     d = A
  End If
Do Until Val(c) Mod Val(d) = 0
     r = c Mod d
     c = d
     d = r
  Loop
  
  Else
  
  If MBJC(Trim(A), Trim(B)) >= 1 Then
  c = A
  d = B
  Else
  c = B
  d = A
  End If
  Do Until zhengchuqyushu(MCC1(Trim(c), Trim(d))) = 0
  r = zhengchuqyushu(MCC1(Trim(c), Trim(d)))
  c = d
  d = r
  Loop
  End If

  
  zzxc = d
  
End Function

Private Function qniyuan(sa As String, sb As String) As String
Dim n, p, A, B, c, d, r
  n = Trim(sa)
  p = Trim(sb)
  A = 1
  B = 0
  c = 0
  d = 1
  If Len(n) < 10 And Len(p) < 10 Then
  
  If Val(n) > Val(p) Then
     m = n
     q = p
     s1 = 1
  Else
     m = p
     q = n
     s1 = 0
  End If
Do Until Val(m) Mod Val(q) = 0
    s = m \ q
     r = m Mod q
     s1 = s1 + 1
     If s1 Mod 2 = 1 Then
     A = A
     B = A * s + B
     c = c
     d = c * s + d
     Else
     B = B
     A = A + B * s
     d = d
     c = c + d * s
     End If
     m = q
     q = r
  Loop
  If Val(A + B * m) = p Then
  B = B
  A = A + B * (m - 1)
  d = d
  c = c + d * (m - 1)
  Else
  If Val(B + A * m) = p Then
  A = A
  B = B + A * m
  c = c
  d = d + c * m
  Else
  B = B
  A = A + B * (m - 1)
  d = d
  c = c + d * (m - 1)
  End If
  End If
x = (A + B) Mod p
  Y = (c + d) Mod n
  
  
  Else
  
  If MBJC(Trim(n), Trim(p)) >= 1 Then
  m = n
  q = p
  s1 = 1
  Else
  m = p
  q = n
  s1 = 0
  End If
  Do Until zhengchuqyushu(MCC1(Trim(m), Trim(q))) = 0
  s = zhengchuqy(MCC1(Trim(m), Trim(q)))
  r = zhengchuqyushu(MCC1(Trim(m), Trim(q)))
  s1 = s1 + 1
  If s1 Mod 2 = 1 Then
  A = A
  B = MPC1(MbC(Trim(A), Trim(s)), Trim(B))
  c = c
  d = MPC1(MbC(Trim(c), Trim(s)), Trim(d))
  Else
  B = B
  A = MPC1(Trim(A), MbC(Trim(B), Trim(s)))
  d = d
  c = MPC1(Trim(c), MbC(Trim(d), Trim(s)))
  End If
  
  m = q
  q = r
  Loop
  
  If MPC1(Trim(A), MbC(Trim(B), Trim(m))) = p Then
  B = B
  A = MPC1(Trim(A), MbC(Trim(B), MPC(Trim(m), 1)))
  d = d
  c = MPC1(Trim(c), MbC(Trim(d), MPC(Trim(m), 1)))
  Else
  If MPC1(Trim(B), MbC(Trim(A), Trim(m))) = p Then
  A = A
  B = MPC1(Trim(B), MbC(Trim(A), Trim(m)))
  c = c
  d = MPC1(Trim(d), MbC(Trim(c), Trim(m)))
  Else
  B = B
  A = MPC1(Trim(A), MbC(Trim(B), MPC(Trim(m), 1)))
  d = d
  c = MPC1(Trim(c), MbC(Trim(d), MPC(Trim(m), 1)))
  End If
  End If
Do While Left(A, 1) = "0"
    A = Mid(A, 2)
Loop
  
  End If
  
  qniyuan = A
End Function

Private Function qksmimo(sa As String, sb As String, sc As String) As String
Dim c, e, n, d
c = Trim(sa)
e = Trim(sb)
n = Trim(sc)
d = 1
If Len(c) < 5 And Len(e) < 5 And Len(n) < 5 Then
c = Val(c): n = Val(n)
Do While e > 0
If Right(e, 1) Mod 2 = 0 Then
c = c * c Mod n
e = e / 2

Else
d = d * c Mod n
e = e - 1
End If
Loop
Else
c = c
Do While MBJC(Trim(e), 1) >= 0
If Right(e, 1) Mod 2 = 0 Then
c = zhengchuqyushu(MCC1(MbC(Trim(c), Trim(c)), Trim(n)))
e = zhengchuqy(MCC1(Trim(e), 2))
Else
d = zhengchuqyushu(MCC1(MbC(Trim(c), Trim(d)), Trim(n)))
e = MPC(Trim(e), 1)
End If
Loop
End If

qksmimo = d
End Function

ysr

仅仅是对大素数的判断，不能分解大整数

ysr

1000位左右的需要几个小时甚至1天，100位左右的可以在几秒内甚至到几分钟内就判断出来了（还要看硬件的配置，一般台式机快，笔记本电脑慢，甚至慢几倍）

太阳

数学帝国网站，可以判断1000位内的质数

simpley

这是用vb写的吧。我只看了前面的一段，没看到对大数是怎么处理的，只是一般的素数检测代码。尤其是你最后说1000位几小时就搞定，可是公钥密码成立的前提就是400的数几天时间也解不了。

simpley

我怕记忆有误，专门去翻了书，确是400位数已构成公钥密码，依据就是计算机无法在短时间内破解

ysr

simpley 发表于 2025-4-10 04:33
我怕记忆有误，专门去翻了书，确是400位数已构成公钥密码，依据就是计算机无法在短时间内破解

是VB程序设计的，仅仅是判断是否是素数，不能分解因数。
今天大风，我厂没有电了，不敢多开手机 ，手机电不多了，下班回家再充电吧！
我的判断程序，10位内的是常规判断法，超过10位是大数判断法，利用的是欧拉原理，欧拉定理和推论统称欧拉原理。

是不同于费马小定理的原理，是确定性判断，没有反例，不用重复多种方法判定，一次性就可以搞定。

时间之所以长，是程序设计的技术问题，我不会快速程序，大整数的乘法除法都是模仿手工计算的程序，速度很慢。

ysr

ysr 发表于 2025-4-12 19:05
是VB程序设计的，仅仅是判断是否是素数，不能分解因数。
今天大风，我厂没有电了，不敢多开手机 ，手机 ...

程序中没有发出来大数的乘法除法程序，是另外的一个可调用程序。