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

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

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

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

401 回复
#2
xianfajushi2020-02-10 23:25
你的程序是怎样的？大数乘除都可以百度到的，可作为参考。

[此贴子已经被作者于2020-2-10 23:29编辑过]
#3
ysr28572020-02-11 00:24
谢谢老师！都是VC的没有VB的，看不懂！我的程序效率低，调试了多次结果是正确的，就是速度慢，而且最多也不知道算多少位，太长的就溢出吧，关键是速度慢！
#4
ysr28572020-02-11 00:27
233333333333333333333333333333333333333333333333333333这是素数有54位

这个是用我的程序判断的，程序用了1分钟还是几分钟？估计的，没有计算时间的程序。
#5
wmf20142020-02-11 09:42
10亿内素数用long型数据即可，不需要大数乘除法，用欧拉筛法应该10秒内可建立一个10亿内的素数表。
#6
ysr28572020-02-11 10:09
不行，超过9位就溢出，不仅是素数表还计算下面的数据，这个数程序运行了至少半个小时：
1000620000与1000720000之间有287对孪生素数对:
1000620317和 1000620319  孪中1000620318
1000620347和 1000620349  孪中1000620348
1000621709和 1000621711  孪中1000621710
1000621799和 1000621801  孪中1000621800
1000622009和 1000622011  孪中1000622010
1000622087和 1000622089  孪中1000622088
1000622891和 1000622893  孪中1000622892
1000622921和 1000622923  孪中1000622922
1000622969和 1000622971  孪中1000622970
1000623341和 1000623343  孪中1000623342
1000623989和 1000623991  孪中1000623990
1000624307和 1000624309  孪中1000624308
1000624619和 1000624621  孪中1000624620
1000624991和 1000624993  孪中1000624992
1000625231和 1000625233  孪中1000625232
1000625411和 1000625413  孪中1000625412
1000625651和 1000625653  孪中1000625652
1000625699和 1000625701  孪中1000625700
1000626047和 1000626049  孪中1000626048
#7
ysr28572020-02-11 10:15
long型的数据？可能是行，咱不会，仅会有限个vb语句，不精通。但是判断几十位几百位的整数是否是素数，必须用大整数的快速乘法除法程序，欢迎指导！
谢谢楼上的老师！
#8
wmf20142020-02-11 10:31
long型数据可以做20亿内的整数计算，如果是几十上百位当然要使用大数乘除，而对大数的素数判断不能使用常规的算术运算，一般使用Miller-Rabin素性测试方法，有点复杂，其中要用到快速模运算和快速积运算。仅仅实现大数加减乘除很简单，但做素性测试还不够的。
#9
ysr28572020-02-11 11:25
对，我的程序就是个太慢效率低。我的大数程序好像超过2万位就内存不足溢出了，不能算更大的，上万位的整数算一步乘法的时间也是长，太慢。
#10
ysr28572020-02-11 11:34
判断大素数我采用的是RSA密码的逆命题，用到快速幂模算法，是确定性的算法，小于5位的就失效了，因为明文采用3位的，用一位的数字怕不准，明文是余数才能还原的，除数低于3位余数就不会是3位的，还原不回去原理就失效。大于5位的是成立的，由于我的大整数的乘除法速度太慢，所以几十位的运算结果消耗时间还是能忍受的，再大的就无法忍受了。原理上是可以的。
谢谢老师！欢迎指导！

[此贴子已经被作者于2020-2-11 11:47编辑过]
#11
ysr28572020-02-11 11:37
若n=pq，且p丶q均为素数，则φ（n）=(p-1)(q-1)，由于6958000001674999998647为两个11位的素数的积，则可以当公开模数，做密码，这个位数少容易分解，不安全，只是演示RSA密码的原理。
则φ（n）=(p-1)(q-1)=6958000001505999998640，选公钥，
公钥的选择在1~φ（n）之间，公钥必须与φ（n）互质
根据互质数的性质:
(1):小数与大质数互质，
(2):小质数与不含有它的倍数的大合数互质，
由于122333221和6958000001505999998640 最大公约数为：1，所以122333221可以做公钥，而122333221模6958000001505999998640 的逆元为：4415860875509221693741，这个逆元就是私钥，私钥比公钥长，演示加密：明文123456789^122333221 MOD 6958000001674999998647=2920527367305698772708， 解密是这样：密文2920527367305698772708^4415860875509221693741 MOD 6958000001674999998647=123456789，还原回去了，这就是过程。
6958000001674999998647=71000000041*97999999967为两个11位的素数的积，则可以当公开模数，做密码，这个位数少容易分解，不安全，只是演示RSA密码的原理

我的程序缺点就是慢，太慢，效率低，而且还是仅能算2万位以内的，否则内存不足溢出！请求各位老师指导！

[此贴子已经被作者于2020-2-11 11:40编辑过]
#12
wmf20142020-02-11 11:53
看来题主在做rsa加解密相关内容，这个我做过，我是用c做的。不需要做两万位啊，通常做到2^1024位足矣，用“dim a(64) as long”足以表达，如果vb支持无符号型数据定义，用32个就行了，大数运算先做一个大数加法函数和一个大数乘法函数，除法和减法调这两个函数即可，由于不支持无符号数定义，所以可将低16位作为运算结果，高16位作为进位。
#13
ysr28572020-02-11 11:57
判断素数的原理：根据RSA密码的原理，当n为素数的时候成立，φ（n）=n-1，这样可以还原出明文，若n为合数就还原不回去，则判断出n为合数。
#14
ysr28572020-02-11 12:05
回复 12楼 wmf2014
谢谢！您说的可能是一种方法，速度快吗？我不懂vc,不精通vb,大整数的加法减法乘法除法我也有了程序，关键是速度太慢。vc程序我看不懂，希望用vb编程的。或者指导一下原理，如何变成long型的？
#15
ysr28572020-02-11 13:12
由于123=3*41，如果用前面的方法判断的话要先试验n是否能被3或41整除，否则可能输出判断结果错误。
#16
ysr28572020-02-11 16:03
调整了一下，快了一点，没那么快，1001000000～1002000000之间的孪生素数对，将近一个小时了也还没有出来结果呢。

希望老师指导！咋回事呢？

[此贴子已经被作者于2020-2-11 16:06编辑过]
#17
ysr28572020-02-11 16:30
算出来结果了，约1个多小时呢。
1001000000与1002000000之间有3056对孪生素数对:
1001000111和 1001000113  孪中1001000112
1001000381和 1001000383  孪中1001000382
1001001059和 1001001061  孪中1001001060
1001001227和 1001001229  孪中1001001228
1001001557和 1001001559  孪中1001001558
1001002151和 1001002153  孪中1001002152
1001002229和 1001002231  孪中1001002230
1001002487和 1001002489  孪中1001002488
1001002589和 1001002591  孪中1001002590
1001003681和 1001003683  孪中1001003682
1001004239和 1001004241  孪中1001004240
1001004287和 1001004289  孪中1001004288
1001004371和 1001004373  孪中1001004372
1001005217和 1001005219  孪中1001005218
1001005349和 1001005351  孪中1001005350
1001005427和 1001005429  孪中1001005428
1001006231和 1001006233  孪中1001006232
1001006261和 1001006263  孪中1001006262
1001007347和 1001007349  孪中1001007348
1001007779和 1001007781  孪中1001007780
1001008037和 1001008039  孪中1001008038
1001008661和 1001008663  孪中1001008662
1001009591和 1001009593  孪中1001009592
1001009741和 1001009743  孪中1001009742
1001010011和 1001010013  孪中1001010012
后面还有好多，超长了不发了。
#18
ysr28572020-02-11 18:14
不会long型的程序，修改以后我的判断法不能运行了，咋回事呢？
#19
ysr28572020-02-12 08:39
希望老师给个快速的程序！一天也算不出多少，下面是晚上程序晚上算出来的，祝大家新年新年快乐万事如意：
1011000000与1021000000之间有30808对孪生素数对:
1011000371和 1011000373  孪中1011000372
1011000377和 1011000379  孪中1011000378
1011000479和 1011000481  孪中1011000480
1011001427和 1011001429  孪中1011001428
1011001811和 1011001813  孪中1011001812
1011001877和 1011001879  孪中1011001878
1011001967和 1011001969  孪中1011001968
1011003179和 1011003181  孪中1011003180
1011003269和 1011003271  孪中1011003270
1011003359和 1011003361  孪中1011003360
1011003491和 1011003493  孪中1011003492
1011004037和 1011004039  孪中1011004038
1011004067和 1011004069  孪中1011004068
1011004661和 1011004663  孪中1011004662
1011005909和 1011005911  孪中1011005910
1011006011和 1011006013  孪中1011006012
1011006041和 1011006043  孪中1011006042
1011006341和 1011006343  孪中1011006342
1011007007和 1011007009  孪中1011007008
1011007091和 1011007093  孪中1011007092
1011007241和 1011007243  孪中1011007242
1011007451和 1011007453  孪中1011007452
1011007469和 1011007471  孪中1011007470
1011008057和 1011008059  孪中1011008058
1011008291和 1011008293  孪中1011008292
1011008567和 1011008569  孪中1011008568
1011008597和 1011008599  孪中1011008598
1011008891和 1011008893  孪中1011008892
1011009287和 1011009289  孪中1011009288
1011009299和 1011009301  孪中1011009300
1011009341和 1011009343  孪中1011009342
1011009887和 1011009889  孪中1011009888
1011009947和 1011009949  孪中1011009948
1011010289和 1011010291  孪中1011010290
1011010751和 1011010753  孪中1011010752
1011011459和 1011011461  孪中1011011460
1011013019和 1011013021  孪中1011013020
1011013151和 1011013153  孪中1011013152
1011013187和 1011013189  孪中1011013188
1011013649和 1011013651  孪中1011013650
1011013697和 1011013699  孪中1011013698
1011013811和 1011013813  孪中1011013812
1011015539和 1011015541  孪中1011015540
1011015557和 1011015559  孪中1011015558
1011015911和 1011015913  孪中1011015912
1011016001和 1011016003  孪中1011016002
1011016751和 1011016753  孪中1011016752
1011017087和 1011017089  孪中1011017088
1011017219和 1011017221  孪中1011017220
1011017867和 1011017869  孪中1011017868
1011017879和 1011017881  孪中1011017880
1011018131和 1011018133  孪中1011018132
1011018719和 1011018721  孪中1011018720
1011019421和 1011019423  孪中1011019422
1011019871和 1011019873  孪中1011019872
1011019967和 1011019969  孪中1011019968
1011020027和 1011020029  孪中1011020028
1011020471和 1011020473  孪中1011020472
1011020501和 1011020503  孪中1011020502
1011020537和 1011020539  孪中1011020538
1011021377和 1011021379  孪中1011021378
1011021617和 1011021619  孪中1011021618
1011021701和 1011021703  孪中1011021702
1011022919和 1011022921  孪中1011022920
1011023477和 1011023479  孪中1011023478
1011023567和 1011023569  孪中1011023568
1011023639和 1011023641  孪中1011023640
1011023729和 1011023731  孪中1011023730
1011024851和 1011024853  孪中1011024852
1011025619和 1011025621  孪中1011025620
1011026759和 1011026761  孪中1011026760
1011026789和 1011026791  孪中1011026790
1011026921和 1011026923  孪中1011026922
1011026957和 1011026959  孪中1011026958
1011027497和 1011027499  孪中1011027498
1011028349和 1011028351  孪中1011028350
1011028631和 1011028633  孪中1011028632
1011028721和 1011028723  孪中1011028722
1011028829和 1011028831  孪中1011028830
1011028937和 1011028939  孪中1011028938
1011029687和 1011029689  孪中1011029688
1011029909和 1011029911  孪中1011029910
1011030899和 1011030901  孪中1011030900
1011032327和 1011032329  孪中1011032328
1011033167和 1011033169  孪中1011033168
1011033431和 1011033433  孪中1011033432
1011033449和 1011033451  孪中1011033450
1011033731和 1011033733  孪中1011033732
1011033761和 1011033763  孪中1011033762
1011034259和 1011034261  孪中1011034260
1011034991和 1011034993  孪中1011034992
1011035489和 1011035491  孪中1011035490
后面还多内容超长不发了，程序慢，需要改进。
#20
wmf20142020-02-12 09:20
是不是就是找0-2000000000的孪生素数？如果是的话我试试用vb打表看看，我记得用c打表我电脑大概花了30秒钟。
其实打表也还是有难度的，即使按位打表也得250M存储空间，就是只打奇数表也得125M空间，但vb对内存的操作远没有c的指针方便。
我现在都没有vb了，估计只能在excel的vba中测试。

[此贴子已经被作者于2020-2-12 09:31编辑过]
#21
ysr28572020-02-12 10:13
回复 20楼 wmf2014
只要个总个数，不用打表，10^10内的。我都算了好几天了，10^9～10^10之间的都没有算出来，是朋友要这个数据的。谢谢您！祝您身体健康万事如意！
#22
ysr28572020-02-12 10:54
Copyright © 1999-2020, , All Rights Reserved



搜索博文/帖子/用户
 登录
VB实现FFT算法 转载

weixin_34245749

225次阅读 2013-04-17

关注
程序列如下:

Public Function fft(ByRef Data() As Double) As Double()
    ReDim ffft(128, 2) As Double
    Dim length As Integer
    length = UBound(Data, 1) + 1
'    Dim numArray(length - 1, 2) As Double
      
    Dim index As Integer
    Dim num5 As Integer
    Dim num6 As Integer
    Dim num7 As Integer
    Dim num10 As Integer
    Dim num3 As Integer
    Dim num2 As Integer
    Dim num11 As Integer
    Dim num9 As Integer
    num9 = length
      
    Dim num8 As Integer
    num8 = CInt(Math.Log(CDbl(num9)) / Math.Log(2#))
      
    Dim numArray2(128) As Double
    Dim numArray3(128) As Double
    Dim numArray4(128) As Double
    Dim numArray5(128) As Double
    For index = 0 To num9 - 1
        numArray2(index) = Data(index)
        numArray3(index) = 0#
    Next
    Dim a As Double
    Dim num14 As Double
      
   num14 = 6.28318530717959 / CDbl(num9)
    index = 0
    While index < (num9 \ 2)
        numArray4(index) = Math.Sin(a)
        numArray5(index) = Math.Cos(a)
        a = a + num14
        index = index + 1
    Wend
    num7 = num9
    num3 = 1
    For num2 = 1 To num8
        num7 = num7 / 2
        num6 = 0
        For num11 = 1 To num3
            num10 = 0
            index = num6
            While index <= ((num7 + num6) - 1)
                num5 = index + num7
                a = numArray2(index) - numArray2(num5)
                num14 = numArray3(index) - numArray3(num5)
                numArray2(index) = numArray2(index) + numArray2(num5)
                numArray3(index) = numArray3(index) + numArray3(num5)
                If num10 = 0 Then
                    numArray2(num5) = a
                    numArray3(num5) = num14
                Else
                    numArray2(num5) = (a * numArray5(num10)) + (num14 * numArray4(num10))
                    numArray3(num5) = (num14 * numArray5(num10)) - (a * numArray4(num10))
                End If
                num10 = num10 + num3
                index = index + 1
           Wend
            num6 = (num6 + num7) + num7
        Next
        num3 = num3 + num3
    Next
    num5 = num9 \ 2
    For index = 1 To (num9 - 1)
        num6 = num9
        If num5 < index Then
            Dim num12 As Double
              
          num12 = numArray2(index)
            numArray2(index) = numArray2(num5)
            numArray2(num5) = num12
            num12 = numArray3(index)
            numArray3(index) = numArray3(num5)
            numArray3(num5) = num12
        End If
        num6 = num6 / 2
        Do While num5 >= num6
            num5 = num5 - num6
            num6 = num6 / 2
            If num5 = 0 Then
                Exit Do
            End If
        Loop
        num5 = num5 + num6
    Next
    For index = 0 To num9 - 1
        numArray(index, 0) = numArray2(index)
        numArray(index, 1) = numArray3(index)
        numArray(index, 2) = ((numArray2(index)) ^ 2# + (numArray3(index)) ^ 2#) ^ 0.5
    Next
   fft = numArray
End Function

前面的程序的说明（原稿中复制过来的）：
默认了数组为128
如果你需要动态，请
redim各数组

输入：一串数据
输出：FFT变换后的数据，1维是实部 ，2维是虚部

这是vb版快速傅立叶变换fft，不懂，也不知道输出啥结果，不知道是否可以用于大整数的快速乘法。

没有找到vb版的大整数快速乘法程序。

有vc版的，不懂。
#23
ysr28572020-02-12 11:33
是不是输出素数占用了时间，不输出素数仅输出总个数就会快了？
#24
ysr28572020-02-12 13:38
前面的这个程序如何调用？想试试能出啥结果，不知道如何用？
#25
ysr28572020-02-12 16:47
找到一个vb程序，不知道是不是快速乘法程序，原文前面的是高精度vc版乘法程序，不懂，后面是这个程序，不知道是不是乘法程序。
Dim i, j, L(2), a(1000) As Integer, b(1000) As Integer, c(2000, 2000) As Integer, d(2000, 2000) As Integer, x(10000) As Integer, jieguo As String, y(10000) As Integer

Private Sub Command1_Click()

L(1) = Len(Text2.Text)

L(2) = Len(Text3.Text)

For i = 1 To L(1)

a(i) = Val(Mid(Text2.Text, L(1) - i + 1, 1))

Next i

For i = 1 To L(2)

b(i) = Val(Mid(Text3.Text, L(2) - i + 1, 1))

Next i

For i = 1 To L(2)

For j = 1 To L(1)

c(i, j) = b(i) * a(j) + c(i, j)

d(i, j) = Int(c(i, j) / 10)

If d(i, j) > 0 Then

c(i, j) = c(i, j) - 10 * d(i, j)

c(i, j + 1) = c(i, j + 1) + d(i, j)

End If

d(i, j) = 0

Next j

Next i

For i = 1 To L(2)

b(i) = 0

Next i

For i = 1 To L(1)

a(i) = 0

Next i

For i = 1 To L(2)

For j = 1 To L(1) + 1

x(i + j - 1) = x(i + j - 1) + c(i, j)

c(i, j) = 0

Next j

Next i

For i = 1 To L(1) + L(2) + 1

y(i) = Int(x(i) / 10)

If y(i) > 0 Then

x(i) = x(i) - 10 * y(i)

x(i + 1) = x(i + 1) + y(i)

End If

y(i) = 0

Next i

Text1.Text = ""

If x(L(1) + L(2) + 1) <> 0 Then Text1.Text = Text1.Text & x(L(1) + L(2) + 1)

If x(L(1) + L(2)) <> 0 Then Text1.Text = Text1.Text & x(L(1) + L(2))

For i = L(1) + L(2) - 1 To 1 Step -1

Text1.Text = Text1.Text & x(i)

Next i

For i = 1 To L(1) + L(2) + 1

x(i) = 0

Next i

L(1) = 0

L(2) = 0

jieguo = Text1.Text

End Sub

Private Sub Form_Load()

Text2.Text = "a"

Text3.Text = "b"

Text1.Text = "结果"

Command1.Caption = "计算"

Timer1.Interval = 1

"interval，是间隔，值只能为数字而不能是true

jieguo = "结果"

End Sub

Private Sub Timer1_Timer()

Text1.Text = jieguo

End Sub

经过我验证了一下，这个乘法的速度不快，还没有我的模仿手工计算的乘法速度快，且大整数超过不知道多少位就会下标越界。太大话不能用了。

[此贴子已经被作者于2020-2-12 17:57编辑过]
#26
ysr28572020-02-12 16:50
这个也是写着是分治法乘法，不知道是不是，不知道怎么用？咋弄？
Function Mult_() '分治法   多位数相乘  C*A=C,A 2013-06.14
Dim myVar, myNum, Var, r As Variant
Dim Aa, Ba, Ca, xP2 As Single
Dim Dx As Chen
Dim ax_sz(512), bx_sz(512), cx_sz(512) As Variant
        
Ax.St = Ax.St + Zero
Cx.St = Cx.St + Zero

If Left(Ax.St, 1) > "0" And Left(Cx.St, 1) > "0" Then
    For i = 0 To xP
        ax_sz(i) = CDec(Mid(Ax.St, i * Gsw + 1, Gsw))
        bx_sz(i) = CDec(Mid(Cx.St, i * Gsw + 1, Gsw))
    Next i

    myVar = ax_sz(0) * bx_sz(0)
    cx_sz(1) = myVar
    For i = 1 To xP
       myNum = ax_sz(i) * bx_sz(i)
       myVar = myVar + myNum
       For j = 0 To (i - 1) / 2
        cx_sz(i + 1) = cx_sz(i + 1) + (ax_sz(i - j) - ax_sz(j)) * (bx_sz(j) - bx_sz(i - j))
       Next
       cx_sz(i + 1) = cx_sz(i + 1) + myVar
    Next
   
   r = CDec(0)
For i = xP To 0 Step -1
    cx_sz(i) = cx_sz(i) + r
    r = Fix(cx_sz(i) / Zero6)
    cx_sz(i) = cx_sz(i) - r * Zero6
Next i

oResult = CStr(cx_sz(0))
For i = 1 To xP
    oResult = oResult + Right(Zero06 + CStr(cx_sz(i)), Gsw)
Next i

Dx.Bz = IIf(Ax.Bz = Cx.Bz, "", "-")
Dx.St = oResult

'指数计算
Aa = Val(Left(Ax.St, 1))
Ba = Val(Left(Cx.St, 1))
Ca = Val(Left(Dx.St, 1))

If Ax.Zs + Cx.Zs < 10 ^ 15 Then
    Dx.Zs = Ax.Zs + Cx.Zs + IIf(Aa * Ba <= Ca, 0, 1)
Else
    Dx.Zs = 0
End If

Cx = Dx
Ax = Dx

Else
   Ax.Bz = ""
   Ax.St = "0"
   Ax.Zs = 0
   Cx = Ax
End If
End Function
#27
wmf20142020-02-12 19:13
用excel vba打16（1.6×10^10)亿内素数表，共用时5分钟，有点慢，用c只需要13秒，vba代码如下：
程序代码：
Dim pri(200000000) As Byte

Sub 按钮1_Click()
  pritab
End Sub

Sub pritab()
  '用字节位筛法生成16亿以内的素数表
  Dim i As Long, j As Long, b(8) As Byte, c As Byte, k As Long, l As Long, t As Double
  j = 1
  t = Timer
  For i = 0 To 7
    b(i) = j
    j = j * 2       '位运算值初始化
  Next
  For i = 0 To 200000000
    pri(i) = 170    '先假设所有奇数都是素数
  Next
  pri(0) = 172      '0,1不是素数，2是素数
  i = 3
  While i * i <= 1600000000
    If (pri(Int(i / 8)) And b(i Mod 8)) > 0 Then
      j = i * i
      While j <= 1600000000
        If (pri(Int(j / 8)) And b(j Mod 8)) > 0 Then
          c = b(j Mod 8) Xor 255
          pri(Int(j / 8)) = pri(Int(j / 8)) And c
        End If
        j = j + i * 2
      Wend
    End If
    i = i + 2
  Wend
  k = 0
  j = 0
  For i = 2 To 1600000000
    If (pri(Int(i / 8)) And b(i Mod 8)) > 0 Then
      If i - l = 2 Then j = j + 1
      k = k + 1
      l = i
    End If
  Next
  MsgBox "总素数：" & k & ",最大素数：" & l & "，孪生素数对：" & j & ",用时：" & Timer - t & "秒"
End Sub



运行效果如下：
只有本站会员才能查看附件，请 登录
#28
ysr28572020-02-12 20:23
嗯，谢谢！您这个是1.6*10^10内的吧？这个是vba程序？我能用吗？谢谢！我试试吧！
太好了，谢谢，非常感谢！祝您新年快乐万事如意，身体健康阖家幸福安康！
#29
ysr28572020-02-12 20:28
是1.6*10^9吧？看你程序中的数字的位数是10位的
#30
ysr28572020-02-12 20:29
我的程序到现在还没有算到这么大呢。
#31
wmf20142020-02-12 20:41
哦，是10^9，10^10 long型数无法表达，可用double数做，这个类型可做到10^15，估计速度太慢，受内存限制也无法打表，但可以通过打10^5表来提高素数判断速度，速度会很慢。
#32
ysr28572020-02-12 21:55
谢谢！我复制到电脑，运行了一下程序，结果一样，时间比你长，可能是我开的程序多？我是一边看电视（电脑上），一边还运行了其它两个程序。
只有本站会员才能查看附件，请 登录
#33
ysr28572020-02-12 22:01
我的运行时间是1149秒多一点，我的另两个程序还没有出来结果呢。不太懂你的这个程序，能不能修改一下，仅算出10^9内的孪生素数呢？如何改呢？我不知道10^9内有多少，需要这个数据。谢谢！有空再弄吧！
#34
ysr28572020-02-12 22:18
您的程序确实速度快，比我的快多了，不知道原理，我直接把6改为0，就是把1.6*10^9改为了10^9，等会儿看看结果吧！确实是比我的程序快，学习了，弄明白了再调整一下我的程序。谢谢！
#35
ysr28572020-02-12 22:23
就是快，出来结果了，用时291秒，非常感谢！10^内有孪生素数对：3424507.
只有本站会员才能查看附件，请 登录


[此贴子已经被作者于2020-2-12 22:28编辑过]
#36
wmf20142020-02-12 22:57
筛法求素数了解下，该算法主要是可以最快速给出一定数据范围内的所有素数表，受限于编译器能申请的最大内存数，我用位表法最多可给出2^34范围内的素数表，大概是1.7×10^10，需要消耗1.1G内存，用c也要耗时半个钟头，没什么实用性。
#37
ysr28572020-02-13 01:21
嗯嗯好，埃拉托斯尼筛法？高手！我的朋友要这些数据的，我不关心这个数据，关心程序的速度！希望您能指导！提高速度，搞出大整数的快速乘法除法程序，重点是除法程序。我的程序太慢了，还没有算到1600000000.
谢谢！晚安！祝新春愉快万事如意！
#38
ysr28572020-02-13 11:36
额，是欧拉筛法？我改了一下程序，改成计算到10^10，还没有出来结果，也没有提示溢出，不知道是否能出结果？多长时间？
#39
ysr28572020-02-13 13:34
内存溢出了，我开的程序多还是咋了？等其它程序运行结束了再试试吧。
#40
wmf20142020-02-13 13:49
你还是去多学些基础吧。
long型数据能表达的数据范围大约是-2.1×10^9至2.1×10^9，你无法通过它计算到10^10.再就是光修改计算范围也没用，用位表筛法存储10^10范围内的素数表需要1.3G内存，byte型数组定义是pri(1300000000)，这么大数组vb无法定义。
#41
ysr28572020-02-13 16:56
嗯嗯好，多介绍一下，没地方学，这个少，网上都是vc版程序。
#42
ysr28572020-02-14 09:39
回复 40楼 wmf2014
您的程序速度很快了，还能提高吗？或者还能算出来更大的数据吗？
最后结果中的孪生素数对比实际多1对吧？把程序倒数第10
行的j=0，改为j=-1就行。
速度可以提高的，另外能不能改为可以从中间算起的程序？
如下数列：
7，13，19，……
5，11，17，……
包含了除了3和5一对的全部孪生素数对。
也包含了除了2和3以外的全部素数。
所以步长可以改为6，且从5开始算，或从6n+5开始算。这样就省掉了1/6，速度快了一点儿吧？
多谢指导，欢迎沟通！我不懂vc也弄不懂原理，欢迎直接给出个快速乘法除法程序vb版的，谢谢您！
#43
ysr28572020-02-14 09:49
回复 36楼 wmf2014
您能算到100或170亿吗？请给出100亿内的孪生素数对总个数吧，不用打表，给出个总个数就行。我朋友要这个数据，谢谢您了！
#44
wmf20142020-02-14 12:50
用vb的for空循环到100亿都要一分多钟，没什么动力让我那样做下去，给个别人做研究出的一个表你吧，应该可以给你朋友一个交代。
只有本站会员才能查看附件，请 登录
#45
ysr28572020-02-14 23:06
回复 44楼 wmf2014
刚才看到，谢谢！有个网友需要这些数据的，非常感谢！
#46
ysr28572020-02-15 00:05
回复 12楼 wmf2014
是的，RSA密码加解密程序只是快速乘法除法程序的一个应用，其它方面还会用到。这方面我做出了相关程序，是分开做的，大整数的分解程序(我的程序运行速度太慢只能分解几十位的整数的)，蒙哥马利快速幂模程序(这个道运行很快，若有了快速乘法除法程序就更快了，原理简单的，就是:幂的模等于模的幂，再求模)，求乘法的逆元的程序，求两数的最大公约的程序(也可以叫判断两数是否互质的程序，用到辗转相除法，也很快的)，这几个结合就可以破解RSA密码了。
RSA密码的原理方法(费马-殴拉定理)的逆命题可以用于判断大整数是否是素数，我已经编程，几十位的迅速出结果，超过百位的时间就长了。所以这个程序很重要，很有用，对我是个难题，高手可能是容易的。
(网上有个网站有能分解200位内的整数的程序，现在找不到那个网站了，RSA密码的公开模数在2千位以上目前是安全的，可能不是绝对安全，不否认有高手能破解，不能绝对认定。RSA有多个变种，有多因子的，两个大因子各自多少次方，再乘起来，想想就太大了，可能常用的就是双因子的，有的说是两个关联素数的积，其实这样的容易分解不安全，非关联素数的积倒是更安全。秀尔算法可用于快速分解大整数的，据说秀尔算法其中一个步骤必须用到量子计算机，咱也不知道这种算法的原理，量子计算机是并行算法，等于多少个可能的待测因子一次性试除完成，很快就找到余数为0的一个，当然还得结合传统的串行计算机才能完成破解RSA密码的任务。量子计算机虽然还没有正式上场，但这方面的研究已有突破性进展，试验性的机器不断报到表现不俗，RSA肯定也是不能永久安全，也是要改进和发展，或者弄出新的密码体制，肯定也是面临淘汰更新，网络安全不能没有密码，人类道德还不能让网络进入裸奔时代，这方面研究应该还是有意义的。)
   谢谢朋友指导帮助！希望朋友给出个快速乘法除法程序的vb版的程序！
祝各位老师新春快乐，身体健康万事如意！
#47
ysr28572020-02-15 00:16
RSA公钥密码体制的逆命题，可以用来判断大整数是否是素数，是确定性的，我的程序对于大于5位的整数都有效，若有了快速乘法除法程序运行就更快了，用到了快速幂模算法，多少位的指数也是很快就算完了。
    所以我要研究这个，希望老师帮助，给予指导！欢迎直接给出个快速乘法除法程序，或者解释一下原理！
谢谢您！
#48
wmf20142020-02-15 10:36
实话实说，你说这么多，我一句都没听懂。不过最后的意思我还是明白了，你还是要“欢迎直接给出个快速乘法除法程序”。
这很奇怪的，你说“RSA密码的原理方法(费马-殴拉定理)的逆命题可以用于判断大整数是否是素数，我已经编程，几十位的迅速出结果”，如果你真的搞定了就应该知道rsa通过公匙是很难逆出组成他们的大素数PQ的，否则用这种方式加密就没有意义了。你居然能把几十位的迅速得出结果，我深表佩服。
你这篇帖子就只是我俩的讨论，我至少为帮你解决问题不辞辛劳地给出代码了，你是不是也把你那个“几十位的迅速得出结果”的代码提供出来，让我学习学习？
期待ing!
#49
ysr28572020-02-15 16:28
回复 48楼 wmf2014
谢谢您的帮助，我只能发个主程序，因为代码太长，您知道原理那些可调用程序对你不成问题，就是些可调用的加减乘除程序。我电脑上正运行程序，还一边看电视剧，可以暂时停一下。先给你个判断素数的程序。分解因子效果不好，不发了，是不完全分解，只能分解成两个因子，至于是否是素因子就不管了，而且是部分类型的分解，不是全部合数都能分解。先说这么多，程序中缺少解释，希望您能理解，能看懂，不懂的话，我再补充注解。才看到，非常感谢您沟通！
#50
ysr28572020-02-15 16:34
回复 48楼 wmf2014
在判断素数中的公开模数是待判定的整数，假设其为素数的话，就逆回去了，无需分解，此时肺(n)=n-1.不用找pQ，(肺，希腊字母，打不出来)。
#51
ysr28572020-02-15 16:41
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
123456789
©2024, BCCN.NET
电脑版