数学中国

用户名  找回密码
 注册
帖子
热搜: 活动 交友 discuz
楼主: ysr

[原创]RSA公钥密码的破解

[复制链接]
 楼主| 发表于 2020-1-13 08:57 | 显示全部楼层
当然这个法只能用来判断是否是素数,不能用来分解因数,要分解n,还要用到其他方法。
回复 支持 反对

使用道具 举报

 楼主| 发表于 2020-1-13 15:32 | 显示全部楼层
RSA密码的原理和方法的逆命题,可以用来判断一大数是否是素数,如:6958000001674999998647是两个11位的素数的积,经判断为合数。而2^89-1=618970019642690137449562111,经判断是素数有27位。
回复 支持 反对

使用道具 举报

 楼主| 发表于 2020-1-13 20:26 | 显示全部楼层
这个判断比常规法快的多。
回复 支持 反对

使用道具 举报

 楼主| 发表于 2020-1-13 22:43 | 显示全部楼层
45367929763334872117245196642377832066594422737383这是素数有50位,
8548077248145782626619300287299705673980083387922967这是素数有52位,
3535000647287053716310161223639238642910682574781777736223167这是合数有61位
回复 支持 反对

使用道具 举报

 楼主| 发表于 2020-1-17 14:00 | 显示全部楼层
本帖最后由 ysr 于 2022-12-8 13:00 编辑

经过实验,大于5位的整数的判断是正确的,小于5可能前面的原理就失效了,因为我们用的明文已经是3位的,(小于3位的是否能用是否还准确,不知道有待研究),用小于3位的如7,11,13,97等做公开模数,来判断的话,还原不出3位的明文,因为明文是余数,小于3位的模数(或者说是除数),余数不能是3位的,所以原理失效,(还原不出来明文就被判定为合数,而实际这几个例子(7,11,13,97)都是素数,所以此时输出结果错误)而大于5位的都成立!5位以下的用常规法已经可以快速分解和判断了,所以这个法对于大整数的判断还是有效的,有价值的。(经过验证大于11位的有效,判断是准确的,小于11位的就是10位以内的用常规法)
回复 支持 反对

使用道具 举报

 楼主| 发表于 2020-1-18 00:15 | 显示全部楼层
999999999977779这是素数有15位,这个判断素数速度比较快,挺好玩的程序。
23这是一个质数
233这是一个质数
2333这是一个质数
23333这是素数有5位
233333=353*661
2333333=19*227*541
23333333=17*1372549
233333333=29*47*193*887
2333333333=10163*229591
23333333333这是素数有11位
233333333333是合数
2333333333333是合数
23333333333333是合数
233333333333333是合数
2333333333333333是合数
23333333333333333这是素数有17位
233333333333333333是合数。(18位)
23333333333333333333333这是素数有23位。
23333333333333333333333333333333333333333333333333333是合数有53位。
233333333333333333333333333333333333333333333333333333这是素数有54位。
回复 支持 反对

使用道具 举报

 楼主| 发表于 2020-1-20 22:20 | 显示全部楼层
下图中是我的程序对22位的整数的分解,用常规法很费力的,此法道是快速方便,若是用到快速乘法除法程序则更快,能分解的整数就更大。
对22位的整数用费马分解法等方法也可以分解但步骤和计算量太大,必须用大整数的快速乘法除法才能出结果,这个方法则计算量稍小一些。
只是咱不会快速乘法除法,效率低,再大一些的就慢了,超过1个小时甚至是无法分解。而且只能分解成两个因子,是不完全分解法。

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?注册

x
回复 支持 反对

使用道具 举报

 楼主| 发表于 2020-1-20 22:25 | 显示全部楼层
对这个22位的整数的分解程序运行了几秒钟时间,图片中显示了中间数据,当程序运行调试好以后就不必显示中间数据了。
回复 支持 反对

使用道具 举报

 楼主| 发表于 2020-1-30 09:52 | 显示全部楼层
19748381714759701=99368963*198737927,这是两个关联素数的积,很容易分解的。
回复 支持 反对

使用道具 举报

 楼主| 发表于 2020-2-1 05:40 | 显示全部楼层
本帖最后由 ysr 于 2020-1-31 21:44 编辑

56楼及58楼的例子中的p小于实际,B=B*η,其中η<1,F越小η越接近1,而当p大于实际呢?B=B*η,此时η>1,F越小越接近1,方程变为:(p-F)(2B+1)F=qF+r,整理得:
-(2B+1)F^2+((2B+1)p-q)F-r=0.
η对每个F的值是不一样的,实际可以估计个值,理论上η要精确到点后的位数等于p的位数,实际我们采用点后3或5位即可。如η=0.618或η=1.618,这时F的值就会很大的,实际验证F的值不用很大,因为当B的整数部分等于实际的时候,p的值的最高位有至少2位是等于实际,的,所以,η的值要实际验证后确定,要让大多数的整数能够分解了,F值越接近实际试除的越少越能快速分解,所以η要选择适当的值。
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

本版积分规则

LaTEX预览输入 教程 符号库 加行内标签 加行间标签 
对应的 LaTEX 效果:

Archiver|手机版|小黑屋|数学中国 ( 京ICP备05040119号 )

GMT+8, 2025-7-23 05:31 , Processed in 0.106003 second(s), 14 queries .

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表
\frac{\square}{\square}\sqrt{\square}\square_{\baguet}^{\baguet}\overarc{\square}\ \dot{\baguet}\left(\square\right)\binom{\square}{\square}\begin{cases}\square\\\square\end{cases}\ \begin{bmatrix}\square&\square\\\square&\square\end{bmatrix}\to\Rightarrow\mapsto\alpha\ \theta\ \pi\times\div\pm\because\angle\ \infty
\frac{\square}{\square}\sqrt{\square}\sqrt[\baguet]{\square}\square_{\baguet}\square^{\baguet}\square_{\baguet}^{\baguet}\sum_{\baguet}^{\baguet}\prod_{\baguet}^{\baguet}\coprod_{\baguet}^{\baguet}\int_{\baguet}^{\baguet}\lim_{\baguet}\lim_{\baguet}^{\baguet}\bigcup_{\baguet}^{\baguet}\bigcap_{\baguet}^{\baguet}\bigwedge_{\baguet}^{\baguet}\bigvee_{\baguet}^{\baguet}
\underline{\square}\overline{\square}\overrightarrow{\square}\overleftarrow{\square}\overleftrightarrow{\square}\underrightarrow{\square}\underleftarrow{\square}\underleftrightarrow{\square}\dot{\baguet}\hat{\baguet}\vec{\baguet}\tilde{\baguet}
\left(\square\right)\left[\square\right]\left\{\square\right\}\left|\square\right|\left\langle\square\right\rangle\left\lVert\square\right\rVert\left\lfloor\square\right\rfloor\left\lceil\square\right\rceil\binom{\square}{\square}\boxed{\square}
\begin{cases}\square\\\square\end{cases}\begin{matrix}\square&\square\\\square&\square\end{matrix}\begin{pmatrix}\square&\square\\\square&\square\end{pmatrix}\begin{bmatrix}\square&\square\\\square&\square\end{bmatrix}\begin{Bmatrix}\square&\square\\\square&\square\end{Bmatrix}\begin{vmatrix}\square&\square\\\square&\square\end{vmatrix}\begin{Vmatrix}\square&\square\\\square&\square\end{Vmatrix}\begin{array}{l|l}\square&\square\\\hline\square&\square\end{array}
\to\gets\leftrightarrow\nearrow\searrow\downarrow\uparrow\updownarrow\swarrow\nwarrow\Leftarrow\Rightarrow\Leftrightarrow\rightharpoonup\rightharpoondown\impliedby\implies\Longleftrightarrow\leftharpoonup\leftharpoondown\longleftarrow\longrightarrow\longleftrightarrow\Uparrow\Downarrow\Updownarrow\hookleftarrow\hookrightarrow\mapsto
\alpha\beta\gamma\Gamma\delta\Delta\epsilon\varepsilon\zeta\eta\theta\Theta\iota\kappa\varkappa\lambda\Lambda\mu\nu\xi\Xi\pi\Pi\varpi\rho\varrho\sigma\Sigma\tau\upsilon\Upsilon\phi\Phi\varphi\chi\psi\Psi\omega\Omega\digamma\vartheta\varsigma\mathbb{C}\mathbb{H}\mathbb{N}\mathbb{P}\mathbb{Q}\mathbb{R}\mathbb{Z}\Re\Im\aleph\partial\nabla
\times\cdot\ast\div\pm\mp\circ\backslash\oplus\ominus\otimes\odot\bullet\varnothing\neq\equiv\not\equiv\sim\approx\simeq\cong\geq\leq\ll\gg\succ\prec\in\ni\cup\cap\subset\supset\not\subset\not\supset\notin\not\ni\subseteq\supseteq\nsubseteq\nsupseteq\sqsubset\sqsupset\sqsubseteq\sqsupseteq\sqcap\sqcup\wedge\vee\neg\forall\exists\nexists\uplus\bigsqcup\bigodot\bigotimes\bigoplus\biguplus\bigcap\bigcup\bigvee\bigwedge
\because\therefore\angle\parallel\perp\top\nparallel\measuredangle\sphericalangle\diamond\diamondsuit\doteq\propto\infty\bowtie\square\smile\frown\bigtriangledown\triangle\triangleleft\triangleright\bigcirc \wr\amalg\models\preceq\mid\nmid\vdash\dashv\nless\ngtr\ldots\cdots\vdots\ddots\surd\ell\flat\sharp\natural\wp\clubsuit\heartsuit\spadesuit\oint\lfloor\rfloor\lceil\rceil\lbrace\rbrace\lbrack\rbrack\vert\hbar\aleph\dagger\ddagger

MathQuill输入:

Latex代码输入: