算法与计算机科学chosenplaintext.ca
基数 2^51 技巧
The radix 2^51 trick (2017)
2020 — 2025，它一次次回到首页
黑点是上首页（≥ 50 分）的那次投稿，空心点是没冲上去的投稿，点越大分数越高。
导读
这篇文章讲解 radix 2^51 技巧：把 256 位整数拆成 5 个 51 位的肢体，利用每个肢体上方预留的空间推迟或省去进位处理，从而让大整数乘加和模运算更简单高效。它是密码学高性能实现中的经典表示法，常见于 Curve25519 一类代码；文章也讨论了最高肢体的回绕与位数分配等细节。
为什么经久不衰：它用极小的表示改动把昂贵的进位链移出热点路径，是密码学和大整数运算里简单而持久的优化，因此多年后仍被反复讨论。
HN 评论精选
指出这是进位保存加法器，并说明加宽进位寄存器可批量延迟进位，甚至可用于量子 Shor 算法。
在硬件里这被称为进位保存加法器。一个有趣的性质是：可以把保存进位的寄存器加宽，从而很长时间内不必在字之间做进位。比如用 60 位表示 52 位，就能连续做 256 次加法，直到进位部分饱和再处理。更意外的是，这种构造也能用于量子计算；通常额外寄存器会造成信息泄漏（在量子计算中是错误），但如果把进位填充随机初始化，并在开头从下一个字中减去，使最终求和仍正确，就能让信息泄漏和溢出概率随填充长度指数下降。目前已知最高效的 Shor 算法实现就用了这个技巧。
Strilanc查看英文原文
In hardware this would be called a carry save adder [1]. One interesting fact about carry save adders is that the carry part of the register can be extended in order to avoid any carrying between words for very long periods of time. Instead of using 53 bits to represent 52 bits, use 60 bits, and now you can perform 256 sequential additions with no carrying between words before the carry part saturates and needs to be handled. Somewhat surprisingly, it's even possible to use this construction in the context of a quantum computation [2][3]. The reason it's surprising is because tacking on additional registers like this can act as an information leakage mechanism (which is an error in a quantum computation). For analogy, you can imagine that if you computed a public key using this trick that you would not be comfortable handing an attacker the registers storing your public key before you removed the carry padding that made the computation faster. But it turns out that if you just initialize the carry padding randomly, subtracting out of the next word at the start to ensure everything sums to the correct result at the end, then you can show that the information leakage and chance-of-bad-overflow is exponentially suppressed in the length of the carry padding. Currently the most efficient known way to implement Shor's algorithm uses this technique [4]. 1: https://en.wikipedia.org/wiki/Carry-save_adder 2: https://arxiv.org/abs/1905.08488 3: https://youtu.be/upTipX9yXNg?t=777 4: https://arxiv.org/abs/1905.09749
建议把最高肢体设为 64 位并把省下的位分给其余肢体，从而获得更多进位余量。
如果你允许回绕，你完全可以给最高肢体分配 64 位；这样省下 12 位可以分给其他四个肢体。你可以从 {52,51,51,51,51} 变成 {64,48,48,48,48}，于是有 16 位余量而不是 13 位。
tspiteri查看英文原文
> Aside: Why 13 bits instead of 12? For our purposes, we’re going to ignore the carries in the most significant limb, allowing numbers to wrap when they overflow past 2^256 - 1 (just like how unsigned addition works in C with normal size integer types). As a result, we can assign 52 bits to the most significant limb and ignore the fact that it will run out of room for carries before the other limbs do. If you're going to wrap, you could go all the way and assign 64 bits to the most significant limb; that way you save 12 bits which you can spread to the other four limbs. You can go from {52, 51, 51, 51, 51} to {64, 48, 48, 48, 48}, so you have a spare 16 bits instead of 13 bits.
说明 Poly1305 直接采用该技巧和零填充位，安全界也因此变为 2^106。
Poly1305 的设计正是受这一技巧直接影响，还加上了在 80 位模式的 x87 FPU 上做运算。它甚至刻意放置了一些零填充位来配合该技巧，因此安全界是 2^106 而不是 2^128 或 2^130。
brandmeyer查看英文原文
The design of Poly1305 was directly informed by this very technique, with the addition (heh) of performing the arithmetic on the x87 FPU operating in 80-bit mode. It even has some zero padding bits placed strategically to aid the technique, hence the security bound of 2^106 instead of 2^128 or 2^130. See also https://cr.yp.to/mac/poly1305-20050113.pdf
认为冗余表示可避免进位回溯，并保证流式生成数字时持续前进。
冗余数制是个很棒的话题。我设想一个任意精度算术库，把数表示为从最高位开始的数字流。冗余表示可以避免无界回溯（比如普通表示中在 0.9999... 和 1.0000... 之间来回切换），并能保证生成数字时持续前进。
steerablesafe查看英文原文
Redundant number systems are a really great topic. https://en.wikipedia.org/wiki/Redundant_binary_representation https://en.wikipedia.org/wiki/Carry-save_adder http://lux.dmcs.pl/csII/ca2_RedundantNS.pdf I have an arbitrary precision arithmetic library in my mind that represents numbers as streams of digits starting from the most significant digit. A redundant numeric representation could avoid unbounded backtracking (think flipping between 0.9999... and 1.0000... in a regular representation) and could guarantee forward progress for the generated digits.
历次讨论
同类还值得读
位运算技巧集
Bit Twiddling Hacks
斯坦福页面上的经典位运算技巧合集，收录了 popcount、前导/尾随零、位反转、交换、舍入等大量技巧，并附有解释和性能讨论。
算法与计算机科学上首页 8 次 · 2011–2024graphics.stanford.edu编辑精选如何不按平均评分排序
How Not To Sort By Average Rating
经典文章解释了为什么按平均评分排序不可靠：只有少量评价的条目（比如仅一条五星）会轻易排到最前，而评价数量的差异被忽略。
算法与计算机科学上首页 7 次 · 2009–2024evanmiller.org编辑精选数据结构可视化
Data Structure Visualizations
旧金山大学 David Galles 教授制作的数据结构与算法交互式可视化网站，涵盖 B 树、红黑树、排序、图算法等，可逐步操作观察其运行过程。
算法与计算机科学上首页 6 次 · 2011–2021cs.usfca.edu编辑精选1996 年以来的计算机科学最佳论文奖
Best Paper Awards in Computer Science since 1996
Jeff Huang 维护的一个汇总页面，收录了自 1996 年以来计算机科学各主要会议的“最佳论文奖”获奖名单，并按年份和会议整理，方便读者一站式浏览历届获奖论文。
算法与计算机科学上首页 6 次 · 2010–2018jeffhuang.com编辑精选算法（Jeff Erickson）
Algorithms, by Jeff Erickson
伊利诺伊大学 Jeff Erickson 教授的算法课教材，免费在线开放。
算法与计算机科学上首页 5 次 · 2018–2022jeffe.cs.illinois.edu编辑精选