动机
BCH 构造需要一个具有指定乘法阶的元素。密码学构造则关心某个指数是否仍然难以恢复。这是两类不同的计算问题。找到合适的单位根可能很容易,而在它所在的循环群中恢复指数却可能代价高得多。
我们先构造所需的单位根,再用两种一般方法求解离散对数。小步大步算法以存储空间换取平方根量级的搜索。素数幂数位恢复则利用群的阶的分解,把任务拆成若干较小的对数问题。二者合在一起说明:起决定作用的是阶及其素因子,而不仅仅是域的大小。
这里给出的是算法与上界,而不是密码学困难性的证明。一个对阶的二进制长度呈指数级的算法,并不能推翻多项式时间困难性假设;反过来,域很大本身也不能确立该假设。我们的计算使用前面各单元已经验证过的域的表示。
定义
设 是含 个元素的域,其乘法群是大小为 的循环群。固定整除 的 ,并假定已给出 的素因子分解。对于带有显式长度为 的码字的编码应用,通过试除获得该分解的代价对 是多项式的;我们并不声称对任意数的分解在 下具有多项式代价。
定义 14.3.1
(阶与离散对数)
若 且没有更小的正整数幂等于 ,则称元素 的阶为 。它的各次幂构成子群 。对 ,其离散对数是满足 的唯一剩余类 。零不是乘法群中的元素。
对于阶为 的元素 , 的阶是 :方程 等价于 ,其最小正解就是该商。我们使用精确的域乘法、求逆与取幂,并用规范的系数列表编码来比较元素。
定理/命题
定理 14.3.2
(构造所要求阶的单位根)
给定 的素因子分解以及有理数 ,可以在精确域运算下,以至少 的概率找到阶恰为 的元素,否则报告失败;所用时间关于 、 以及 的编码长度是多项式的。每个返回的元素都经过确定性验证。该过程既不要求分解 ,也不要求求解离散对数。
定理 14.3.3
(小步大步算法)
给定已知阶为 的元素 与非零目标 ,可以判定 是否属于 ,并在属于时用 次群运算与 个存储元素恢复其对数。确定性的表排序与查找另外需要 次编码比较。
定理 14.3.4
(素数幂数位恢复)
若 已经分解,则对每个因子求解阶为 的群中的 个对数,再用中国剩余定理合并答案,即可恢复对数。若这些小对数用小步大步算法求解,则群运算的代价为
此外还有表比较以及已给定的整数/域运算。分解本身的代价被明确排除在外。
证明思路或证明
把均匀元素投影到目标子群
证明
(投影、精确的阶检验与固定的失败预算)
映射 从 出发,其像是唯一的阶为 的子群。为看出这一点,把元素写成该循环群某个抽象生成元的幂。指数乘以 后,恰好得到模 的 的所有倍数,每个值有 个原像。因此,均匀的非零域元素被映到该子群中的均匀元素,尽管算法并不知道那个抽象生成元。
候选元素 的阶恰为 ,当且仅当 ,且对 的每个素因子 都有 。若其阶是 的真因子,则商的某个素因子会使其中一个检验失败。投影已经保证了第一个条件,但再验证一次也无妨。
由幂的阶公式,阶为 的循环群中有 个生成元。对素数作容斥原理,得 。把不同素数按递增顺序排列,有 ,故该乘积至少为 。由于 ,对 ,它至少为 。
取整数 使 ,并尝试 个相互独立的投影候选。在理想的均匀非零抽样下,全部失败的概率至多为 。返回第一个通过精确阶检验的候选。
为实现非零抽样,用 个公平比特生成整数标号,并接受 到 之间的标号。把被接受的标号解释为以 为基的系数列表,这是到非零域元素的双射。每次尝试成功的概率至少为 。把每次抽样限制在 次尝试之内,其中 。在相同比特上与不设上限的抽样耦合,可知任何上限改变搜索结果的概率至多为 。总失败概率至多为 ,且所有预算都是固定的多项式量。标号只用于抽样,绝不替代域运算。
阶检验必须在 的每个素因子处进行;只做一个检验是不够的。
反例模式
只检验一个素因子会接受错误的阶
断言:若 ,且对 的最大素因子 有 ,则 的阶为 。取 、,其最大素因子为三,并取 。则
该候选通过了在三处的检验,但其阶是三而不是六;在二处的检验会发现这一点。修正后的命题就是上面所用的: 的阶为 ,当且仅当 ,且对 的每个素因子 都有 。
让一个小步与一个大步相匹配
证明
(碰撞搜索及其代价)
成员判定首先有一个简单而精确的检验: 当且仅当 。该子群已经包含 的 个不同的根,域上的根数界不允许再有其他根。零以及任何未通过成员检验的元素都应被拒绝。
令 。对 存储小步 。对 计算大步 ,直到某个值与已存值相等。一次碰撞给出 ,于是返回模 约化后的该指数并加以验证。
由于 ,每个指数 都有分解 ,其中 。因此对有效目标必然发生碰撞。相邻的小步用乘以 得到;相邻的大步用乘以 得到,所以次数为 。负幂使用域中的逆元,而不是离散对数的计算。对规范编码排序并作二分查找,即得所述的确定性比较代价与存储界。
群运算的次数并不是全部的比特代价。用 个素域系数表示的元素占用 比特,所以除了下标之外,小步表占用 比特。前面的算术算法使每次群运算的比特代价关于 是多项式的。比较两个规范系数列表的最坏代价也与其长度成正比。
对这些列表排序仅仅是为精确编码建立索引;它并没有在元素上赋予与域相容的数值序。编码标号可以按字典序比较,尽管域本身并不是有序域。哈希表实现可以给出不同的期望查找界,但需要自己的数据结构假设。上述确定性的排序加搜索估计避免了对该期望的依赖。最后,由于 可能超过 ,匹配的指数可能大于 。将其模 约化既不改变群中的值,也不改变唯一的对数剩余类,而最后的等式检验使返回的答案可以直接验证。
该表把对 个指数的穷举搜索改进为约 次群运算。若 约为 ,这仍然约为 次运算,对比特参数是指数级的:算法提供的是上界,并没有相应的困难性定理。
由低位到高位恢复素数幂的数位
证明
(数位归纳与中国剩余定理的合并)
对因子 ,投影到 与 。 的阶为 ,未知指数是 。令 ,其阶为 。
假设前 个数位已给出 ,用 到 之间的代表表示。写 。则
更高的数位消失了,因为它们的指数是 的倍数。求解这个阶为 的对数,令 ,并重复直到 。以 起步即完成归纳,并恢复整个素数幂剩余类。
模数 两两互素。令 ,并由 Bézout 选取 使 。则 具有所有已恢复的剩余。两个解之差是每个互素的 的倍数,因而是它们乘积 的倍数,由此证明唯一性。
每个数位使用普通取幂,需 次群运算,外加一次阶为 的小步大步搜索。依次处理各素数幂可以复用存储。因此,即使阶很大,只要它只含小素因子,其对数就可能很容易求得。该定理并不假设分解总能被高效找到。
证明透视
哪个指数消去哪些数位
三个假设分别在不同地方起作用。投影 用到 的阶恰为 :只有这样, 的阶才恰为 , 的阶才恰为 。若真正的阶较小, 可能等于一,每个数位看起来都会是零。
关键的一步是两边同时消去。乘以 去掉已知的数位;取 次幂则把未知的高位部分 变成 的倍数而消失,当前数位则以 的形式保留。由于 而 的阶为 ,这个小对数唯一确定 ,所以从 开始的归纳在 步后完成。模 的唯一性则来自中国剩余定理一步中各 两两互素,而不是来自数位恢复本身。
例题详解
例题 14.3.5
(十六元域中的五元单位根子群)
在 中,元素 的阶为十五:仅有的素因子检验是 与 ,二者都由不可约四次关系得出。因此 的阶为五。它的五个幂是 的互不相同的根,适用于长度为五的循环构造。
随机化投影可以从任意均匀的非零元素出发,不必是这个已知的本原元。立方把十五个元素均匀地映到那个五元子群上,每个输出有三个原像。该五个元素中有四个是生成元,所以一次投影试验成功的概率为 。
例题 14.3.6
(一次小步大步碰撞)
在模二十三下, 的阶为十一。设 ,。小步为 。大步乘子的逆为 。第一个大步值是十三,不在表中;下一个是 ,与小步指数三匹配。故 ,且 验证了结果。该表并不需要整数四模十一的逆;它用的是 的群逆元。
例题 14.3.7
(光滑阶对数的四个二进制数位)
在模十七下,由于 , 的阶为十六。取 ,。在 时,,所以第一个数位为一,。在 时,余项为 ,其四次方为十六;下一个数位为一,。
在 时,余项为 ,其平方为一,得数位零。在 时,余项仍为十六,不需要再取幂,得数位一。因此 。直接相乘得 。每个小对数只有两种可能;由于阶是二的幂,不需要对大阶作搜索。
概念视角结构
对数是到剩余类的同构
由于 的阶为 ,映射 , 是群同构,而离散对数正是它的逆:它把 中的乘法变成剩余类的加法。数位恢复就是通过中国剩余定理来看这个同构。在 之下,取 次幂把 映到其 阶子群上,并把 映到 ,而后者恰好记录 。因此成本界由最大的素数 主导。
常见错误
常见错误
(满足 的元素不一定阶为 )
单位元对每个 都满足该方程。因此,投影到阶为 的子群后,必须先通过生成元检验,其输出才能充当所要求的元素。在 处的检验排除了每一个真阶,而不是仅仅检验某个方便的指数。
常见错误
(高效的构造不是困难性的证明)
已验证的域或本原元都不能证明某个密码学假设。离散对数求解器在熟知的容易方向上给出共享密钥求解器与判定检验,但困难性的逆命题需要另行论证。这里的算法只展示了在所选群上假设可能失效的特定方式;它们并不证明能抵抗这些特定方法的群就是安全的。
总结
投影与经验证的阶检验,可以在显式有界的失败预算下构造循环码所需的单位根。小步大步算法以平方根量级的存储与群运算恢复子群中的任意对数。阶已分解的群允许进行素数幂数位恢复与中国剩余定理合并,这凸显了小因子的重要性,同时明确保留了关于分解的假设。
练习
快速检查
(为什么只靠 次幂投影而不作最后的阶检验是不够的?)
想一想投影后的元素可能落在哪些子群中。
解答 · 答案
投影落在正确的子群中,但也可能落在某个真子群中,包括其单位元。这些检验排除了 的所有真因子,从而保证了得到各坐标幂互不相同所需的精确阶。
快速检查
(为什么 刻画了由阶为 的域元素生成的子群的成员资格?)
数一数该子群中已有多少个 的根。
解答 · 答案
该子群包含 的 个不同的根。域上的 次多项式不会有更多的根。因此非零成员检验恰好识别出这些幂。
快速检查
(在数位恢复中,为什么所选的指数能消去未知的更高数位?)
追踪未知余项的指数被 的多少次幂整除。
解答
未知余项的指数可被 整除。乘以 后,它可被 整除,而 正是投影后的生成元的阶。当前数位则作为阶为 的元素 的幂保留下来。
快速检查
(为什么素数幂算法并不证明存在分解任意群的阶的多项式时间算法?)
检查算法接收的输入是什么。
解答
它的素数幂分解在一开始就已给定。高效地利用已知的分解并不等于计算这个分解。试除对显式的编码长度 是多项式的,但对密码学复杂度中使用的二进制长度 可能是指数级的。
快速检查
(投影后的对数给出 与 。求 。)
用 与 代入中国剩余定理公式。
解答
中国剩余定理公式使用 与 。得 。直接验证,七模三余一、模五余二,并且这些剩余唯一确定它模十五的值。