注册 登录
编程论坛 → VB6论坛

各位老师好！求助编辑一个大整数的快速乘除法可调用程序

ysr2857 发布于 2020-02-10 23:10， 35105 次点击
我用于判断和筛选10亿内的素数表的程序速度太慢，1亿内的需要3个小时，10亿内的更是24个小时没有结果，只好关闭了，已经是采用了快速判断法，但效果低，原因是不会大整数的快速乘除法程序，希望老师帮助。我仅会一点VB语句，希望是用VB编程的。
我的判断素数的程序，对单个整数几十位的可以迅速判断，素数表就不行了，只能到1亿，单个整数100位以上的也不行。希望老师指点，会快速乘法除法的原理的也请指导帮助！
谢谢！
   祝愿各位老师，新年快乐，阖家幸福安康，万事如意！

[此贴子已经被作者于2020-2-10 23:14编辑过]

401 回复
#52
ysr28572020-02-15 16:49
其中zzxc()为辗转相除判断是否互质，qniyuan()为求乘法的逆元的，qksmimo()为快速幂模算法求余数（或叫明文，密文），这3个程序您都会的吧对你不难，需要的话我可以传上来。也是只传主程序。否则代码太长，超长了，不好传完整的。

[此贴子已经被作者于2020-2-15 16:54编辑过]
#53
ysr28572020-02-15 16:51
有问题随时可以给您解释！谢谢您帮助，非常感谢！
#54
ysr28572020-02-15 17:03
再发一遍，实际做成可调用程序是这个样子：（稍改一下，使用于大于10位的，加了个常规法的判断程序，小于等于10位的用常规法，常规法的程序您也是容易的不发了）
Private Function fenjieyinzi0(n As String) As String
If Len(n) < 11 Then
fenjieyinzi0 = fenjieyinzi(Trim(n))
Else
Dim a
n = Trim(n)
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 = "这是素数有" & Len(n) & "位"
Else
fenjieyinzi0 = "2*2"
End If
End If
 
 
 End If
End Function

[此贴子已经被作者于2021-9-14 21:36编辑过]
#55
ysr28572020-02-15 17:11
其中的MBJC（）为比较大小的程序，因为有时候会遇到大数，其中可能遇到大数运算的地方您可以自己调整为大数的可调用程序。
#56
ysr28572020-02-15 17:22
再发一下那3个可调用程序：（辗转相除法，求乘法逆元，快速幂模计算程序）
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
#57
ysr28572020-02-15 17:29
为了调用方便，合数时输出为2*2，关键是有*号以区别是否是素数。
#58
wmf20142020-02-15 23:55
如果可以的话，你还是提供全面的工程文件吧。
仔细看了你51楼代码，很震惊，完全不是我理解的RSA加解密方式：
1，首先n和c从text中读来的，这个我可以理解，它们做为公钥提供给第三方加密数据的，其中n=p*q，由于p和q是两个非常大的质数，所以你很难通过n逆出p、q
2，n1 = MPC(Trim(n), 1)这是很难理解的，因为后面你的私钥d = qniyuan(Trim(c), Trim(n1))，根据RSA原理，n1=(p-1)*(q-1)，可是你无法从公匙n里逆出pq的，不知道你的代码如何算出pq的。
3，正常的RSA获取公匙私匙的顺序是：首先随机得到两个大素数p和q，依此得到密钥n=p*q，随机选择一个和(p-1)*(q-1)互质的大数e,这个e就是公钥，要进行保密通讯的公司（假设是A公司）可以把n和e公布到互联网上，互联网上任何要和A公司要交换数据的可以把数据用公匙n和e加密，加密后的密文给A公司就行了。最后，由于A公司掌握p和q，A公司可以通过计算(p-1)*(q-1)和公匙e的最大公约数d，这个d就是私匙，A公司就可以用私匙n、d对第三方发过来的密文进行解密了。


[此贴子已经被作者于2020-2-16 00:03编辑过]
#59
ysr28572020-02-16 02:12
回复 58楼 wmf2014
您好！我刚才看到您的回复！您的疑问是不明白原理:
当n值是素数的时候，就不用分解，此时则φ（n）=n-1.（欧拉函数，函数值是n内与n互质的个数，当n=Pq，且pq均为素数时则φ（n）=(p-1)(q-1)，由于n是素数则则φ（n）=n-1.）根据殴拉-费马定理，加解密仍成立（只是不用分解因数了，不保密了），但若n是合数，则不能解密而还原明文。所以，得出判断。

这个是确定性的判断，若能得到大整数的快速乘法除法程序则可判断大的整数，有价值的。
和拉宾-米勒不同，那个是直接利用了费马小定理，而费马小定理的前提和结论不是严格充要条件(这个说法明白吗？大致知道，再多我也不会)所以，逆回去时有反例的，就是有不成立的情况，即使有一个也是不确定的，严格意义上逆命题不成立，但人们发现了反例是少数的，概率高，且可以有方法去掉反例就是把反例再试一次(我是这么理解的没用过那个法)。所以也能用。

而这个法是确定性的，条件和结论可以互推，是充要条件，逆命题或说是逆否命题是成立的。如果方便就有价值。

明白了吗？用的是逆命题或叫逆否命题，还原回去就是逆题，不是求明文而是证明公开模数是素数，结果和明文不相等，就是逆否命题，证明了所要判断的公开模数是合数。(这个明白了吗？为啥没有人这么用？我也不知道。有人这么用过没有？不知道，没见过这么用，我自己想到和实验的，小于5位原理就失效了，明文如果仅用1位的怕不精确，理论上应该是应该是成立的，但是1位的除了0和1不能用，那就只有8种数字了，所以可能不好，要成千上万种情况，真的不敢保证没有丝毫误差，所以我用了3位的明文，就是123，由于123=3*41，所以还要考虑n是否能被3和41整除。) 欢迎试用，欢迎找反例，理论上成立，可靠的，起码我是这么推导证明了一下谢谢！我不是专家再多了讲不了，但我们可以探讨，欢迎试用欢迎沟通，希望您能理解，能帮助我搞出个快速的程序。

可以发完整的程序，太长，明天试试吧！谢谢您！
#60
ysr28572020-02-16 02:54
n=Text1是输入的要判断的整数，c=999是公钥，是设定值，则φ（n）=n1=n-1，要判断c与n1是否互质，否则c=c-1，迭代就选出c了，虽然未严格证明在1～999之间必然能找到c，一般是可以的，1和任何数都互质，但c=1时显然不能用了，程序沒有限制c>1或c>2(因为n1必是偶数)这一条，也许不用限制。(因为999内有一百多素数，当然合数也行只要是互质的，对了，可以改为c=n1-1，这一步也不费劲，这样就完整了，万无一失了)
先这样用，需要的话再改成这一条。
#61
ysr28572020-02-16 02:57
当然，c可以改为1～n1之间的其它值，尽量小一点，这样计算快，我是这样认为的。
#62
ysr28572020-02-16 12:41
回复 58楼 wmf2014
以下是完整的代码，欢迎试用！谢谢您的帮助！有问题欢迎沟通！加了个常规判定程序，小于等于10位的都是常规法判断的，那些中文注释全变？号了，随便改了去掉？号，没有注释了，不理解的随时问我随时解释吧！长，试试能发出来不？

Private Function zhengchuqyushu(sa As String) As String
If InStr(sa, "/") = 0 Then
 zhengchuqyushu = 0
 Else
 zhengchuqyushu = Mid(sa, InStr(sa, "/") + 1)
 End If
 

End Function


Private Function zhengchuqy(sa As String) As String
If InStr(sa, "/") = 0 Then
 zhengchuqy = sa
 Else
 zhengchuqy = Left(sa, InStr(sa, "/") - 1)
 End If
 

End Function


Public Function MBBC(D1 As String) As String 'kai pingfang
If Len(D1) < 10 Then
 jss = Int(Sqr(D1))
 JW = Val(D1) - (jss) ^ 2
  If JW = 0 Then
  MBBC = jss
  Else
  MBBC = jss & "/" & JW
    End If
 Else
Dim x 'shuju changdu
x = Len(D1) \ 4
D2 = String(4 - Len(D1) + 4 * x, "0") & D1
Dim a() As String
ReDim a(4 To 4 * x + 4)
Dim b() As String
ReDim b(2 To 2 * x)
Dim I, J, js
  For I = 4 To 4 * x + 4 Step 4
  
a(I) = Mid(D2, I - 3, 4)
js = Int(Sqr(Val(a(4) & a(8))))
 JW = Val(a(4) & a(8)) - (js) ^ 2
 Next
   J = 4
   Do While J <= 2 * x
   
   jws = MPC1(JW & "0000", a(2 * J + 4))
   If MBJC(Trim(jws), MbC(Trim(js), 200)) <= 0 Then
    b(J) = "00"
    Else
    jwc = Left(jws, Len(jws) - Len(MbC(Trim(js), 200)) + 2) \ Left(MbC(Trim(js), 200), 2)
    If Len(jwc) > 2 Then
     b(J) = 99
     Else
     b(J) = jwc
     End If
   
     
     Do While MBJC(Trim(jws), MbC(MPC1(b(J), MbC(Trim(js), 200)), b(J))) = -1
     
     b(J) = b(J) - 1
     
               Loop
          End If
          JW = MPC(Trim(jws), MbC(MPC1(MbC(200, Trim(js)), b(J)), b(J)))
      
     js = MPC1(MbC(Trim(js), 100), Trim(b(J)))
     
      
   J = J + 2
   If JW = 0 Then
      
   MBBC = js
   Else
   MBBC = js & "/" & JW
   End If
   Loop
   
 End If
End Function

Public Function MBJC(D1 As String, D2 As String) As String ';bijiao
If Len(D1) <= 10 And Len(D2) <= 10 Then
If Val(D1) > Val(D2) Then
MBJC = 1
Else
If Val(D1) = Val(D2) Then
MBJC = 0
Else
MBJC = -1
End If
End If
Else

If Len(D1) > Len(D2) Then
MBJC = 1
Else
If Len(D1) < Len(D2) Then
MBJC = -1
Else
If Len(D1) = Len(D2) Then
 Dim x, Y
 x = Len(D1) \ 4: Y = Len(D2) \ 4
 Dim a() As String, b() As String
 ReDim a(4 To 4 * x + 4)
 ReDim b(4 To 4 * Y + 4)
 If Val(Left(D1, Len(D1) - 4 * x)) > Val(Left(D2, Len(D2) - 4 * Y)) Then
  MBJC = 1
  Else
  If Val(Left(D1, Len(D1) - 4 * x)) < Val(Left(D2, Len(D2) - 4 * Y)) Then
  MBJC = -1
  Else
  For I = 4 To 4 * x Step 4
  a(I) = Mid(D1, Len(D1) - I + 1, 4)
  b(I) = Mid(D2, Len(D2) - I + 1, 4)
  Next
  J = 4 * x
  Do While a(J) = b(J) And J >= 8
  
  J = J - 4
     Loop
     
     
   If Val(a(J)) - Val(b(J)) > 0 Then
   MBJC = 1
   Else
   If Val(a(J)) - Val(b(J)) < 0 Then
   MBJC = -1
   Else
   MBJC = 0
   End If
   
  End If
  
  
  
 End If
End If
End If
End If
End If
End If
End Function

Public Function MCC(D1 As String, D2 As String) As String '程序
If Len(D1) < Len(D2) Then
   MCC = "0" & "/" & D1
   Else
   If Len(D1) < 9 Then
    MCC = Val(D1) \ Val(D2) & "/" & Val(D1) - (Val(D1) \ Val(D2)) * Val(D2)
     If Mid(MCC, InStr(MCC, "/") + 1) = 0 Then
  MCC = Left(MCC, InStr(MCC, "/") - 1)
 Else
MCC = MCC
End If
   
    Else
   
   Dim x ';fen duan changdu
   x = Len(D1)
   
     
   
     Dim a() As String
      ReDim a(1 To x)  '程序
      For I = 1 To x Step 1  '程序
       a(I) = Mid(D1, I, 1)
        
      
       Next I
      Dim b() As String
      JW = 0
     ReDim b(1 To x)
     For J = 1 To x Step 1
    b(J) = Val(JW & a(J)) \ Val(D2)
      JW = Val(JW & a(J)) - Val(b(J)) * Val(D2)
       Next J
       For r = 1 To x
       If JW = 0 Then
          MCC = MCC & b(r)
          Else
          CJ = CJ & b(r)
          MCC = CJ & "/" & JW
      
    End If
   
    For I = 1 To Len(MCC)
   If Not Mid(MCC, I, 1) = "0" Then
       Exit For
   End If
Next
strtmp = Mid(MCC, I)
 If Len(strtmp) = 0 Then
 MCC = "0"
 Else
MCC = strtmp
End If
   
   Next
   
   End If
     
     End If
   
End Function
 
 Public Function MCC1(D1 As String, D2 As String) As String '去问号
Dim ss
 ss = MBJC(D1, D2)
If ss = -1 Then
 MCC1 = "0" & "/" & D1
  Else
  If ss = 0 Then
   MCC1 = 1
   Else
   If Len(D1) = Len(D2) Then
     s = Val(Left(D1, 1)) \ Val(Left(D2, 1))
 
 Do While MBJC(MbC(Trim(s), Trim(D2)), D1) = 1
  s = s - 1
  Loop
  If MBJC(MbC(Trim(s), Trim(D2)), D1) = 0 Then
   MCC1 = s
   Else
   MCC1 = s & "/" & MPC(Trim(D1), MbC(Trim(s), Trim(D2)))
 
 End If
    Else
    If Len(D2) < 9 Then
     MCC1 = MCC(D1, D2)
     Else
    Dim x, Y '变问号了咋
    x = Len(D1): Y = Len(D2)
   
Dim JW, jcc, jss, jcs
 
  Dim a() As String, b() As String
  
  ReDim a(1 To x)
  ReDim b(1 To Y)
  For I = 1 To x
  a(I) = Mid(D1, I, 1)
  Next
  For J = 1 To Y
  b(J) = Mid(D2, J, 1)
  Next
  jcc = Val(a(1) & a(2)) \ Val(b(1) & b(2))
   
      
        
  jss = MbC(Trim(jcc), D2)
   For i1 = 1 To Y
    jws = jws & a(i1)
      Next
      
      Do While MBJC(Trim(jws), Trim(jss)) = -1
      jcc = jcc - 1
      jss = MbC(Trim(jcc), D2)
      Loop
  JW = MPC(Trim(jws), Trim(jss))
  
    z = x - Y
   
    Dim c() As String
    ReDim c(1 To z)
    For s = 1 To z
     If MBJC(JW & a(s + Y), D2) = -1 Then
       c(s) = "0"
       Else
     jwc = Val(Left(JW & a(s + Y), 3)) \ Val(Left(D2, 2))
      If Len(jwc) > 1 Then
      c(s) = "9"
       Else
        c(s) = jwc
         End If
      
     Do While MBJC(JW & a(s + Y), MbC(Val(c(s)), D2)) = -1
    c(s) = Right(10000 + Val(c(s) - 1), 1)
     Loop
     End If
   
     JW = MPC(JW & a(s + Y), MbC(Val(c(s)), D2))
     
    jcc = jcc & c(s)
    Next s
    If JW = 0 Then
    MCC1 = jcc
    Else
    MCC1 = jcc & "/" & JW
    End If
   
  For I = 1 To Len(MCC1)
    If Not Mid(MCC1, I, 1) = "0" Then
        Exit For
    End If
Next
strtmp = Mid(MCC1, I)
  If Len(strtmp) = 0 Then
  MCC1 = "0"
  Else
MCC1 = strtmp
 End If
   
   
   
    End If
   
   
   
   
   
  
  End If
End If
End If
End Function
Public Function MbC(D1 As String, D2 As String) As String '???
Dim x, Y '啥变问号了
x = Len(D1): Y = Len(D2)
Dim a() As Integer
ReDim a(1 To x + Y, 1 To Y)
Dim I, J, C1, C2, CJ, JW
For J = Y To 1 Step -1 'D2
JW = 0 '??λ??0
C2 = Mid$(D2, J, 1) '啥
For I = x To 1 Step -1 'D1
  C1 = Mid$(D1, I, 1) '啥
  CJ = C1 * C2 + JW '位
  c = I + J: r = Y + 1 - J
  a(c, r) = CJ Mod 10 '我弄不清了变问号改一下去掉问号而已
JW = CJ \ 10 '位
Next
a(c - 1, r) = JW
Next
Dim b() As Integer
ReDim b(1 To x + Y)
JW = 0
For I = x + Y To 1 Step -1
Bit = JW
For J = 1 To Y
  Bit = Bit + a(I, J)
Next
b(I) = Bit Mod 10
JW = Bit \ 10
Next
If b(1) > 0 Then
MbC = MbC & b(1)
Else
MbC = MbC
End If
For I = 2 To x + Y
MbC = MbC & b(I)
Next
End Function

 Public Function MPC(D1 As String, D2 As String) As String ';jianfaqi
Dim x, Y '定义长度
If Len(D1) >= Len(D2) Then
D4 = String(Len(D1) - Len(D2), "0") & D2
d3 = D1
Else
D4 = D2
d3 = String(Len(D2) - Len(D1), "0") & D1
End If
x = Len(d3): Y = Len(D4)
Dim a() As Integer, B1() As Integer, C1() As Integer, E1() As Integer
ReDim a(1 To x)
ReDim B1(1 To Y)
ReDim C1(1 To x)
ReDim E1(1 To x)
Dim I, J, C2, CJ, JW
For J = Y To 1 Step -1 ';D2
JW = 1 ';yu jie weichuzhi
B1(J) = Mid(D4, J, 1) ';?λ??
For I = x To 1 Step -1  ';D1
   a(I) = Mid(d3, I, 1) ';?λ??
   C1(I) = 10 + a(I) - B1(I) - 1 + JW ';????jia
   JW = C1(I) \ 10
   E1(I) = C1(I) Mod 10
  Next
  Next
  For r = 1 To x
  MPC = MPC & E1(r)
  For I = 1 To Len(MPC)
    If Not Mid(MPC, I, 1) = "0" Then
        Exit For
    End If
Next
strtmp = Mid(MPC, I)
  If Len(strtmp) = 0 Then
  MPC = "0"
  Else
MPC = strtmp
End If
  Next
  
  
End Function
  Public Function MPC1(D1 As String, D2 As String) As String 'jiafa
Dim x, Y '????????

If Len(D1) >= Len(D2) Then
D4 = String(Len(D1) - Len(D2), "0") & D2
d3 = D1
Else
D4 = D2
d3 = String(Len(D2) - Len(D1), "0") & D1
End If
x = Len(d3): Y = Len(D4)
Dim a() As Integer, B1() As Integer, C1() As Integer, E1() As Integer
ReDim a(1 To x)
ReDim B1(1 To Y)
ReDim C1(1 To x)
ReDim E1(1 To x)
Dim I, J, C2, CJ, JW
For J = Y To 1 Step -1 'D2
JW = 0 '??λ??0
B1(J) = Mid$(D4, J, 1) '?λ??
For I = x To 1 Step -1  'D1
   a(I) = Mid$(d3, I, 1) '?λ??
   C1(I) = a(I) + B1(I) + JW '????jia
   JW = C1(I) \ 10
   E1(I) = C1(I) Mod 10
  Next
  Next
  For r = 1 To x
  If JW = 0 Then
  MPC1 = MPC1 & E1(r)
  Else
  jc = jc & E1(r)
  MPC1 = JW & jc
  End If
  Next
  
End Function


 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
 
 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 Right(X, 1) Mod 2 = 0 Then
a = False
Else

For I = 3 To 2 * B + 1 Step 2
If InStr(X / 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 Sub Command1_Click()
Dim a, n
n = Trim(Text1)
If Len(n) < 11 Then
Text2 = fenjieyinzi(Trim(n))
Else
n1 = MPC(Trim(n), 1)
a = 123
'a为明文
a1 = zzxc(Trim(n), Trim(a))
If Val(a1) > 1 Then
Text2 = 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
Text2 = "这是素数有" & Len(n) & "位"
Else
Text2 = "2*2"
End If
End If
End If
End Sub

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

End Sub




[此贴子已经被作者于2021-9-14 21:47编辑过]
#63
wmf20142020-02-16 12:57
回复 59楼 ysr2857
嗯，理论上是可以的，这样做别人解密也是so easy。
当初做RSA时对什么欧拉函数、费马大定理等也是狠狠啃过的，代码通过后就扔了。我现在对什么扩展欧几里得算法求乘法逆元都搞不清楚是啥玩意了，好像是假设n-1、d互质，可以找到一个因子e让式子e*d-e*(e*d mod (n-1))=1成立吧，这个因子e就是用于解密的私匙。
有空再啃啃。
做RSA加解密的基础是大数的加减乘除和取余，我记得当初做时，为了提高运算速度，充分利用了cpu的运算能力，都在16进制下运算，比那种纯数字字符串大数运算的效率高，除法使用了二分法求商，效率也还可以。至于那种用分治法的快速乘法算法我也不会弄，有空去学习下。
如果代码太多，你可以只提供你的大数运算代码，我看看有改进优化的空间没有。
#64
ysr28572020-02-16 13:27
回复 63楼 wmf2014
对，一般是e为公钥，d为私钥，e，d互为逆元，都能用，反过来也成立。
#65
ysr28572020-02-16 13:34
回复 63楼 wmf2014
二分法求商的除法程序请你给我发一下！我的除法慢，效率低，仿手工计算的。
我的大数运算程序都在上面了，都是可调用程序，已经完整了，可以直接复制代码运行试验了。
欢迎试验！
欢迎帮助指导！谢谢指教！
#66
ysr28572020-02-16 13:42
是e*d mod  (n-1) =1.这就是e叫d的乘法逆元，或叫e模(n-1)的逆元为d，e和d互为逆元，可以互推的，上面的可调用程序qniyuan()就可以求出来，输入e和(n-1)，输出d.
#67
ysr28572020-02-16 13:52
MPC1()为大数加法，MPC()为大数的减法，MbC( )为大数的乘法，MCC1()为大数的除法，
MCC( )为除数少于8位的大数的除法，MBBC( )为大数开平方。
这些程序您有快速的效果好的都可以发过来！请教了，向您学习学习！谢谢！
#68
ysr28572020-02-16 13:59
凡是合数程序输出结果都是2*2或3*，有个*号，凡是素数程序输出结果都是这是素数。
程序只做判断，不分解因数。
#69
wmf20142020-02-16 14:17
我们的设计理念不一样，在c里我是把2^32当作一位做运算，你是按十进制位做运算，效率肯定低，不过仍有改进优化空间，我试着按你的思路改进下，要花点时间。
#70
ysr28572020-02-16 15:06
好，谢谢！期待好的程序！您慢慢弄，不行的话，请把你的二分法求商值的除法程序发一下！
谢谢您！
#71
wmf20142020-02-16 18:12
回复 70楼 ysr2857
给你的代码加了个运行时间输出，你这个判断54位的素数时间太长了，需要78秒，我记得我的那个判断300位十进制数是否为素数用时不超过10毫秒。
程序代码：
Private Sub Command1_Click()
Dim a, n
Dim t As Double
t = Timer
n = Trim(Text1)
If Len(n) < 6 Then
Text2 = fenjieyinzi(Trim(n))
Else
n1 = MPC(Trim(n), 1)
a = 123
'a为明文
a1 = zzxc(Trim(n), Trim(a))
If Val(a1) > 1 Then
Text2 = 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
Text2 = "这是素数有" & Len(n) & "位,用时" & Timer - t & "秒"
Else
Text2 = "2*2"
End If
End If
End If
End Sub


只有本站会员才能查看附件，请 登录
#72
ysr28572020-02-16 18:29
很好！是的，我的程序效率低，所以要搞出快速版大数运算程序。谢谢！希望您能给予指导！
与常规法验证比较举例:(这个程序仅仅是判断不做分解因数)
输入9999997，输出2*2，就是说是合数。
常规法:9999997=7*1428571。
输入1428571，输出:这是素数有7位。
常规法:1428571，这是个素数.
#73
ysr28572020-02-17 09:48
欢迎给予指导！欢迎给出快速乘法除法程序！祝各位老师朋友新春愉快！
#74
ysr28572020-02-17 15:20
介绍一下素数的判定原理方法：常规法是把整数的方根内的素数都试除一下，不能整除的就是素数。速度太慢。
筛法：把某数内的整数编号，把其方根内的素数的倍数去掉而剩下的是素数，效率高，占内存，不能算的太多。
拉宾-米勒法：利用费马定理，多试几个素数，也是利用前面用到的快速幂模程序，速度快概率高，而不是确定性的，有限个内人们知道某些数是会漏掉，可以排除，太大的数就不确定虽然概率高也是不确定性的算法。
还有一种是叫AKS算法：是确定性的，是三位顶级高手，顶级数学家搞出来的，是外国人。速度快，确定性的，可以计算大整数，但原理复杂，不容易实现，非高手编不了程序。我也理解不了具体原理。

前面的方法，比拉宾米勒靠谱，比AKS方便，是不是我的首发？不知道。
原理容易实现，我已经做出来了程序，但我的程序用到的大数计算程序速度慢，是用低效的程序做高效工作，凭的优良的数学原理方法和简捷的步骤，所以要做个快速乘法除法程序，这样就快速方便了。咱不图名不图利，自己方便感兴趣的朋友用到的方便，就好！
欢迎感兴趣的沟通探讨，欢迎给出快速乘法除法程序。

[此贴子已经被作者于2020-2-17 15:29编辑过]
#75
ysr28572020-02-17 17:24
我有个加解密软件，原理方法是与前面的体制完全不同的，是采用了随机密码或叫伪随机密码，密码规则是伪随机的，用于加密文本文件。同一个文件每点击一次产生的密文是不同的，不能用无穷枚举法，概率法等暴力攻击法破解的，不知道有没有用，起码可以当智力游戏玩，或朋友间密码通信（游戏活动），有感兴趣的朋友我可以发一下。
#76
smitest2020-02-17 21:30
qq347895961联系
#77
ysr28572020-02-18 01:19
回复 76楼 smitest
搜索不到，是qq还是微信？
#78
ysr28572020-02-18 10:23
回复 71楼 wmf2014
您好！有qq或微信吗？欢迎联系！大整数的快速乘法除法程序至今我也弄不出来，请帮忙！
#79
wmf20142020-02-18 12:18
回复 78楼 ysr2857
这两天要参加疫情防控，每天都要值班十小时以上，没精力弄。
今天休息，弄了下，仅仅在修改大数加减乘的情况下，就可以做到20秒完成，比你的速度快尽4倍，但除法无法达到要求。经调试你的除法，发现你输出结果包含余数，也按照你的要求输出余数，仍然得不到正确结果，我反复测试我的除法没问题的，是不是你的除法还包含了其他输出功能？
只有本站会员才能查看附件，请 登录
#80
ysr28572020-02-18 12:33
回复 79楼 wmf2014
谢谢！已经不错了，辛苦了！我的除法没有其它功能，只是分类计算的，比如除数小于8位的就转为MCC()了。可能是这样吧，也是调试多少次多种类型才弄对的，有的类型过不去正常，只是一时找不到哪里错，慢慢会找到的，你可以重新编个除法程序，谢谢！
#81
ysr28572020-02-18 12:53
输出余数的除法结果：123456789876543/987654321=124999/987405864，
输出带小数点的除法：123456789876543/987654321=124999.9997484372。
#82
ysr28572020-02-18 12:57
我的除法只算到整数部分，要得到小数点后的商值被除数末尾必须补0，精确几位补几个0.
#83
ysr28572020-02-18 18:41
回复 79楼 wmf2014
当余数为0的时候不要输出/0，因为判断是否整除的时候是以有没有/号为标准的，这一点要注意！
#84
ysr28572020-02-18 23:23
回复 79楼 wmf2014
下面是网上找到的用vc编程的fft快速高精度乘法程序，我看不懂，请看看，翻译成vb可调用程序，谢谢！
#include<bits/stdc++.h>
using namespace std;
//complex是stl自带的定义复数的容器
typedef complex<double> cp;
#define N 2097153
//pie表示圆周率π
const double pie=acos(-1);
int n;
cp a[N],b[N];
int rev[N],ans[N];
char s1[N],s2[N];
//读入优化
int read(){
    int sum=0,f=1;
    char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
    return sum*f;
}
//初始化每个位置最终到达的位置
{
    int len=1<<k;
    for(int i=0;i<len;i++)
    rev[i]=(rev[i>>1]>>1)|((i&1)<<(k-1));
}
//a表示要操作的系数，n表示序列长度
//若flag为1，则表示FFT，为-1则为IFFT(需要求倒数）
void fft(cp *a,int n,int flag){
    for(int i=0;i<n;i++)
    {
     //i小于rev[i]时才交换，防止同一个元素交换两次，回到它原来的位置。
      if(i<rev[i])swap(a[i],a[rev[i]]);
    }
    for(int h=1;h<n;h*=2)//h是准备合并序列的长度的二分之一
    {
    cp wn=exp(cp(0,flag*pie/h));//求单位根w_n^1
     for(int j=0;j<n;j+=h*2)//j表示合并到了哪一位
     {
      cp w(1,0);
       for(int k=j;k<j+h;k++)//只扫左半部分，得到右半部分的答案
       {
         cp x=a[k];
         cp y=w*a[k+h];
         a[k]=x+y;  //这两步是蝴蝶变换
         a[k+h]=x-y;
         w*=wn; //求w_n^k
       }
     }
     }
     //判断是否是FFT还是IFFT
     if(flag==-1)
     for(int i=0;i<n;i++)
     a[i]/=n;
}
int main(){
    n=read();
    scanf("%s%s",s1,s2);
    //读入的数的每一位看成多项式的一项，保存在复数的实部
    for(int i=0;i<n;i++)a[i]=(double)(s1[n-i-1]-'0');
    for(int i=0;i<n;i++)b[i]=(double)(s2[n-i-1]-'0');
    //k表示转化成二进制的位数
    int k=1,s=2;
     while((1<<k)<2*n-1)k++,s<<=1;
    init(k);
    //FFT 把a的系数表示转化为点值表示
    fft(a,s,1);
    //FFT 把b的系数表示转化为点值表示
    fft(b,s,1);
    //FFT 两个多项式的点值表示相乘
    for(int i=0;i<s;i++)
    a[i]*=b[i];
    //IFFT 把这个点值表示转化为系数表示
    fft(a,s,-1);
    //保存答案的每一位(注意进位）
    for(int i=0;i<s;i++)
    {
    //取实数四舍五入，此时虚数部分应当为0或由于浮点误差接近0
    ans[i]+=(int)(a[i].real()+0.5);
    ans[i+1]+=ans[i]/10;
    ans[i]%=10;
    }
    while(!ans[s]&&s>-1)s--;
    if(s==-1)printf("0");
    else
    for(int i=s;i>=0;i--)
    printf("%d",ans[i]);
    return 0;
}
#85
ysr28572020-02-19 06:05
回复 79楼 wmf2014
给出一个超大整数快速求商的原理图，您是否能编程vb版程序：
只有本站会员才能查看附件，请 登录

对于超大整数步骤是这样：
初始：c=0，i>=0
1，满足被除数>=2^i*除数，得到最大的i0.c=c+2^i0.
新的被除数=被除数-2^i0*除数。
2，满足新被除数>=2^i*除数的最大的i1.c=c
3，若2^0=1>=2^i的i不存在，则商c=c+2^0.
我是这么理解的。
速度取决于求2^i的速度，以及比较大小的速度，行不行？请指导！
（我的理解第一步和第二步都是迭代，第三步i已经等于0，无需迭代仅是个判断。）

[此贴子已经被作者于2020-2-19 06:24编辑过]
#86
ysr28572020-02-19 07:04
我觉得i不用从0开始算就可以得到i0及i1，方法：
被除数的位数减掉除数的位数，设差为x，x乘以0.3010就是i，因为log2=0.3010，而x*log2是2^i的位数，此时结果要小一点，比如减1或2，再迭代就可以减少迭代次数，（试了一下，不对，太大，应该令x1=x+1，迭代，当x1*log2=x时的x1的值。）
下一步类似，求出i1的近似值，要小于i1，就是新被除数的位数减掉除数的位数 ，再用上面的方法求出i1的近似值再迭代，直到i等于0为止。
当然，若被除数的位数和除数的位数的比值是1，那就可以从0开始算了。
我先试一下，如果成立把程序发一下，请您优化一下。

[此贴子已经被作者于2020-2-19 10:01编辑过]
#87
ysr28572020-02-19 11:33
这种方法不能实现，速度也许快，弄不准确，第一步就无法调整，多乘一次2则过大，远大于实际，少乘一次又过小。请把我发在84楼的vc程序翻译成vb程序吧，谢谢！欢迎指导！欢迎沟通！
#88
wmf20142020-02-21 23:56
大致知道你确定大素数的思想了：n是素数，和n的互质数有n-1个，找到一个和n-1互质的数c，求出逆元d，用n和c对明文a加密得到密文b，用n和d对b解密得到a1，如果a1=a则说明n是素数，反之不是。
问题是这个理论能否成立呢？我感觉以往做rsa时，有些合数也可以正确加解密的。我是用Miller-Rabin检测大数素性的，但是要找到P、Q两个随机大素数很费时（我通常使用的P、Q都在十进制120位以上），用时多在10分钟以上，为了加快速度，我不断减少Miller-Rabin算法的检测样本数，我发现在很多时候都能实现加解密，Miller-Rabin算法是无法确保得到大质数的，我总感觉其中好多次在P、Q不是质数时也通过了加解密。
抽空用c做下。
我做的大数除法没有你快，我的除法过份依赖乘法和加法，但用我的加减乘配合你的除法可以大幅度提高运算速度，代码在下面工程里，你可以参考下：

我提供的是工程目录及相关文件的压缩包，解压后就可用vb打开这个工程了，你不会连解压缩文件都没有吧！全部代码如下：

程序代码：

Private Function zhengchuqyushu(sa As String) As String
'获取余数
If InStr(sa, "/") = 0 Then

 zhengchuqyushu = 0

 Else

 zhengchuqyushu = Mid(sa, InStr(sa, "/") + 1)

 End If
End Function


Private Function zhengchuqy(sa As String) As String
'获取商
If InStr(sa, "/") = 0 Then

 zhengchuqy = sa

 Else

 zhengchuqy = Left(sa, InStr(sa, "/") - 1)

 End If
End Function


Public Function MBBC(d1 As String) As String 'kai pingfang
If Len(d1) < 10 Then

 jss = Int(Sqr(d1))

 JW = Val(d1) - (jss) ^ 2
  If JW = 0 Then
  MBBC = jss
  Else
  MBBC = jss & "/" & JW
    End If

 Else
Dim x 'shuju changdu
x = Len(d1) \ 4
d2 = String(4 - Len(d1) + 4 * x, "0") & d1
Dim a() As String
ReDim a(4 To 4 * x + 4)
Dim b() As String
ReDim b(2 To 2 * x)
Dim i, j, js
  For i = 4 To 4 * x + 4 Step 4
  
a(i) = Mid(d2, i - 3, 4)
js = Int(Sqr(Val(a(4) & a(8))))

 JW = Val(a(4) & a(8)) - (js) ^ 2

 Next
   j = 4
   Do While j <= 2 * x
   
   jws = MPC1(JW & "0000", a(2 * j + 4))
   If MBJC(Trim(jws), MbC(Trim(js), 200)) <= 0 Then
    b(j) = "00"
    Else
    jwc = Left(jws, Len(jws) - Len(MbC(Trim(js), 200)) + 2) \ Left(MbC(Trim(js), 200), 2)
    If Len(jwc) > 2 Then
     b(j) = 99
     Else
     b(j) = jwc
     End If
   
     
     Do While MBJC(Trim(jws), MbC(MPC1(b(j), MbC(Trim(js), 200)), b(j))) = -1
     
     b(j) = b(j) - 1
     
               Loop
          End If
          JW = MPC(Trim(jws), MbC(MPC1(MbC(200, Trim(js)), b(j)), b(j)))
      
     js = MPC1(MbC(Trim(js), 100), Trim(b(j)))
     
      
   j = j + 2
   If JW = 0 Then
      
   MBBC = js
   Else
   MBBC = js & "/" & JW
   End If
   Loop
   

 End If
End Function

Public Function MBJC(d1 As String, d2 As String) As String ';bijiao
If Len(d1) <= 10 And Len(d2) <= 10 Then
If Val(d1) > Val(d2) Then
MBJC = 1
Else
If Val(d1) = Val(d2) Then
MBJC = 0
Else
MBJC = -1
End If
End If
Else

If Len(d1) > Len(d2) Then
MBJC = 1
Else
If Len(d1) < Len(d2) Then
MBJC = -1
Else
If Len(d1) = Len(d2) Then

 Dim x, Y

 x = Len(d1) \ 4: Y = Len(d2) \ 4

 Dim a() As String, b() As String

 ReDim a(4 To 4 * x + 4)

 ReDim b(4 To 4 * Y + 4)

 If Val(Left(d1, Len(d1) - 4 * x)) > Val(Left(d2, Len(d2) - 4 * Y)) Then
  MBJC = 1
  Else
  If Val(Left(d1, Len(d1) - 4 * x)) < Val(Left(d2, Len(d2) - 4 * Y)) Then
  MBJC = -1
  Else
  For i = 4 To 4 * x Step 4
  a(i) = Mid(d1, Len(d1) - i + 1, 4)
  b(i) = Mid(d2, Len(d2) - i + 1, 4)
  Next
  j = 4 * x
  Do While a(j) = b(j) And j >= 8
  
  j = j - 4
     Loop
     
     
   If Val(a(j)) - Val(b(j)) > 0 Then
   MBJC = 1
   Else
   If Val(a(j)) - Val(b(j)) < 0 Then
   MBJC = -1
   Else
   MBJC = 0
   End If
   
  End If
  
  
  

 End If
End If
End If
End If
End If
End If
End Function

Public Function MCC(d1 As String, d2 As String) As String '程序
If Len(d1) < Len(d2) Then
   MCC = "0" & "/" & d1
   Else
   If Len(d1) < 9 Then
    MCC = Val(d1) \ Val(d2) & "/" & Val(d1) - (Val(d1) \ Val(d2)) * Val(d2)
     If Mid(MCC, InStr(MCC, "/") + 1) = 0 Then
  MCC = Left(MCC, InStr(MCC, "/") - 1)

 Else
MCC = MCC
End If
   
    Else
   
   Dim x ';fen duan changdu
   x = Len(d1)
   
     
   
     Dim a() As String
      ReDim a(1 To x)  '程序
      For i = 1 To x Step 1  '程序
       a(i) = Mid(d1, i, 1)
        
      
       Next i
      Dim b() As String
      JW = 0
     ReDim b(1 To x)
     For j = 1 To x Step 1
    b(j) = Val(JW & a(j)) \ Val(d2)
      JW = Val(JW & a(j)) - Val(b(j)) * Val(d2)
       Next j
       For r = 1 To x
       If JW = 0 Then
          MCC = MCC & b(r)
          Else
          CJ = CJ & b(r)
          MCC = CJ & "/" & JW
      
    End If
   
    For i = 1 To Len(MCC)
   If Not Mid(MCC, i, 1) = "0" Then
       Exit For
   End If
Next
strtmp = Mid(MCC, i)

 If Len(strtmp) = 0 Then

 MCC = "0"

 Else
MCC = strtmp
End If
   
   Next
   
   End If
     
     End If
   
End Function

 
Public Function mComp(ByVal d1 As String, ByVal d2 As String) As Integer
  '大数比较函数，-1:d1<d2  0:d1=d2 1:d1>d2
'  mComp = Val(Left(MPC(D1, D2), 2))
'  If mComp <> 0 Then mComp = Int(mComp / Abs(mComp))
'  Exit Function
  Dim i As Integer, j As Integer
  mFormat d1
  mFormat d2
  i = Len(d1)
  j = Len(d2)
  mComp = 1
  If i = j Then
    If d1 = d2 Then mComp = 0
    If d1 < d2 Then mComp = -1
  Else
    If i < j Then mComp = -1
  End If
End Function

Public Function mFormat(d As String) As Integer
  '格式化数据，将数据格式化为纯数字，非数字字符替换为0，大数为负数则去掉负号并返回-1，否则返回1
  Dim i As Integer, a As String, b As String
  a = Trim(d)
  d = ""
  mFormat = 1
  If Left(a, 1) = "-" Then mFormat = -1
  For i = 1 To Len(a)
    '本循环将大数中非数字字符用数字0代替，如-123a456=01230456
    b = Mid(a, i, 1)
    If b >= "0" And b <= "9" Then
      d = d & b
    Else
      d = d & "0"
    End If
  Next
  For i = 1 To Len(d)
    If Mid(d, i, 1) > 0 Then Exit For
  Next
  d = Right(d, Len(d) + 1 - i) '消前导0，如0000123456=123456
  If d = "" Then d = "0"
End Function

Public Function MCC1(d1 As String, d2 As String) As String '去问号
Dim ss As String, s As Integer
'MCC1 = MCC3(d1, d2)
'Exit Function             '去掉这两句的单引号就会用我的大数除法，速度慢，需要300秒，注释掉后就会用题主的除法算法，20多秒可以完成
ss = MBJC(d1, d2)
If Val(ss) = -1 Then
  MCC1 = "0" & "/" & d1
Else
  If Val(ss) = 0 Then
    MCC1 = 1
  Else
    If Len(d1) = Len(d2) Then
      s = Val(Left(d1, 1)) \ Val(Left(d2, 1))
      Do While MBJC(MbC(Trim(s), Trim(d2)), d1) = 1
        s = s - 1
      Loop
      If MBJC(MbC(Trim(s), Trim(d2)), d1) = 0 Then
        MCC1 = s
      Else
        MCC1 = s & "/" & MPC(Trim(d1), MbC(Trim(s), Trim(d2)))
      End If
    Else
      If Len(d2) < 9 Then
        MCC1 = MCC(d1, d2)
      Else
        Dim x, Y '变问号了咋
        x = Len(d1): Y = Len(d2)
        Dim JW, jcc, jss, jcs
        Dim a() As String, b() As String
        ReDim a(1 To x)
        ReDim b(1 To Y)
        For i = 1 To x
          a(i) = Mid(d1, i, 1)
        Next
        For j = 1 To Y
          b(j) = Mid(d2, j, 1)
        Next
        jcc = Val(a(1) & a(2)) \ Val(b(1) & b(2))
        jss = MbC(Trim(jcc), d2)
        For i1 = 1 To Y
          jws = jws & a(i1)
        Next
        Do While MBJC(Trim(jws), Trim(jss)) = -1
          jcc = jcc - 1
          jss = MbC(Trim(jcc), d2)
        Loop
        JW = MPC(Trim(jws), Trim(jss))
        z = x - Y
        Dim c() As String
        ReDim c(1 To z)
        For s = 1 To z
          If MBJC(JW & a(s + Y), d2) = -1 Then
            c(s) = "0"
          Else
            jwc = Val(Left(JW & a(s + Y), 3)) \ Val(Left(d2, 2))
            If Len(jwc) > 1 Then
              c(s) = "9"
            Else
              c(s) = jwc
            End If
            Do While MBJC(JW & a(s + Y), MbC(Val(c(s)), d2)) = -1
              c(s) = Right(10000 + Val(c(s) - 1), 1)
            Loop
          End If
          JW = MPC(JW & a(s + Y), MbC(Val(c(s)), d2))
          jcc = jcc & c(s)
        Next s
        If JW = 0 Then
          MCC1 = jcc
        Else
          MCC1 = jcc & "/" & JW
        End If
        For i = 1 To Len(MCC1)
          If Not Mid(MCC1, i, 1) = "0" Then Exit For
        Next
        strtmp = Mid(MCC1, i)
        If Len(strtmp) = 0 Then
          MCC1 = "0"
        Else
          MCC1 = strtmp
        End If
      End If
    End If
  End If
End If
End Function

Public Function MCC3(ByVal d1 As String, ByVal d2 As String) As String
  '格式转换，将我的大数除法结果转换为题主设定的“商/余数”格式
  Dim a As String, b As String
  a = MCC5(d1, d2)
  b = MPC(d1, MbC(d2, a))
  If Val(b) > 0 Then a = a & "/" & b
  MCC3 = a
End Function

Public Function MCC5(ByVal d1 As String, ByVal d2 As String) As String
  '大数除法，d1/d2，不处理负数，参数中非数字字符按0处理
  Dim i As Long, j As Long, k As Long, a As String, b As String, c As String
  Dim l1 As Integer, l2 As Integer, l As Integer
  i = mComp(d1, d2)
  If i < 1 Then
    MCC5 = i + 1
    Exit Function  '返回被除数小于或等于除数的商
  End If
  MCC5 = d1
  If Val(d2) < 2 Then Exit Function '如果除数为0或1则直接把被除数作为结果返回（除0不给出错误）
  a = ""
  If Len(d2) < 9 Then
    k = Val(d2)
    j = 0
    For i = 1 To Len(d1)
      If j > 100000000 Then
        a = a & Int(j / k)
        j = j Mod k
      Else
        If a <> "" And j < k Then a = a & "0"
      End If
      j = j * 10 + Val(Mid(d1, i, 1))
    Next
    a = a & Int(j / k)
  Else
    b = ""
    a = ""
    i = 1
    While i <= Len(d1)
      j = Len(b)
      b = b & Mid(d1, i, Len(d2) + 1 - j)  '多加一位是确保b>d2
      j = Len(b) - j
      i = i + j
      l = 0
      l1 = 0
      l2 = 100
      If mComp(b, d2) >= 0 Then
        While l2 > l1 + 1
          l = Int(l2 + l1) / 2
          c = MbC(d2, l)
          If mComp(b, c) < 0 Then
            l2 = l
          Else
            l1 = l
          End If
        Wend
        b = MPC(b, MbC(d2, l1))
        If Val(Left(b, 2)) = 0 Then b = "" '获取余数
      End If
      c = Trim(l1)
      If l1 = 0 Then c = ""
      If a <> "" Then
        For k = 1 To j - Len(c)
          a = a & "0"
        Next
      End If
      a = a & c
    Wend
  End If
  MCC5 = a
End Function
Public Function MbC(ByVal d1 As String, ByVal d2 As String) As String
  '大数乘法，d1*d2，不处理负数，参数中非数字字符按0处理
  Dim i As Integer, j As Long, k As Integer, a As String, b As String, Y As String
  Y = ""
  a = "0"
  For i = Len(d1) To 1 Step -1
    j = 0
    b = ""
    For k = Len(d2) To 1 Step -1
      j = Val(Mid(d1, i, 1)) * Val(Mid(d2, k, 1)) + j
      b = (j Mod 10) & b
      j = Int(j / 10)
    Next
    If j > 0 Then b = j & b
    a = MPC1(a, b & Y)
    Y = Y & "0"
  Next
  MbC = a
End Function

Public Function MPC(ByVal d1 As String, ByVal d2 As String) As String
  '大数减法d1-d2，如果d2>d1则交换，非法字符当字符0处理，不识别负数
  Dim a As String, b As String, c As String, i As Integer
  If mComp(d1, d2) < 0 Then                     '确保被减数大于减数
    MPC = MPC(d2, d1)                           '这里可根据需要输出负数
    Exit Function
  End If
  c = "9876543210"
  a = ""
  b = ""
  For i = 1 To Len(d2)
    b = b & Mid(c, Val(Mid(d2, i, 1)) + 1, 1)   '对减数按位取反
  Next
  For i = Len(d2) + 1 To Len(d1)
    b = "9" + b
  Next
  b = MPC1(b, "1")                              '调整该减数为对应十进制补数
  b = MPC1(d1, b)
  a = Right(b, Len(d1))
  For i = 1 To Len(a)
    If Mid(a, i, 1) <> "0" Then Exit For
  Next
  a = Right(a, Len(a) + 1 - i)                  '消前导0
  If a = "" Then a = "0"
  MPC = a
End Function

Public Function MPC1(ByVal d1 As String, ByVal d2 As String) As String
  '大数加法d1+d2,函数不识别参数的合法性,参数中有非法字符当作0处理,不识别负数
  Dim l1 As Integer, l2 As Integer, j As Integer, a As Integer, b As Integer
  l1 = Len(d1)
  l2 = Len(d2)
  j = 0
  While l1 + l2 + j > 0
    a = 0
    b = 0
    If l1 > 0 Then
      a = Val(Mid(d1, l1, 1))
      l1 = l1 - 1
    End If
    If l2 > 0 Then
      b = Val(Mid(d2, l2, 1))
      l2 = l2 - 1
    End If
    j = a + b + j
    MPC1 = (j Mod 10) & MPC1
    j = Int(j / 10)
  Wend
End Function


 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

 

 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 Sub Command1_Click()
Dim a, n
Dim t As Double
t = Timer
n = Trim(Text1)
If Len(n) < 6 Then
Text2 = fenjieyinzi(Trim(n))
Else
n1 = MPC(Trim(n), 1)
a = 123
'a为明文
a1 = zzxc(Trim(n), Trim(a))
If Val(a1) > 1 Then
Text2 = 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
Text2 = "这是素数有" & Len(n) & "位,用时" & Timer - t & "秒"
Else
Text2 = "2*2" & "用时" & Timer - t & "秒"
End If
End If
End If
End Sub

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

Private Sub Form_Load()
  Command2_Click
End Sub


[此贴子已经被作者于2020-2-22 09:02编辑过]
#89
ysr28572020-02-22 00:19
回复 88楼 wmf2014
谢谢你！原理是成立的，我已经推导证明过了，你说的道理是对的。命题是可以逆推的，结论和前提是充要条件。所以是确定性的，比AKS法方便容易实现，比拉宾-米勒法靠谱，拉宾-米勒法在小数据中由于人们已经找到了漏掉的合数，所以可以排除确定，更大范围就不是确定的。这个法是确定的，限于速度，我也不知道能算到多少位的。
程序速度提高了就是有价值的，谢谢你，非常感谢！明天我试试！
前面提到的那个大整数的除法的算法我已经搞出程序，不快，前面的迭代增长太快，是2的幂数增长的，最后一步弄不准了，只好一个一个加上，所以最后这一步就特别慢，偶尔会有一个刚好不用加的就快，不好用。不是好法，不是普遍的所有整数的速度都能提高的。不发了。仅供参考。
#90
ysr28572020-02-22 08:03
回复 88楼 wmf2014
这个文件打不开，我的电脑没有打开此文件的程序需要下载其他程序，也不知道啥样的程序。
谢谢您！
下面发个除法程序，只发主程序，也是个可调用程序。太慢，不断调用乘法比较大小，加法减法，若把乘法等程序速度提高了，程序是不是能用也不知道，发一下仅供参考。
 Public Function MCC1(D1 As String, D2 As String) As String ';大整数的除法
Dim ss
 ss = MBJC(D1, D2)
If ss = -1 Then
 MCC1 = "0" & "/" & D1
  Else
  If ss = 0 Then
   MCC1 = 1
   Else
   If Len(D2) < 9 Then
   MCC1 = MCC(Trim(D1), Trim(D2))
   Else
   x = Len(D1) - Len(D2)
   d4 = D1
  If x <= 3 Then
  x = 3
  B = 0
  Else
  a = Log(2) / Log(10)
  X1 = x
 B = Int(X1 * Val(a))
Do While B >= x
X1 = X1 + 1
B = Int(X1 * Val(a))
Loop
B = X1 - 1
End If
  c = 1
   Do Until i = B
    i = i + 1
    c = MbC(Trim(c), 2)
   Loop
   i1 = B
  Do While MBJC(Trim(D1), MbC(Trim(D2), Trim(c))) = 1
 i1 = i1 + 1
c = MbC(Trim(c), 2)
Loop
c = 1
Do Until i2 = i1 - 1
c = MbC(Trim(c), 2)
i2 = i2 + 1
Loop
D1 = MPC(Trim(D1), MbC(Trim(D2), Trim(c)))
D3 = c
C1 = c

D1 = MPC(Trim(d4), MbC(Trim(D3), Trim(D2)))
d5 = D1
If x >= 15 Then
x = x + 2
Else
x = x
End If
Do Until i2 <= x
c = 1
i1 = 0
  Do While MBJC(Trim(D1), MbC(Trim(D2), Trim(c))) = 1
 i1 = i1 + 1
c = MbC(Trim(c), 2)
Loop

i2 = 0
c = 1
Do Until i2 = i1 - 1
c = MbC(Trim(c), 2)
i2 = i2 + 1
Loop
D1 = MPC(Trim(D1), MbC(Trim(D2), Trim(c)))
D3 = MPC1(Trim(D3), Trim(c))
C1 = c
Print i2, D3
Loop
Do While MBJC(Trim(d4), MbC(Trim(D3), Trim(D2))) > 0
D3 = MPC1(Trim(D3), 1)
Loop
If MBJC(Trim(d4), MbC(Trim(D3), Trim(D2))) < 0 Then
D3 = MPC(Trim(D3), 1)
Else
D3 = D3
End If
JW = MPC(Trim(d4), MbC(Trim(D3), Trim(D2)))

If MBJC(Trim(JW), 0) = 0 Then
MCC1 = D3
Else

MCC1 = D3 & "/" & JW
End If
 End If
End If
End If
End Function
#91
ysr28572020-02-22 09:20
回复 88楼 wmf2014
这回好！复制下来了，谢谢您！学习学习，非常感谢！
#92
ysr28572020-02-22 09:38
试验了一下程序，用时16秒，快了不少，继续研究学习，谢谢老师！！
#93
wmf20142020-02-22 09:52
大数减法再优化了下，减少不必要的变量，十进制补数用计算的方式获取，优化后代码如下：
程序代码：
Public Function MPC(ByVal d1 As String, ByVal d2 As String) As String
  '大数减法d1-d2，如果d2>d1则交换，非法字符当字符0处理，不识别负数
  Dim a As String, i As Integer
  If mComp(d1, d2) < 0 Then                      '确保被减数大于减数
    MPC = MPC(d2, d1)                            '这里可根据需要添加负号输出负数
    Exit Function                                '其实负数还是要处理的，我经常取逆元取到负数，这时就需要加一次n-1
  End If
  a = ""
  For i = 1 To Len(d2)
    a = a & (9 - Val(Mid(d2, i, 1)))             '对减数按位取反
  Next
  For i = Len(d2) + 1 To Len(d1)
    a = "9" + a
  Next
  a = MPC1(d1, MPC1(a, "1"))                     '调整该减数为对应十进制补数并和被加数相加
  If Len(a) > Len(d1) Then a = Right(a, Len(d1)) '去掉进位
  For i = 1 To Len(a)
    If Mid(a, i, 1) <> "0" Then Exit For
  Next
  a = Right(a, Len(a) + 1 - i)                   '消前导0
  If a = "" Then a = "0"
  MPC = a
End Function
#94
ysr28572020-02-22 10:54
回复 93楼 wmf2014
非常好，谢谢！我试验一下！学习了，向你学习！
#95
xianfajushi2020-02-23 06:39
含控制台输出1亿内用时2070秒转换约等34.5分钟
只有本站会员才能查看附件，请 登录


[此贴子已经被作者于2020-2-23 06:48编辑过]
#96
xianfajushi2020-02-23 06:39
不含控制台输出用时1002转换约等16.7分钟。C++普通函数调用运算。
只有本站会员才能查看附件，请 登录

普通的判断，不含使用质数表。
只有本站会员才能查看附件，请 登录


[此贴子已经被作者于2020-2-23 08:27编辑过]
#97
ysr28572020-02-23 09:17
您的程序比我的快，我的程序不是仅算素数的是1亿的拆分素数对，两个素数的和等于1亿，程序计算了大槪3小时以上（没有计算时间的程序，现在刚学会计算时间的程序），结果如下：（太长，仅发一部分）
100000000的方根为10000,方根内有119个总数有291400个:100000000=11+ 99999989
29+ 99999971
41+ 99999959
59+ 99999941
173+ 99999827
179+ 99999821
227+ 99999773
383+ 99999617
389+ 99999611
449+ 99999551
461+ 99999539
491+ 99999509
563+ 99999437
599+ 99999401
647+ 99999353
677+ 99999323
743+ 99999257
887+ 99999113
911+ 99999089
1091+ 99998909
1109+ 99998891
1181+ 99998819
1217+ 99998783
1487+ 99998513
1553+ 99998447
1559+ 99998441
1571+ 99998429
1583+ 99998417
1637+ 99998363
1709+ 99998291
1889+ 99998111
1901+ 99998099
1949+ 99998051
1979+ 99998021
2027+ 99997973
2087+ 99997913
2099+ 99997901
#98
xianfajushi2020-02-23 09:27
那算前面小质数即可，后面大质数用减法即可得，不是更快了？
#99
ysr28572020-02-23 10:09
回复 98楼 xianfajushi
就是这样算的，并不是减出来结果都是素数，还要判断，所以程序运行慢！谢谢关注！我不需要这么大的数据，我需要的是快速程序！一亿内的素数，数值不大数量多，经过比较前面的程序速度没有变化几乎一样，判定一个23位的素数单个素数，二者差1秒，明显的差距，再小的就没有差距了，用前面的程序算1亿内的数据差别很小，没有进步，不明显。
我算10090000000～10090001000之间有5对孪生素数，用我的程序运行时间179秒，用网友前面的改进程序运行时间是167秒，进步不明显，所以我还是要弄出快速乘法除法程序，有毫秒级的程序吗？算一步大整数的乘法除法在毫秒内的？
希望老师帮忙！其中一个用途就是前面的大整数的素性测试。
#100
xianfajushi2020-02-23 10:53
前面例举出孪生质数对，10090000000～10090001000之间有5对孪生素数是虾米？
孪生素数就是指相差2的素数对，例如3和5，5和7，11和13？如果是那只能找到2对27-29，17-19，有那5对？
只有本站会员才能查看附件，请 登录


[此贴子已经被作者于2020-2-23 11:54编辑过]
#101
ysr28572020-02-23 11:31
回复 100楼 xianfajushi
谢谢关注和指导！对，孪生素数对就是差为2的素数对：
10090000000与10090001000之间有5对孪生素数对:
10090000241和 10090000243  孪中10090000242
10090000469和 10090000471  孪中10090000470
10090000517和 10090000519  孪中10090000518
10090000637和 10090000639  孪中10090000638
10090000727和 10090000729  孪中10090000728
用时167秒。
123456789
©2025, BC-CN.NET
电脑版