[特别关注]中国剩余定理及求模的逆元的公式

ysr

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

求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

求乘法的逆元的程序代码，利用陆元鸿教授的矩阵变换法做的，计算小于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

求大数的乘法逆元的主程序代码，只发主程序：
  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

用辗转相除法计算两个数的最大公约数的程序也弄出来了，只发计算小于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

用辗转相除法求两个大数的最大公约数的程序代码，只发主程序：

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

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

ysr

求乘法的逆元的程序还可以解如下这样的方程，如：
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

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

ysr

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

ysr

辗转相除法求最大公约数也可以用于梅森数的快速分解，得到的是一个因数，如分解M659：7902859836985358356891715837313578515318368789285762814010081688109186064065709648812125和M659=2392032866531905486790942578809394338145620987608332988883503686824375178865503049616412016019962016447144819201720664620106359620960485637227891297994520232330261783830994590149049944504587400511487 最大公约数为：1319