，然后选择$ t $来设置所需的难题难度。 $ t $连续的
平方为模$ n $，以值$ 2 $开始。也就是说，设置
$ W（0）= 2 $，
$ W（i + 1）= W（i）^ 2 \ pmod n \ quad $为$ i \ ge0 $，
并计算$ W（t）$。
没有已知的方法可以更快速地执行此计算，而无需知道$ n $的因式分解。 。
1999年，他们预测到现在我们将拥有10 GHz处理器。我意识到原始GHz是一种测量速度的愚蠢方法，但是用于这种“本质上顺序”计算的计算机速度有多快？
我想我的问题是：
1）不能并行化的最新计算技术是什么？
2）有谁声称在这一挑战方面取得了任何进展？
#1 楼
2）有没有人声称在挑战方面取得了进展？
我可以回答的那个问题...
我发现了解决方案于2019年4月15日发送给麻省理工学院的CSAIL，并于4月16日发送给麻省理工学院的CSAIL。另一个团队应在5月11日或12日之前得到答案（他们使用了FPGA）。
我在2015年底注意到，如果使用GMP，我可以在Core i7上找到答案。 6700 CPU大约需要三年半时间。所以我基本上让我的电脑全天候24/7打开，以便解决“难题”。
秘密信息和两个素数应在5月15日举行的“时间胶囊”开幕式上宣布。
链接到CSAIL的有关它：
程序员解决了麻省理工学院长达20年的密码难题
评论
$ \ begingroup $
恭喜你。您可以在不破坏聚会的情况下为解决方案提供任何小提示吗？
$ \ endgroup $
–Paul Uszak
19年4月30日在0:12
$ \ begingroup $
欢迎使用crypto.stackexchange-我不得不说，很高兴看到解决方案的工作原理概述。如果可以的话，请考虑将其编辑为答案。
$ \ endgroup $
–艾拉·罗斯（Ella Rose）
19年4月30日在0:30
$ \ begingroup $
@nealmcb我想可以通过将其发送给MIT来实现。
$ \ endgroup $
–森林
19年5月1日，0：24
$ \ begingroup $
@nealmcb：麻省理工学院的CSAIL和罗恩·里维斯特公开证实我是第一个找到解决方案的人，但是……在此之前的四天，Antpool比特币矿池确实将个性化的区块头放入了比特币区块＃573 138中，恭喜解决LCS35的方法：）因此，从技术上讲，Antpool是第一个宣布解决LCS35的方法。尚无证据：解决方案将于5月15日公布。
$ \ endgroup $
– TacticalCoder
19年5月1日在18:41
$ \ begingroup $
@nealmcb：是的，它比tx更好：正如您所注意到的，它在块本身中，这真是太神奇了，因为它需要找到一个块，如今只有采矿池才能为比特币做这件事（非常感谢的蚂蚁矿池的家伙们就此永垂不朽）。我不知道这些非ASCII字节：我也注意到了，但是还没有检查...也许是汉字？
$ \ endgroup $
– TacticalCoder
19年5月4日在21:17
#2 楼
该难题现已解决！该解决方案于2019年5月宣布。它由Bernard Fabrot解决，他使用了现代优化的大整数乘法实现来加快计算速度，并在大约1秒钟内完成计算。 3.5年的计算，而不是35年。大约在同一时间，经过大约2个月的计算，使用FPGA的第二个团队报告说距离解决方案数周。恭喜他们俩。
在介绍这一思想的研究论文中对这一理论进行了解释：发布加密货币。 Ronald L. Rivest，Adi Shamir和David A.Wagner。麻省理工学院计算机科学实验室，技术备忘录MIT / LCS / TR-684（1996）（修订3/10/96）。
Rivest对时间胶囊的描述引用了该论文。 >
正如该论文中的安全性分析所解释的那样，尚无使用并行性（包括多核计算机）的方法来在很大程度上加快重复平方处理的已知方法。并行性帮助的唯一已知方法是为每个单独的平方运算提供适度的加速。多核计算机也许能够比单核计算机更快地计算模块化平方运算，但是以这种方式可用的整体加速是有限的。例如，这是该论文的引文：
重复平方似乎是一个“本质上是顺序的”过程。
我们知道没有明显的方法可以将其并行化为任何形式。很大程度。 （在每个平方中可能有少量的
并行化。）拥有多台计算机并不比拥有一台计算机好。 （但是拥有一台速度快的计算机要优于一台速度慢的计算机。）解决难题的时间长短的变化程度取决于单台计算机的速度变化，而不是一个人的总预算。由于硬件的速度
对于个人消费者而言，这是大型情报组织所能使用的很小的常数，因此解决方案的时间差异是可以合理控制的。
据我所知，这仍然是对现有技术的准确描述。
评论
$ \ begingroup $
对于在家中具有复杂性理论的人来说，“本质上是顺序的”〜P-complete。内在假设是在NC中没有P中存在问题。这似乎有可能，但尚未得到证实。
$ \ endgroup $
–pg1989
13年8月8日在6:30
$ \ begingroup $
$ w $（或这里所说的$ W（t）$）是否已在线发布？时间囊应该现在打开，对吗？
$ \ endgroup $
– Henno Brandsma
19年5月26日在22:51
#3 楼
除非$ 2 ^ t $在$ \ mathbb Z_n $组中的顺序为$ 2 $，在这种情况下解决方案是微不足道的。除非知道$ n $的因数，否则可以使用中文余数定理。
除非$ n $（或其因数）具有特殊形式，仅设置了一些稀疏位（例如$ n = 2 ^ a + 2 ^ b + 1 $）和类似情况，其中$ n $在其二进制扩展中只有$ 1 $ s和$ 0 $ s之间有一些交替，在这种情况下，可能有快速的归约方法。
n $是$ 2 $减去$ 1 $的幂，而$ t = n-1 $是Great Internet Mersenne Prime Search，在这里您可以找到“快速”专用软件的最新技术水平。
量子计算？摘自en.wikipedia.org/wiki/Shor's_algorithm：“在2012年，重复进行了15的因式分解。[7]同样在2012年，实现了21的因式分解，创下了用量子计算机分解的最大数的记录“ ....” Shor算法的运行时瓶颈是量子模幂。仍然很慢，而且对于大数仍然不切实际...
我不知道有任何证据表明无法针对$ t $和$ n $的常规值解决此问题，重复平方的相关步骤是唯一的解决方案。
毕竟，在正常情况下，平方可以被循环移位代替。看看http://en.wikipedia.org/wiki/Normal_basis。
评论
$ \ begingroup $
如果知道$ n $的因素，则您甚至不需要CRT。您有足够的信息来减少$ 2 ^ t〜\ text {mod}〜\ varphi {（n）} $并有效地解决难题。
$ \ endgroup $
–托马斯
13年1月10日，下午3:58
$ \ begingroup $
@Pierre，与此同时，Rivest的科学论文对此做了很多介绍。 （在该组中，$ 2 ^ t $是$ 2 $的可能性很小。整个要点的一部分是，选择$ n $使得它很难被分解，并且它的因子未知。所以上。）
$ \ endgroup $
– D.W.
13年1月10日在6:34
#4 楼
令人惊讶的是，按照https://www.cryptophage.com所述，@ TacticalCoder于5月10日获得答案后几周就解决了这个难题。由于他们使用针对此任务进行了优化的FPGA硬件，因此他们的解决方案在2个月而不是近4年的时间内起作用。 。真是让每个人震惊！那天他们还发布了其解决方案的SHA-256哈希值：
1310966a15298e756b1d2533a9316eb2e2a582a492841a71f15a04a264ce2ae6
评论
Tacticalcoder的答案值得加分。@kelalaka这就是我开始赏金的答案。 ：P