V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
iwishing
V2EX  ›  程序员

知道 V2 能人多,问个 MIT 算法题

  •  
  •   iwishing ·
    941zturn · 2019-05-01 00:37:56 +08:00 · 2946 次点击
    这是一个创建于 1794 天前的主题,其中的信息可能已经有所发展或是发生改变。
    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
    10 条回复    2019-05-02 06:20:27 +08:00
    jessehzj
        1
    jessehzj  
       2019-05-01 01:09:33 +08:00 via Android
    jessehzj
        2
    jessehzj  
       2019-05-01 01:10:36 +08:00 via Android
    里面不是说要花 35 年去算么?还考虑了 moore 定律的算力提升
    TusEis
        3
    TusEis  
       2019-05-01 01:20:46 +08:00
    geelaw
        4
    geelaw  
       2019-05-01 01:27:29 +08:00
    如果你知道 phi(N) 的一个较小的倍数 X (知道 N 的分解则可以知道 phi(N)),则可以用 Euler 定理在 O(log(t)polylog(X)polylog(N)) 的时间内解决。
    siyemiaokube
        5
    siyemiaokube  
       2019-05-01 10:18:15 +08:00 via iPhone
    欧拉降幂
    iwishing
        6
    iwishing  
    OP
       2019-05-01 12:01:05 +08:00
    @TusEis 是的,人家一个业余的程序员算出结果来了,所以才想来问问

    @geelaw 你的意思就是先去算 n 的因子,有啥方法么?
    ccpp132
        7
    ccpp132  
       2019-05-01 20:55:52 +08:00 via Android
    难点是分解 n 吧,和破解 rsa 类似。看位数了,好像 rsa512 已经能分解了?
    geelaw
        8
    geelaw  
       2019-05-01 23:10:30 +08:00
    @iwishing #6 我提到是在“可忍受时间”解决问题的方法,然而目前没有人知道如何多项式时间分解一个数,也没有人知道如何在多项式时间得到 phi(N) 的多项式长度的倍数,所以加了前提条件。新闻里面的那位优胜者的做法就是普通的死算,只不过他的硬件是专门为计算平方而设计的,所以(常数上)很快。
    iceheart
        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
    ...
    完全不懂,我瞎说的
    zealot0630
        10
    zealot0630  
       2019-05-02 06:20:27 +08:00 via Android
    @iceheart 会循环,但是循环的长度在 n 的因子附近,就是 2^1024,比 t 大得多。关键字 multiplicative order
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1646 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 104ms · UTC 16:48 · PVG 00:48 · LAX 09:48 · JFK 12:48
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.