| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 28355 人关注过本帖
标题:各位老师好!求助编辑一个大整数的快速乘除法可调用程序
只看楼主 加入收藏
ysr2857
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:34
帖 子:792
专家分:70
注 册:2020-2-10
收藏
得分:0 
Private Sub Command1_Click()
Dim a, n
n = Trim(Text1)
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 Sub

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

End Sub

2020-02-15 16:41
ysr2857
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:34
帖 子:792
专家分:70
注 册:2020-2-10
收藏
得分:0 
其中zzxc()为辗转相除判断是否互质,qniyuan()为求乘法的逆元的,qksmimo()为快速幂模算法求余数(或叫明文,密文),这3个程序您都会的吧对你不难,需要的话我可以传上来。也是只传主程序。否则代码太长,超长了,不好传完整的。

[此贴子已经被作者于2020-2-15 16:54编辑过]

2020-02-15 16:49
ysr2857
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:34
帖 子:792
专家分:70
注 册:2020-2-10
收藏
得分:0 
有问题随时可以给您解释!谢谢您帮助,非常感谢!
2020-02-15 16:51
ysr2857
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:34
帖 子:792
专家分:70
注 册:2020-2-10
收藏
得分:0 
再发一遍,实际做成可调用程序是这个样子:(稍改一下,使用于大于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编辑过]

2020-02-15 17:03
ysr2857
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:34
帖 子:792
专家分:70
注 册:2020-2-10
收藏
得分:0 
其中的MBJC()为比较大小的程序,因为有时候会遇到大数,其中可能遇到大数运算的地方您可以自己调整为大数的可调用程序。
2020-02-15 17:11
ysr2857
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:34
帖 子:792
专家分:70
注 册:2020-2-10
收藏
得分:0 
再发一下那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


2020-02-15 17:22
ysr2857
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:34
帖 子:792
专家分:70
注 册:2020-2-10
收藏
得分:0 
为了调用方便,合数时输出为2*2,关键是有*号以区别是否是素数。
2020-02-15 17:29
wmf2014
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:216
帖 子:2039
专家分:11273
注 册:2014-12-6
收藏
得分:0 
如果可以的话,你还是提供全面的工程文件吧。
仔细看了你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编辑过]


能编个毛线衣吗?
2020-02-15 23:55
ysr2857
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:34
帖 子:792
专家分:70
注 册:2020-2-10
收藏
得分:0 
回复 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整除。) 欢迎试用,欢迎找反例,理论上成立,可靠的,起码我是这么推导证明了一下谢谢!我不是专家再多了讲不了,但我们可以探讨,欢迎试用欢迎沟通,希望您能理解,能帮助我搞出个快速的程序。

可以发完整的程序,太长,明天试试吧!谢谢您!
2020-02-16 02:12
ysr2857
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:34
帖 子:792
专家分:70
注 册:2020-2-10
收藏
得分:0 
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,这一步也不费劲,这样就完整了,万无一失了)
先这样用,需要的话再改成这一条。
2020-02-16 02:54
快速回复:各位老师好!求助编辑一个大整数的快速乘除法可调用程序
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.021107 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved