这是一个创建于 2067 天前的主题，其中的信息可能已经有所发展或是发生改变。
W(0)=2
W(i+1)=(W(i)^2)(mod n) //(i>0)
n 是两个大素数的成绩，计算 W(t)
举个例子：
假设 n = 11 * 23 = 253，t = 10
2^(2^1) = 2^2 = 4 (mod 253)
2^(2^2) = 4^2 = 16 (mod 253)
2^(2^3) = 16^2 = 3 (mod 253)
2^(2^4) = 3^2 = 9 (mod 253)
2^(2^5) = 9^2 = 81 (mod 253)
2^(2^6) = 81^2 = 236 (mod 253)
2^(2^7) = 236^2 = 36 (mod 253)
2^(2^8) = 36^2 = 31 (mod 253)
2^(2^9) = 31^2 = 202 (mod 253)
w = 2^(2^t) = 2^(2^10) = 202^2 = 71 (mod 253)
算一下
n = 631446608307288889379935712613129233236329881833084137558899
077270195712892488554730844605575320651361834662884894808866
350036848039658817136198766052189726781016228055747539383830
826175971321892666861177695452639157012069093997368008972127
446466642331918780683055206795125307008202024124623398241073
775370512734449416950118097524189066796385875485631980550727
370990439711973361466670154390536015254337398252457931357531
765364633198906465140213398526580034199190398219284471021246
488745938885358207031808428902320971090703239693491996277899
532332018406452247646396635593736700936921275809208629319872
7008292431243681
t = 79685186856218
原文链接： http://people.csail.mit.edu/rivest/lcs35-puzzle-description.txt
W(i+1)=(W(i)^2)(mod n) //(i>0)
n 是两个大素数的成绩，计算 W(t)
举个例子：
假设 n = 11 * 23 = 253，t = 10
2^(2^1) = 2^2 = 4 (mod 253)
2^(2^2) = 4^2 = 16 (mod 253)
2^(2^3) = 16^2 = 3 (mod 253)
2^(2^4) = 3^2 = 9 (mod 253)
2^(2^5) = 9^2 = 81 (mod 253)
2^(2^6) = 81^2 = 236 (mod 253)
2^(2^7) = 236^2 = 36 (mod 253)
2^(2^8) = 36^2 = 31 (mod 253)
2^(2^9) = 31^2 = 202 (mod 253)
w = 2^(2^t) = 2^(2^10) = 202^2 = 71 (mod 253)
算一下
n = 631446608307288889379935712613129233236329881833084137558899
077270195712892488554730844605575320651361834662884894808866
350036848039658817136198766052189726781016228055747539383830
826175971321892666861177695452639157012069093997368008972127
446466642331918780683055206795125307008202024124623398241073
775370512734449416950118097524189066796385875485631980550727
370990439711973361466670154390536015254337398252457931357531
765364633198906465140213398526580034199190398219284471021246
488745938885358207031808428902320971090703239693491996277899
532332018406452247646396635593736700936921275809208629319872
7008292431243681
t = 79685186856218
原文链接： http://people.csail.mit.edu/rivest/lcs35-puzzle-description.txt
 |
1
jessehzj 2019-05-01 01:09:33 +08:00 via Android
乙
|
|
2
jessehzj 2019-05-01 01:10:36 +08:00 via Android
里面不是说要花 35 年去算么？还考虑了 moore 定律的算力提升
|
 |
3
TusEis 2019-05-01 01:20:46 +08:00
|
 |
4
geelaw 2019-05-01 01:27:29 +08:00
如果你知道 phi(N) 的一个较小的倍数 X （知道 N 的分解则可以知道 phi(N)），则可以用 Euler 定理在 O(log(t)polylog(X)polylog(N)) 的时间内解决。
|
 |
5
siyemiaokube 2019-05-01 10:18:15 +08:00 via iPhone
欧拉降幂
|
 |
6
iwishing OP |
 |
7
ccpp132 2019-05-01 20:55:52 +08:00 via Android
难点是分解 n 吧，和破解 rsa 类似。看位数了，好像 rsa512 已经能分解了？
|
|
8
geelaw 2019-05-01 23:10:30 +08:00
@iwishing #6 我提到是在“可忍受时间”解决问题的方法，然而目前没有人知道如何多项式时间分解一个数，也没有人知道如何在多项式时间得到 phi(N) 的多项式长度的倍数，所以加了前提条件。新闻里面的那位优胜者的做法就是普通的死算，只不过他的硬件是专门为计算平方而设计的，所以（常数上）很快。
|
 |
9
iceheart 2019-05-02 05:06:03 +08:00 via Android
会不会进入某个死循环？
比如 n =15 W[1]=4 W[2]=1 W[3]=1 ... 或者 n=39 W[2]=16 W[3]=22 W[4]=16 ... 完全不懂，我瞎说的 |
 |
10
zealot0630 2019-05-02 06:20:27 +08:00 via Android
@iceheart 会循环，但是循环的长度在 n 的因子附近，就是 2^1024，比 t 大得多。关键字 multiplicative order
|
Select Language