数学中国

标题: [特别关注]中国剩余定理及求模的逆元的公式 [打印本页]

作者: ysr 时间: 2017-10-5 22:45
标题: [特别关注]中国剩余定理及求模的逆元的公式
本帖最后由 ysr 于 2017-10-5 14:54 编辑

普及个知识:中国剩余定理在小学课本中有，大学也讲，所以老少皆宜。古代中国🇨🇳 研究已很精辟，并广泛应用。历代皇帝重视历法，历法中大量用到这种计算，古代中国历法精确就得益于此。农历是阴阳合历，既照顾太阳又照顾月亮，较复杂，我不懂历法，不知具体如何算。在现代科技中也会用到，如公钥密码体制中的公钥和私钥的计算。
法:若某数除以ABC余分别为r1，r2，r3，求此数？
求除A余r1要在BC的倍数中求，先求乘以BC使余数(/A)为1的乘率m，(或直接得出余r1的乘率)，则m乘r1与BC的积满足/A余r1。当数据很大不便于从1试到m，求m的方法古人叫“大衍求一术”，其实就是现代的求模的逆元，若ed/P余1则e与d互为逆元。查书，用到辗转相除法，好象没有公式，只讲到方法:辗转相除(用余数再去除除数)到余1再逆推回去。
我弄了个经验公式供试用:
求e模p的逆元d=？即ed/P余1，(e和P必须互质，不互质的姑何？没研究)

当r1=1，则d=1或P的倍数+1，或P+1，
当r2=1，则d=x2(p-1)，(这两个解可以证明的，下面的未证明)，
x1，x2，…为商，r1，r2，…为余，下面的合为一个公式，当rw=1，则d=x1(x2+x3+…+x(w-1)+1)+w-3，其中w，(w-1)，为下脚码，
由公式知，
当r3=1，则d=x1(x2+1)，
如求137/120的逆元？137/120=10……17，120/17=7……1，则d=7*119=833，833*137=114121，114120/120=951，
如131/120的逆元？131/120=1……11，120/11=10……10，11/10=1……1，则d=1*(10+1)=11，11*131=1441，1440/120=12，
注意:公式中只计算到倒数第二的商，倒数第一的商没用，公式逻辑未证明，经验公式。

作者: ysr 时间: 2017-10-5 23:54
例某数除120余3，除137余0，求此数？
解:由上知833*3*137/120余3，故此数为114121*3=342363.
这个不是最小的，故342363MOD(137*120)=13563，则13563为最小的满足题意的正确答案。

作者: ysr 时间: 2017-10-6 21:29
模的逆元可以是无穷多，上面的结果是不是最小我们就不管了，只要是真的逆元就行，我们可以通过除以最小公倍求余来得到满足中国剩余定理的最小值。

作者: ysr 时间: 2017-10-30 04:48
如何求出最小的逆元d呢？可以这样做:
例如:求315/11的逆元d？
解:315/11=28……7，11/7=1……4，7/4=1……3，4/3=1……1，据公式得:d=x1(x2+x3+1)+4-3=28*3+1=85，
而315*85=26775，26774/11=2434，故85是逆元，但不是最小。
85/11=7……8，而315*8=2520，2519/11=229，故8才是最小的逆元。
当然此题可以用试除法(穷举法)直接得出315*8MOD11=1.这样做同样费事。

作者: ysr 时间: 2017-10-30 05:11
本帖最后由 ysr 于 2017-10-29 21:17 编辑

有人这样做:由于315/11=28……7，7*8-1=0MOD11，故d=8。
这样做很简单，但当P很大时也很麻烦，故有时用上面公式更简便些。

作者: ysr 时间: 2017-10-30 05:29
再如上面的例子:833/120=6……113，而113*137-1=0MOD120，故113为最小的逆元。

作者: ysr 时间: 2017-10-30 07:35
由于3*113*137=46443=13563MOD(137*120)，故这样得出来的值也不一定是满足中国剩余定理的最小值，而13563/137=99=3*33，而33并不是逆元，虽99是满足*137/120余3的最小值，但要用穷举法试出来很费事，故用公式有时是较省事的。

作者: ysr 时间: 2018-2-21 16:05
中国剩余定理问题中，模数不是两两互质如何弄？
古人研究结果: (秦九韶)(1)找合适的定数(就是模数)，(2)约掉公因子，成新的定数(现代叫模数)。
注意:结果要符合原题意，要具体问题具体分析，自己灵活掌握。
欢迎探讨，欢迎批评！

作者: simpley 时间: 2018-2-22 07:02
67和23就不行。
其实求逆元的公式完全可由辗转相除法得出，但书写麻烦，还不如直接说相除法

作者: ysr 时间: 2018-2-22 08:45
谢谢关注！
例:求67模23的逆元？
67/23=2……21，23/21=1……2，21/2=10……1，故r3=1，x1=2，x2=1，由公式知逆元d=x1(x2+1)=2*(1+1)=4，4*67=268，267/23=11……14，故4非逆元，的确是反例，谢谢提供反例！
查资料，古人求逆元还要看末尾的商值的奇偶性，x3=10为偶数，故可能要另一种公式，再研究研究！谢谢朋友！欢迎继续探讨！

作者: ysr 时间: 2018-2-22 09:04
接前面的计算，由于x3=10为偶数，可能公式需要另一种，由于67*11=737，736/23=32，故11为逆元，x3+1=10+1=11，公式是否为xw+1？待研究，网上资料中见过这样的例子现在找不到了！再想想再研究一下，欢迎给出更多的特例！

作者: ysr 时间: 2018-2-22 09:24
还可能是这样:由于2*4+3=11，故公式为2*x1(x2+1)+3，……，2x1(x2+…+1)+3。

这个是猜测，需推导证明，前面公式是几年前弄出的，逻辑关系也推出过，两头往中间推，通了，相等了，草稿纸丢了，当时认为类似的公式早已有人弄出来了，地球人都知道的咱不发，所以没有整理和重视，后来找不到这样的公式，所以我才发出来这个，前面公式的证明我现在也没有时间搞了，反对研究的太多了，水平有限，希望感兴趣的研究和探讨！为数学做贡献，若真的是一个创新的方法超码自己长知识，自己应用方便。在此再一次真诚感谢这位朋友！感谢所有关注鼓励支持我的朋友！

作者: simpley 时间: 2018-2-23 13:50
求逆元可用欧拉演段

作者: simpley 时间: 2018-2-23 14:22
设倒数第一个商是X1，正数第2个商是XN。则逆元为AN。
AN=A（N-2）+A（N-1）*XN。A0=1，A1=X1。最后取值时，N为奇数AN为正，偶数为负.

作者: ysr 时间: 2018-2-23 16:05
谢谢探讨！不太好懂，最好举个例子。

作者: ysr 时间: 2018-2-24 19:41
可能这样公式适用情况仅一部分，分类也不止上面说的两类，分类方法也可能不是上面说的那样，有没有总公式？也可以有的。
求逆元的方法据网上资料介绍有多种，下面主要介绍两种常用法:
一、枚举法:就是乘1，2，……，m，直到找到余数为1的那个乘率m。此法只能用于小数值，数值没有电脑是算不完的。
二、辗转相除再逆推，此法可以用于大数值计算，还可用于编程。下面举例说明:
例:求23模67的逆元？
67=2*23+21，23=1*21+2，21=10*2+1，
1=21-10*2=(67-23*2)-10*2=67-23*2-(23-21)*2

作者: ysr 时间: 2018-2-24 20:20
本帖最后由 ysr 于 2018-2-24 12:22 编辑

可能这样公式适用情况仅一部分，分类也不止上面说的两类，分类方法也可能不是上面说的那样，有没有总公式？也可以有的。
求逆元的方法据网上资料介绍有多种，下面主要介绍两种常用法:
一、枚举法:就是乘1，2，……，m，直到找到余数为1的那个乘率m。此法只能用于小数值，大数值没有电脑是算不完的。
二、辗转相除再逆推，此法可以用于大数值计算，还可用于编程。下面举例说明:
例:求23模67的逆元？
67=2*23+21，23=1*21+2，21=10*2+1，
1=21-10*2=21-(23-21*1)*10=11*21-10*23=11*(67-2*23)-23*10=11*67-32*23，
故逆元为-32，是负值，当被除数(暂称，古人有别称)小于模数时逆元为负值，加上模数或模数的倍数就成正值，即模数中的补数。67-32=35即为逆元，35*23-1=804，804/67=12.

这个式子也同时得到67/23的逆元为11。

可见当被除数大于模时逆元为正，小于模时逆元为负。32=10+2*(10+1)=x3+x1(x3+1)。
11=x3+1。

感兴趣的研究一下，这东西不应该成为人们前进道路上的壁垒，应该是人们熟悉并方便应用的。也不必当课题专门研究，就在你无聊时考虑一下，打发时光，只要你感兴趣，奖金啥的都是扯淡，想通了让你快乐并获得简便方法就好！

谢谢朋友讨论！欢迎关注！

作者: ysr 时间: 2018-2-24 23:47
再举一个例子，是网上的截图，如下:
11/26的逆元为-7+26=19，26/11的逆元为3，7=2*3+1=x1*r2+1，3=r2，可见与上例公式不同，不是同一类，公式能否统一成一个？还是要研究研究！

作者: simpley 时间: 2018-2-25 00:04
正负由奇偶决定，和数的大小无关。比如9模29的逆元为13.

作者: ysr 时间: 2018-2-25 02:31
本帖最后由 ysr 于 2018-2-24 18:33 编辑

嗯嗯，谢谢关注讨论！(负值也只是中间过程可以转化为正值)

作者: ysr 时间: 2018-2-25 03:57
求29/9的逆元？29=3*9+2，9=2*4+1，
这个用前面的公式也能算出来:d=x2(P-1)=4*8=32，32MOD9=5，5为逆元。

1=9-2*4=9-(29-3*9)*4=13*9-4*29，
这个正负值反了，正好对调，29/9的逆元为-4，-4+9=5。

作者: ysr 时间: 2018-2-25 09:16
本帖最后由 ysr 于 2018-2-25 01:27 编辑

前面的反例中，67/23，29/9的倒数第一个商值均为偶数；26/11的倒数第一个商值为奇数，倒数第二和倒数第三个商值为偶数。

求26/11的逆元？这个居然也可用前面的公式稍加修改:d=x1(x2+1)/2=2*(2+1)/2=3，即为逆元。

是巧合还是有逻辑关系？要研究研究，有趣复杂。

作者: simpley 时间: 2018-2-25 13:30
求逆元用欧拉演段，这是通用方法。不应有别的公式。
另外中国剩余定理有的不是必定要用逆元，用欧拉演段可直接解出。
如孙子算经的题，求35x=2(mod 3),可直接得x=1,不用先算逆元。

作者: ysr 时间: 2018-2-25 15:08
正确！多谢关注和讨论！

作者: ysr 时间: 2018-3-1 10:08
各位老师朋友元霄快乐！欢迎关注！

字谜:高台对映月分明(打一字)

我也不知谜底，供乐！

作者: ysr 时间: 2018-3-1 18:44
原题给出四个字供选:省，照，昙，晨。
我不知道哪个是谜底，猜一下，选照吧！月下对映就是照的意思吧？我猜！

欢迎关注！供乐！

作者: ysr 时间: 2018-3-5 10:09
诗词数学与人生(新韵)
真言赛大钟，曲罢鬼神惊。
阻碍千山里，心潮上碧空。

作者: luyuanhong 时间: 2018-3-16 23:25
[attach]65358[/attach]

[attach]65359[/attach]

作者: ysr 时间: 2018-3-17 15:50
谢谢陆教授的精彩解答！感谢多次指导和帮助！

作者: ysr 时间: 2018-3-24 14:01
终于明白了这个道理，其实与辗转相除法或更相减损法，或方程加减消元法处理系数，是一个道理，只不过是整列计算(我把纵向排列的叫列)，最终使上一行一个为1一个为0，虽然无法转化为统一的公式，但是可以不用再逆推而直接得到abcd几个数，从而得到要求的结果，简便，可以用于编程。

作者: ysr 时间: 2019-12-9 17:18
前面的是陆元鸿教授做的求乘法的逆元的方法和例子，根据这种方法（矩阵变换法）我已做好程序，对各种类型都有效，相当于一个总公式。

求n模p的逆元，二者必须互质，否则就没有逆元，即使程序能给出了结果也是错的。

例子：137模120 的逆元为：113，我曾用公式手工计算得833，也对，因为833MOD120=113. 再如：131模120 的逆元为：11，9模29 的逆元为：13，29模9 的逆元为：5，67模23 的逆元为：11，23模67 的逆元为：35，都是对的。

而268模67 的逆元为：1，67模268 的逆元为：1；是错的，因为268/67=4，268 MOD 67 =0,而a的初始值是1，辗转相除的条件是n除以p余数不为0，所以程序结束而输出初始值1.

而123模15 的逆元为：1，15模123 的逆元为：113，都是错的；因为123和15不互质，有公约数3，不可能得到逆元，最终3/3=0，不会得到余数为1的情况，所以程序输出的值是错的，是余数为0时的a的值。

所以这一点要注意，先判断n和p是否互质。

作者: ysr 时间: 2019-12-15 20:30
求乘法的逆元的程序代码，利用陆元鸿教授的矩阵变换法做的，计算小于10位的两个数的逆元，n模p的逆元。

Private Sub Command1_Click()
Dim n, p, a, b, c, d, r
  n = Trim(Text1.Text)
  p = Trim(Text2.Text)
  a = 1
  b = 0
  c = 0
  d = 1

  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


  Text3 = n & "模" & p & " 的逆元为：" & a


End Sub

Private Sub Command2_Click()
Text1 = ""
Text2 = ""
Text3 = ""
End Sub
大数的乘法逆元的程序也出来了，如：67模147573952589676412927 的逆元为：145371356282367809749。由于代码太长，需要可调用程序如大数的乘法除法加法减法等，不发了，下面给出主程序。

作者: ysr 时间: 2019-12-15 20:40
求大数的乘法逆元的主程序代码，只发主程序：
  Private Sub Command1_Click()
  Dim n, p, a, b, c, d, r
  n = Trim(Text1.Text)
  p = Trim(Text2.Text)
  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
  If Len(a) = 0 Then
  a = 0
  Else
  a = a
  End If

  End If

  Text3 = n & "模" & p & " 的逆元为：" & a

End Sub

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

作者: ysr 时间: 2019-12-16 00:33
用辗转相除法计算两个数的最大公约数的程序也弄出来了，只发计算小于10位的数的程序，如：12345679和111 最大公约数为：37。

  Private Sub Command1_Click()
Dim a, b, c, d, r
  a = Trim(Text1.Text)
  b = Trim(Text2.Text)

  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



  Text3 = a & "和" & b & " 最大公约数为：" & d


End Sub

Private Sub Command2_Click()
Text1 = ""
Text2 = ""
Text3 = ""
End Sub
大数值的程序只发主程序。如：1234567912345679和111111111 最大公约数为：12345679；1234567912345679和111111 最大公约数为：37。大数运算的可调用程序代码太长不发了。

作者: ysr 时间: 2019-12-16 00:35
用辗转相除法求两个大数的最大公约数的程序代码，只发主程序：

Private Sub Command1_Click()
  Dim a, b, c, d, r
  a = Trim(Text1.Text)
  b = Trim(Text2.Text)
  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


  Text3 = a & "和" & b & " 最大公约数为：" & d

End Sub

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

作者: ysr 时间: 2019-12-16 01:05
这两个程序可以结合起来使用，先判断n和p是否互质，再求n模p的逆元。这两个程序都有用，如rsa公钥密码中的公钥和私钥是互为逆元的，可以用这个程序来求出来，知道了公钥和公开模数，就可以用此程序求出密钥，从而破解密码。公开模数虽然巨大，其实容易分解，因为是特殊类型的合数，常规法不能分解，但用特殊算法可以分解，如有的是关联素数的积，知道了啥是关联素数就可以快速分解了，还有的可能用到了梅森素数？由于梅森素数才发现了51个，那就容易了。还有的两个素数因子的比值小于100000000的，那个也容易，相关方法我在本论坛发表过，虽然没有弄出程序，有人试了小数值的可以不过小于10位的根本部用这么复杂就可以分解。
程序还要用到蒙哥马利快速幂模算法，原理是幂的模等于模的幂。
感谢陆元鸿教授帮助和指导！使我弄出了求乘法的逆元的程序，离弄出破解密码的程序进了一步。
还要用到大整数及超大整数的快速乘法除法运算程序，有人会这个但不帮忙，比如数学研发论坛的郭xq老板就会，除了不帮忙还把我禁言了，离了x屠夫不吃带毛猪，只要死不了，继续研究下去，一定弄出来。即使没有用，起码能当智力游戏，一定要弄出来。
上面的程序还有其它用处，欢迎感兴趣的朋友试用，欢迎沟通！

作者: ysr 时间: 2019-12-17 22:15
本帖最后由 ysr 于 2019-12-17 19:21 编辑

求乘法的逆元的程序还可以解如下这样的方程，如：
355x-113y=1
n=355，p=113，输入程序得a=106，则c=(355*106-1)/113=333，
所以有x=113t+106，y=355t+333，
令B=y/x，当t=293，则有：B=104348/33215=3.141592653921，
当t=292.5，则有：B=104170.5/33158.5=3.14159265354674，
故可知，t在292～293之间时，B～π，
解这个一次方程，代入准确的π，就可以得到精确的t的值：
（355t+333）/（113t+106）=π，（355-113π）*t=106π-333，
这样就得到t的准确值，可以用电脑做，编程做一下，位数多，不宜用手工算。不过，累似的可以得到多种这样的方程，得到多种t的值，有可能得到一种t的值是有规律的容易记忆的，这就是我们的目的！

作者: ysr 时间: 2019-12-18 03:29
本帖最后由 ysr 于 2019-12-17 19:37 编辑

按照前面的矩阵变换法，此类方程的解为：x=a+bt，y=c+dt，而a，b，c，d是全体整数，若严格按照辗转相除法做，则都是正整数。虽然这样步骤多，循环次数多（数学方法中叫迭代，程序中叫递归或循环），结果是准确的正确的靠谱的。

作者: ysr 时间: 2019-12-19 22:26
前面的一次方程中，有了t的精确值就可以用来求精确的圆周率，验证结果：验证结果：3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823066470938446095505822317253594081284811174503与实际仅末尾1位不同，实际是2 这里是3，点后有159位与实际相同。

作者: ysr 时间: 2019-12-21 11:43
辗转相除法求最大公约数也可以用于梅森数的快速分解，得到的是一个因数，如分解M659：7902859836985358356891715837313578515318368789285762814010081688109186064065709648812125和M659=2392032866531905486790942578809394338145620987608332988883503686824375178865503049616412016019962016447144819201720664620106359620960485637227891297994520232330261783830994590149049944504587400511487 最大公约数为：1319

作者: ysr 时间: 2020-1-28 07:21
这个是求乘法逆元的3种情况，就是原理和方法，根据这个原理方法就可以做程序代码。前面的程序就是这个原理编程的。

作者: ysr 时间: 2020-1-28 10:41
前面陆元鸿教授给出的解答中的两个例子已经是两种情况，两种类型，我只是增加了一种类型，就是7模4的逆元为3，这一种情况，这样就全面了，全体情况都能对付了。

作者: ysr 时间: 2020-1-28 10:56
重发一下陆元鸿教授解答的截图，某些图片显示缓慢，所以再发一下方便感兴趣的朋友查看：

作者: ysr 时间: 2020-1-30 09:36
求模的逆元的原理和方法很重要，可以用于快速破解RSA密码，而不用这个法用无穷枚举法那是破解不了的，不仅人工无法完成，任何计算机即使量子计算机也不行。所以，要破解RSA密码，必须是传统计算机和量子计算机结合起来，目前量子计算机还是探索试验阶段，所以要依赖好数学方法，才能破解某些密码，这个方法重要。
目前RSA密码中的公开模数n的长度可能已经普遍采用2048位以上的，而传统计算机所能分解的大整数的长度是有限的，但不是不能分解，方法好的话，尤其会大整数的快速乘法除法程序的高手，那是很可能的，甚至是容易的快速的。值得注意，值得研究。
欢迎感兴趣的朋友一起探讨，欢迎讨论欢迎沟通！

作者: njzz_yy 时间: 2020-2-2 18:38
祝破解RSA密码

作者: ysr 时间: 2020-2-4 09:11

njzz_yy 发表于 2020-2-2 10:38
祝破解RSA密码

您出书了吗？谢谢朋友关注！我不会大整数的快速乘法除法程序，目前我只能分解几十位的整数，若是又了大整数？快速乘法除法程序，上千位的也是容易分解的。目前网上有的程序已经能分解200多位以内的整数了。RSA密码在2048位以上才是安全的，但已经不是绝对安全的，可能有的高手能破解密码或者是强势攻击。强势攻击可能是物理法。

作者: ysr 时间: 2020-2-4 13:33
前面的求梅森合数的因子的原理是把目前发现的梅森合数的因子的种类都计算出来，乘起来的积与梅森合数求最大公约数就可以迅速得到一个因子，仅用于梅森合数的分解。

作者: njzz_yy 时间: 2020-2-5 20:27

ysr 发表于 2020-2-4 09:11
您出书了吗？谢谢朋友关注！我不会大整数的快速乘法除法程序，目前我只能分解几十位的整数，若是又了大整 ...

我2008年出书，停了数学研究，在2019年才重启数学研究，看到你这位网友数学研究有声有色，能体会到中间的酸甜苦辣，其实研究数学很幸福，希望网友们成果多多

作者: ysr 时间: 2020-2-6 12:42

njzz_yy 发表于 2020-2-5 12:27
我2008年出书，停了数学研究，在2019年才重启数学研究，看到你这位网友数学研究有声有色，能体会到中间的 ...

谢谢您的鼓励！祝贺您出书！如果心情好了，我也可能自费出书，以便留下个痕迹或记念。谁也不知道的纪念！
目前社会现状是普遍缺少科学精神，如果有的人不愿意看别人的东西，只推广自己的，甚至别人给你指出了缺点和错误也不改正，那就没人看了，会被当垃圾。如果人人都不去看科学文章，不关心科学问题如何解决，都认为是科学家大学生的事，中国就不会再产生大学生和科学家，不有科学土壤！我的力量渺小，不能改变现状。

我弄出了许多程序，想传上来保存。可惜网速慢，我这里用电脑打不开本论坛。只能用手机打开。
传上来感兴趣的可以方便使用。等我那天死翘翘了，也算留下个痕迹。
有机会了再传吧！程序有：哥德巴赫猜想的素数和对个数的计算结果和程序统计的实际值，有计算孪生素数对个数的程序，有判断素数的，分解因数的，解方程的，求模的逆元的，求最大公约数的（后面这三个还有快速幂模程序，结合起来就可以破解RSA密码），计算三角函数的，等，有人感兴趣的话，我有机会传上来。

作者: njzz_yy 时间: 2020-2-6 19:02
本帖最后由 njzz_yy 于 2020-2-6 19:12 编辑

ysr 发表于 2020-2-6 12:42
谢谢您的鼓励！祝贺您出书！如果心情好了，我也可能自费出书，以便留下个痕迹或记念。谁也不知道的纪念！ ...

谢谢ysr 坛友回复与祝贺！我主攻素数问题，我的邮箱njzzyy@163.com，方便的话，程序发我邮箱，谢谢！最近主攻孪生素数，哥德巴赫猜想等，只知道10^9范围内的孪生素数实际值，要有更大范围值请提供，谢谢！，如果当时不出书，手稿搬了几次家，可能就没了，书稿用电脑完成，增加了不少内容，电脑写作，效率高了好多好多倍，，现在有好多内容都搞不清楚了，得看自己写的书，非常方便，其实，因为书稿完成时间不充足，急着规定时间出版，有些内容没写进去，现在要回忆困难，要是有条件，再研究10来年，把这个理论搞完善点再版，个人能力太有限，心有余力不足，
破解RSA密码是个好项目，可惜我缺这方面知识，我乐意与人合作研究问题，没遇到合作者。

作者: ysr 时间: 2020-2-7 07:27
本帖最后由 ysr 于 2020-2-6 23:31 编辑

njzz_yy 发表于 2020-2-6 11:02
谢谢ysr 坛友回复与祝贺！我主攻素数问题，我的邮箱，方便的话，程序发我邮箱，谢谢！最近主攻孪生素数 ...

谢谢老朋友！这个是好法，先发你邮箱！先发求孪生素数的吧！这个范围没问题可能时间长，我试试，我不会快速乘法除法程序，判断素数结合了快速幂模算法速度提高不少，能判断几十位的，但时间长了。10^10的没问题，估计得一个小时，我先试试！如果会快速乘法除法程序，1秒钟算多少步大整数的乘法除法程序，那就块多了，几秒几分就行。您会这个或知道原理就是快速傅立叶变换的话，请给讲讲。我先试试多长时间出结果。

作者: ysr 时间: 2020-2-7 11:04
正在验证计算，速度不快，计算结果还没有出来，判断单个的素数速度快，分段计算可能速度快，且控件容量小，计算的多了结果显示不完全。如下结果道是快，几乎没有时间迅速出来结果：
1000000000与1000000200之间有1对孪生素数对:
1000000007和 1000000009 孪中1000000008
100000000与100000200之间有1对孪生素数对:
100000037和 100000039 孪中100000038

作者: ysr 时间: 2020-2-7 14:19
还没有出来结果，太慢了，等会儿再调整一下程序。照片占空间传不上来。

作者: ysr 时间: 2020-2-7 16:30

njzz_yy 发表于 2020-2-6 11:02
谢谢ysr 坛友回复与祝贺！我主攻素数问题，我的邮箱，方便的话，程序发我邮箱，谢谢！最近主攻孪生素数 ...

结果还没有出来，开了3个程序运行，后两个是调整了一下的，速度没有明显的提高。晚上或明天再给你发程序和结果。

作者: ysr 时间: 2020-2-7 18:48
10^9内的实际孪生素数对个数结果还没有出来，发个用连乘积公式计算的结果：
结果还没有出来，开了3个程序运行，后两个是调整了一下的，速度没有明显的提高。晚上或明天再给你发程序和结果。

作者: ysr 时间: 2020-2-7 19:07
连乘积公式结果：整数1000000000 其方根内最大素数31607 方根内的素数个数m=3401 (方根为)31622.7766016838 有31621个区间，其中每个区间孪生素数对个数的平均值122.510367478784 总对数为3873900.33004663，连乘积公式结果：整数10000000000 其方根内最大素数99991 方根内的素数个数m=9592 (方根为)100000 有99999个区间，其中每个区间孪生素数对个数的平均值313.824126174749 总对数为31382098.7933487

作者: ysr 时间: 2020-2-7 19:46

njzz_yy 发表于 2020-2-6 11:02
谢谢ysr 坛友回复与祝贺！我主攻素数问题，我的邮箱，方便的话，程序发我邮箱，谢谢！最近主攻孪生素数 ...

朋友好！程序运行慢，还在运行。给你发个用连乘积公式计算孪生素数对个数的程序吧！已经发你邮箱了，请查收！

祝愿新年快乐身体健康阖家安康万事如意！

作者: ysr 时间: 2020-2-7 19:47

njzz_yy 发表于 2020-2-6 11:02
谢谢ysr 坛友回复与祝贺！我主攻素数问题，我的邮箱，方便的话，程序发我邮箱，谢谢！最近主攻孪生素数 ...

作者: ysr 时间: 2020-2-7 20:05
不会快速乘法除法程序，效率低运行慢。
不行的话分段计算会快些，明天再给你发，谢谢朋友关注鼓励！

作者: njzz_yy 时间: 2020-2-7 20:18
ysr 辛苦了，非常感谢！在大傻8888888的帖子： x以内孪生素数的个数新式子，请网友用数据检验！有天山草老师40万亿亿内的数据，要是能找到他们用的程序就好了，

作者: ysr 时间: 2020-2-7 22:12

njzz_yy 发表于 2020-2-7 12:18
ysr 辛苦了，非常感谢！在大傻8888888的帖子： x以内孪生素数的个数新式子，请网友用数据检验！有天山 ...

谢谢！亿亿也就是10^16次方，用连乘积公式可以快速算出来，程序需要改一下我发给你的程序会可能会溢出的，我试试，你也可以试试，要是有其他函数或公式就不会溢出了，我有个公式也不过是个经验公式或理论上的下限公式，没有得到专家认可的，不必用了。由于网站打不开，大傻的文章也不好找了，他的公式您自己参考吧！程序还在运行，出了结果再给你发吧！不会快速乘法除法程序是不行，程序运行太慢了。等我明天分段计算一下，把数据给你，供参考。欢迎探讨欢迎交流沟通！谢谢！祝新年幸福！身体健康万事如意！

作者: ysr 时间: 2020-2-7 22:26

njzz_yy 发表于 2020-2-7 12:18
ysr 辛苦了，非常感谢！在大傻8888888的帖子： x以内孪生素数的个数新式子，请网友用数据检验！有天山 ...

是40万亿亿？咋用得着那么大了？我立马改一下程序给你发过去，这么大的就只好用连乘积公式了，没有快速乘法除法程序是得不到实际值的，计算量太大运行时间太长，而连乘积公式是最接近实际的。等会儿我试试，您不要熬夜！晚安！

作者: ysr 时间: 2020-2-8 01:17
改进版程序给你发邮箱了，请查收。速度还是太慢，11位以内的可以迅速出来结果。大整数理论上没问题就是速度慢，比值每一步都是移动十几位向后，再取整数计算的，相当于精确到点后十几位，由于速度慢小数点后不能计算的位数太多，经验证比较结果略小于实际，就是说大整数的结果是略小一点偏小了。
原因主要是咱不会大整数的快速乘法除法程序，对我是难题，有高手已经解决了大整数的快速乘法除法程序的问题，没人指导帮忙，等攻克了这个难关再弄个快速程序发给你。谢谢！欢迎指导！欢迎光临关注！晚安！

作者: ysr 时间: 2020-2-8 12:07
程序还在运行结果没有出来，程序运行界面上老是显示未响应，是死机了还是咋的？再会儿关闭程序，重新分段计算把结果发给你。

作者: ysr 时间: 2020-2-8 12:13
程序界面虽然显示未响应，但移动鼠标指针在界面上会变成个转动的圆圈，说明程序还在运行

作者: njzz_yy 时间: 2020-2-8 12:43
本帖最后由 njzz_yy 于 2020-2-8 12:45 编辑

ysr 发表于 2020-2-8 01:17
改进版程序给你发邮箱了，请查收。速度还是太慢，11位以内的可以迅速出来结果。大整数理论上没问题就是速度 ...

谢谢ysr！辛苦了，我只有10^9的孪生素数个数，能算到10^11也不不错，直接把10^9，10^10的孪生素数个数发上来，谢谢！我搞理论，实在没精力搞程序，30多年前用BASIC编过简单程序，电脑运行几天计算的范围也很小，

作者: ysr 时间: 2020-2-8 13:17

njzz_yy 发表于 2020-2-8 04:43
谢谢ysr！辛苦了，我只有10^9的孪生素数个数，能算到10^11也不不错，直接把10^9，10^10的孪生素数个数 ...

感谢朋友关注！程序还在运行，等会儿出不来结果的话就退出程序，再分段计算给你发个结果下，我的连乘积公式经过验证，在大于100000时已经大于实际了，不过采用大整数的乘除法程序反而略低于实际，如100000内实际有1224对孪生素数对，而连乘积公式结果是1231，采用大整数计算结果由于前面的原因说的，循环迭代，每一次都是精确到点后15位然后再移动回去而取整数，小数部分就丢了，计算结果反而略小于实际，如采用大整数的乘法除法算法100000的内的孪生素数对个数是1208对，反而略小于实际，由于考虑速度原因，发给你的程序在12以上才采用这个算法，所以12位以上的数据是略小于实际的，在5位内也是小于实际的，在5～11位之间是大于实际的。

作者: ysr 时间: 2020-2-8 13:29
我也是用的VB语言编程序的。连乘积公式只是个理论值，只能做个参考。等会儿程序没有结果的话就退出程序，分段计算把结果发给你。

作者: ysr 时间: 2020-2-8 15:31
我关掉了程序，分段计算，从10^9开始，分段短的花可以迅速出结果，如：
1000000000与1000000020之间有1对孪生素数对:
1000000007和 1000000009  孪中1000000008
1000000020与1000000200之间有0对孪生素数对:
1000000200与1000001000之间有2对孪生素数对:
1000000409和 1000000411  孪中1000000410
1000000931和 1000000933  孪中1000000932
累计3个了。

作者: ysr 时间: 2020-2-8 16:17
按这个密度计算的话就是1000个里面有3个孪生素数对，10^9～10^10之间差为9*10^9，将有3*9*10^6=27*10^6个孪生素数对，加上10^9内据说约有3873900个（也是连乘积公式结果大于实际肯定），总个数约为30873900比连乘积公式结果31382098小。

作者: ysr 时间: 2020-2-8 16:18
按这个密度计算的话就是1000个里面有3个孪生素数对，10^9～10^10之间差为9*10^9，将有3*9*10^6=27*10^6个孪生素数对，加上10^9内据说约有3873900个（也是连乘积公式结果大于实际肯定），总个数约为30873900比连乘积公式结果31382098小。

作者: ysr 时间: 2020-2-8 16:32
调整了一下程序，用前面的方法大整数乘法除法，来计算（也是用的连乘积公式）的结果是：10^9内有3872518个，10^10内有31378142个。

作者: ysr 时间: 2020-2-8 16:36
不知道是否是比实际大，仅能做参考值。

作者: ysr 时间: 2020-2-8 16:49
我有个经验公式，以前发过一个比这个小的，这个也是下限公式比过去发的方便：设整数为x，令m=x/lnx，则x内的孪生素数对个数为s=m/lnm，例如当x=10^10有m=10^10/ln10^10=434294428.s=434294482/ln434294482=21835657.
仅供参考。

作者: ysr 时间: 2020-2-8 16:52
我有个经验公式，以前发过一个比这个小的，这个也是下限公式比过去发的方便：设整数为x，令m=x/lnx，则x内的孪生素数对个数为s=m/lnm，例如当x=10^10有m=10^10/ln10^10=434294482.s=434294482/ln434294482=21835657.
仅供参考。

作者: ysr 时间: 2020-2-8 17:14
上网慢，打开网站慢，发个帖子很不容易，咋回事？

作者: ysr 时间: 2020-2-8 18:02
1000001000与1000002000之间有4对孪生素数对:
1000001447和 1000001449  孪中1000001448
1000001537和 1000001539  孪中1000001538
1000001789和 1000001791  孪中1000001790
1000001801和 1000001803  孪中1000001802
、1000002000与1000005000之间有11对孪生素数对:
1000002359和 1000002361  孪中1000002360
1000002821和 1000002823  孪中1000002822
1000003271和 1000003273  孪中1000003272
1000003469和 1000003471  孪中1000003470
1000003577和 1000003579  孪中1000003578
1000003889和 1000003891  孪中1000003890
1000004249和 1000004251  孪中1000004250
1000004567和 1000004569  孪中1000004568
1000004609和 1000004611  孪中1000004610
1000004867和 1000004869  孪中1000004868
1000004891和 1000004893  孪中1000004892
累计18个了，比按每1000里面3个算还多了3个孪生素数对。

作者: ysr 时间: 2020-2-8 18:09
1000005000与1000010000之间有13对孪生素数对:
1000005449和 1000005451  孪中1000005450
1000005971和 1000005973  孪中1000005972
1000006037和 1000006039  孪中1000006038
1000006127和 1000006129  孪中1000006128
1000006457和 1000006459  孪中1000006458
1000006661和 1000006663  孪中1000006662
1000007651和 1000007653  孪中1000007652
1000007927和 1000007929  孪中1000007928
1000008257和 1000008259  孪中1000008258
1000008311和 1000008313  孪中1000008312
1000009277和 1000009279  孪中1000009278
1000009529和 1000009531  孪中1000009530
1000009559和 1000009561  孪中1000009560
累计已经31个比按每一千个里面有3个还多1个孪生素数对。

作者: ysr 时间: 2020-2-8 18:20
1000010000与1000015000之间有14对孪生素数对:
1000010747和 1000010749  孪中1000010748
1000010969和 1000010971  孪中1000010970
1000011107和 1000011109  孪中1000011108
1000011767和 1000011769  孪中1000011768
1000011821和 1000011823  孪中1000011822
1000012217和 1000012219  孪中1000012218
1000012337和 1000012339  孪中1000012338
1000012679和 1000012681  孪中1000012680
1000012901和 1000012903  孪中1000012902
1000013087和 1000013089  孪中1000013088
1000013141和 1000013143  孪中1000013142
1000013561和 1000013563  孪中1000013562
1000013921和 1000013923  孪中1000013922
1000014581和 1000014583  孪中1000014582
累计已经是45个了，正好平均一千个里面有3个。

作者: ysr 时间: 2020-2-8 18:30
1000015000与1000020000之间有18对孪生素数对:
1000015349和 1000015351  孪中1000015350
1000015649和 1000015651  孪中1000015650
1000016231和 1000016233  孪中1000016232
1000016489和 1000016491  孪中1000016490
1000016621和 1000016623  孪中1000016622
1000017257和 1000017259  孪中1000017258
1000017287和 1000017289  孪中1000017288
1000017959和 1000017961  孪中1000017960
1000018169和 1000018171  孪中1000018170
1000018379和 1000018381  孪中1000018380
1000018601和 1000018603  孪中1000018602
1000018709和 1000018711  孪中1000018710
1000018967和 1000018969  孪中1000018968
1000019159和 1000019161  孪中1000019160
1000019351和 1000019353  孪中1000019352
1000019399和 1000019401  孪中1000019400
1000019861和 1000019863  孪中1000019862
1000019897和 1000019899  孪中1000019898
已经累计63个孪生素数对，比按每一千个有3个算还多3个。
所以，分布规律是时蔬时密，平均值还是均匀的，哈哈哈。

作者: ysr 时间: 2020-2-8 18:37
1000020000～1000025000之间有11对，
累计有74对。

作者: ysr 时间: 2020-2-8 18:47
1000025000～1000030000之间有16对，累计90对。

作者: ysr 时间: 2020-2-8 19:06
1000030000与1000035000之间有16对孪生素数对:
1000030061和 1000030063  孪中1000030062
1000030481和 1000030483  孪中1000030482
1000030571和 1000030573  孪中1000030572
1000030979和 1000030981  孪中1000030980
1000031141和 1000031143  孪中1000031142
1000031867和 1000031869  孪中1000031868
1000032347和 1000032349  孪中1000032348
1000032881和 1000032883  孪中1000032882
1000033037和 1000033039  孪中1000033038
1000033577和 1000033579  孪中1000033578
1000033961和 1000033963  孪中1000033962
1000034309和 1000034311  孪中1000034310
1000034417和 1000034419  孪中1000034418
1000034459和 1000034461  孪中1000034460
1000034471和 1000034473  孪中1000034472
1000034597和 1000034599  孪中1000034598
累计106个

作者: ysr 时间: 2020-2-8 19:11
1000035000～1000040000之间有19对，累计125对。

作者: ysr 时间: 2020-2-8 19:23
1000040000～1000045000之间有20对，累计145对

作者: ysr 时间: 2020-2-8 19:47
1000045000～1000050000之间有17对，累计162对。

作者: ysr 时间: 2020-2-8 20:01
1000050000～1000055000之间有19对，累计181对。

作者: ysr 时间: 2020-2-8 20:02
1000050000～1000055000之间有19对，累计181对。

作者: ysr 时间: 2020-2-8 20:05
1000055027和1000055029是一对孪生素数。

作者: ysr 时间: 2020-2-8 20:23
1000055000～1000060000之间有21对，累计202对。

作者: ysr 时间: 2020-2-8 20:24
1000055000～1000060000之间有21对，累计202对。

作者: ysr 时间: 2020-2-8 20:35
1000060000～1000065000之间有15对，累计217对，照这个密度，总个数可能会略超过27*10^6.

作者: ysr 时间: 2020-2-8 20:36
1000060000～1000065000之间有15对，累计217对，照这个密度，总个数可能会略超过27*10^6.

欢迎光临数学中国 (http://www.mathchina.com/bbs/)