差定理的重要应用

ysr

这个公开模数的一个因子可能在如下这个大整数附近：
40017044723637974584478003007505054918931838568551739572915256970688159436995219811701173699770978125966247837376268111829834719137533060159217957100562760365109185936511463290527787597396269816979318324278349898485992408319735573862554827528110757224503375227944468961640735918018807579884896497147802861443（有308位）

ysr

经过细化公式计算，如下整数更接近实际因子：
40940018678917991906496600760731395308987766044932326316076176437186400542946489190499138212105200919309548313554371874352414082770371197921281745387705947334680015723880583531442267364069256784337536190141636637905046501225871703456251831665529370747455866970323435672242717531597312978112028789442464134199（有308位）

费尔马1

请问ysr老师，您的检验结果出来了，张益唐的617位数究竟是不是素数?当今科技能否判断这么大的数字?

ysr

费尔马1 发表于 2021-10-7 00:00
请问ysr老师，您的检验结果出来了，张益唐的617位数究竟是不是素数?当今科技能否判断这么大的数字?

是合数，是能分解的，当今科技好像还分解不了，我正在试验分解，我的程序比较慢，而且是分步做的，分开做的每一步都是独立的程序，试验好了可以串在一起，程序复杂，所以，消耗精力，搞了好长时间还没有弄好。

ysr

如下是用来试验因子的程序，发一下代码：

Private Sub Command1_Click()
Dim m, n
m = Trim(Text1)
n = Trim(Text2)
n1 = n
Do While InStr(MCC1(Trim(m), Trim(n)), "/") <> 0 And s15 <= 50
s15 = s15 + 1
n = MPC1(Trim(n), 2)
Loop
If InStr(MCC1(Trim(m), Trim(n)), "/") = 0 Then
Text3 = n & "*" & MCC1(Trim(m), Trim(n))
Else
Do While InStr(MCC1(Trim(m), Trim(n1)), "/") <> 0 And s16 <= 50
s16 = s16 + 1
n1 = MPC(Trim(n1), 2)
Loop
If InStr(MCC1(Trim(m), Trim(n1)), "/") = 0 Then
Text3 = n1 & "*" & MCC1(Trim(m), Trim(n1))
Else
Text3 = "bu neng fenjie"
End If
End If

End Sub
'为了节省时间，仅仅变化末尾2位数字的，可能不行不能分解。

费尔马1

要检验一个正整数n是否是素数，采用半筛法。
√n=k，用3~k的素数分别去除n，进行检验。617位数开平方根是大约300位数。……

ysr

费尔马1 发表于 2021-10-7 02:31
要检验一个正整数n是否是素数，采用半筛法。
√n=k，用3~k的素数分别去除n，进行检验。617位数开平方根是 ...

大整数不能这么算，那是算不完的，用的是其他判定方法，速度稍快点儿，但是不能对合数分解。

我对上面的试验因子的试验出来了，结果是：bu neng fenjie，就是不能分解，不过仅仅是判断了末尾2位，就是仅仅有100个整数，更高位的无法判断，如果数据多了，是算不完的，所以，还要提高程序的精确度和速度！

费尔马1

王老师您好:数字无穷，电脑终有止境，这617位数已经够大了！既然当今科技无法判断，那么，这个数字就没有意义，还是不要研究了。

ysr

费尔马1 发表于 2021-10-7 05:31
王老师您好:数字无穷，电脑终有止境，这617位数已经够大了！既然当今科技无法判断，那么，这个数字就没有意 ...

咋没有意义呢？这是RSA密码的公开模数，如果你能分解，那RSA密码就不安全了，等于宣告破解，需要增大公开模数或者淘汰，甚至可能使网络进入裸奔状态！

ysr

费尔马1 发表于 2021-10-7 05:31
王老师您好:数字无穷，电脑终有止境，这617位数已经够大了！既然当今科技无法判断，那么，这个数字就没有意 ...

素数判断不是仅仅有常规的试除法，还有其他方法，判定素数和分解合数不一样，能判定一个大整数不是素数但不一定能分解，啥样的合数容易分解，啥样的不容易分解从而使密码更安全，这个问题关系重大，所以，研究是有价值的。