不依赖素数库分解大数、特大数

朱容仟

重生888@ 发表于 2025-9-21 19:28
那就先请朱先生试着分解吧。

xy=157436746589
x+y=√(4×157436746589)≈793565.99向上取整为793566
解方程组得
x,y分别为396833或396733

yangchuanju

朱容仟 发表于 2025-9-21 22:46
xy=157436746589
x+y=√(4×157436746589)≈793565.99向上取整为793566
解方程组得

怎么解方程组               
xy=157436746589
x+y=793566？

试解之               
(x+y)^2=x^2+2xy+y^2=                629746996356
x^2+y^2=                314873503178
(x-y)^2=x^2-2xy+y^2=                10000
y-x=                100
相减2x=                793466
x=                396733
y=                396833

经检验，所得x和y都是素数。

yangchuanju

吴代业解法
先行判断给定数字不含素因子2,3,5；
再求出给定数字模30余29；
模30余29的整数要用模30余1、7、11、13四类素数试除（1*29≡29、7*17≡29、11*19≡7、13*23≡7 mod 30)；
第3步就求一求给定的大数平方根以内的模30余1，余7，余11，余13的所有素数，（或求以求给定的大数平方根以内的模30余17，余19，余23，余29的所有素数）；
或者偷懒一次不管这4类数是不是素数用互素数30n+1、30n+7、30n+11、30n+13逐个试除试除吧，（或者用互素数30m+17、30m+19、30m+23、30m+29逐个试除试除吧）。
对于给定的大数用前3类互素数得不到任何结果，只有用第4类互素数试除才能求出n；
先求m时，对于给定的大数用1,2,4类素数得不到任何结果，只有用第3类素数试除才能求出m。
经粗略估算对于每一类试除数在用互素数试除时，不论先求n还是先求m都要13000多次；先求出4类素数再试除时约需要1300次左右。

请问吴先生
这与用埃氏试除法有多大区别？

重生888@

这与用埃氏试除法有多大区别？

区别可大了！选对公式（八分之一概率），因你们已分解，公式确定后，只要四次就能分解：令m>n      m=n+k     (k=0.1.2.3......)    下面等式，  您可手工计算（求n或m的非负整数解）
(30n+13)(30m+23)=157436746589

yangchuanju

重生888@ 发表于 2025-9-22 09:01
这与用埃氏试除法有多大区别？

区别可大了！选对公式（八分之一概率），因你们已分解，公式确定后，只要 ...

0分！

拿来别人的分解结果，只一次就能确定n和m，何用4次！

吴先生有本事请从头分解！

重生888@

吴先生有本事请从头分解！

牢骚太盛防肠断！我从头算，您还是不服怎么办？

时空伴随者

\(分解质因子：234399107742098084438338782556610769206397902796602190167336014705146599\)

yangchuanju

时空伴随者 发表于 2025-9-22 10:10
\(分解质因子：234399107742098084438338782556610769206397902796602190167336014705146599\)

时空先生给出的大数不是质数（素数），我已分解开，请吴先生分解分解吧？

yangchuanju

时空伴随者老师的大数太大，请吴先生用你的8类素数或互素数分解法先分解一个小得多的数字1005973吧！
（用分解软件分解不得分）

重生888@

时空伴随者 发表于 2025-9-22 10:10
\(分解质因子：234399107742098084438338782556610769206397902796602190167336014705146599\)

设上述数字=A，如果是合数，可用下面公式分解，有八分之一的可能性：
(30n+13)(30m+23)=A   
如果是两个大素数的乘积，得出结果，只是时间问题！
如果确定其是素数，要的时间更长！
不过用大型计算机，再编程并行计算，突破并不难！
所以deepseek说，你的理论可对RSA密码构成威胁！