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
|