数学研发论坛

 找回密码
 欢迎注册
查看: 218|回复: 10

[讨论] 攻打数字巨人RSA-232

[复制链接]
发表于 2019-4-14 12:47:44 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

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

x
本帖最后由 kte 于 2019-4-14 13:27 编辑

RSA-232=1009881397871923546909564894309468582818233821955573955141120516205831021338
          5285453743661097571543636649133800849170651699217015247332943892702802343809
          6090980497644054071120196541074755382494867277137407501157718230539834060616
          2079

这是一个8k+7的数,是RSA中未被分解的最小的一个数。


已知在前100个数中,它是素数{3, 5, 11, 13, 17, 19, 31, 53, 61, 67, 71, 73, 79, 89}的二次剩余。



IntegerPart[Sqrt[RSA-232]]=31778631151639045179686388493300715963579687858851199671688113190565970121132383850648339145606653258464904492282993




不知此数还有哪些性质
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-4-14 13:12:03 | 显示全部楼层
https://en.wikipedia.org/wiki/RSA_numbers#RSA-232

这辈子能看到这个整数的分解
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-4-14 13:17:22 | 显示全部楼层
我只会穷举法
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-4-14 13:26:30 | 显示全部楼层
你怎么知道是二次剩余的呢?雅克比符号可不能那么玩,
即使等于1,也不表示是剩余
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2019-4-14 13:30:25 | 显示全部楼层
mathematica 发表于 2019-4-14 13:26
你怎么知道是二次剩余的呢?雅克比符号可不能那么玩,
即使等于1,也不表示是剩余

x^2=RSA-232  (Mod p)  有解

点评

但理论上我们总可以通过暴力枚举来得到一些类似x^2=a (Mod RSA-232)的等式啊——我还以为你说的是暴力枚举的事情呢。  发表于 2019-4-15 07:55
kte
不能保证x^2=3 (Mod RSA-232)有解,如果有解,3对它的两个因子 d1,d2必须 都有解  发表于 2019-4-14 15:21
……想错了……算二次剩余的话,直接Jacobi符号不就好了……为啥还要特地说一句呢?  发表于 2019-4-14 14:58
按你的说法,【它是素数{3, 5, 11, 13, 17, 19, 31, 53, 61, 67, 71, 73, 79, 89}的二次剩余。】这句话应该改成【素数{3, 5, 11, 13, 17, 19, 31, 53, 61, 67, 71, 73, 79, 89}是它的二次剩余。】吧……  发表于 2019-4-14 14:57
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-4-14 13:35:31 | 显示全部楼层
kte 发表于 2019-4-14 13:30
x^2=RSA-232  (Mod p)  有解

我理解错了,我以为是这些小素数是RSA-232的剩余
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2019-4-14 14:02:54 | 显示全部楼层
本帖最后由 kte 于 2019-4-14 14:20 编辑
  1. Clear[t, a]; d = RSA-232; pell = -1; P[0] = 0; Q[0] = 1;
  2. t[0] = (P[0] + Sqrt[d])/Q[0]
  3. a[0] = IntegerPart[t[0]];
  4. i = 0; While[(t[i] != 1/(t[0] - a[0]) && P[i] != pell) || i == 1,
  5. P[i + 1] = Q[i] a[i] - P[i];
  6. Q[i + 1] = (d - P[i + 1]^2)/Q[i];
  7. t[i + 1] = (P[i + 1] + Sqrt[d])/Q[i + 1];
  8. a[i + 1] = IntegerPart[t[i + 1]];
  9. If[Q[i + 1] == Q[i] || P[i + 1] == P[i], Break[]];
  10. Print[{i, Q[i], P[i], a[i]}] i++];
  11. {i, Q[i], P[i], a[i]}
  12. {i + 1, Q[i + 1], P[i + 1], a[i + 1]}
复制代码



这是整数平方根的连分式PQa展开算法,只不过计算到完整循环节的一半,就是代码中的Break[]函数,现在要将以上while循环转换成for循环,要求小于给定值,比如大于200时结束循环,并且将Q[  i  ]  和 P[  i  ]分别写入两个表中

代码如何修改
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2019-4-26 00:47 , Processed in 0.063002 second(s), 17 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表