二次剩余
定义
一个数
对二次剩余求解,也就是对常数
通俗一些,可以认为是求模意义下的 开平方 运算。对于更高次方的开方的简单讨论,可以参见离散对数一文。
这里只讨论
Legendre 符号
通过 Legendre 符号可以判断一个数
下表为部分 Legendre 符号的值
特殊情况时的算法
对于同余方程
那么
Atkin 算法
过程
仍然考虑上述同余方程,此时
证明
其中
那么
得证。
Cipolla 算法
定义
Cipolla 算法用于求解同余方程
过程
算法可描述为找到
在复数域
后文考虑对于系数属于有限域
选择
若
证明
令
又因为二项式定理
可以发现只有当
所以
若
所以
Bostan–Mori 算法
该算法基于 Cipolla 算法,我们将问题转换为 常系数齐次线性递推 再应用 Bostan–Mori 算法。考虑另一种常见的 Cipolla 算法的描述为
且
而
Legendre 算法
定义
对于同余方程
证明
考虑选择一个
存在环态射
那么
所以
Tonelli–Shanks 算法
定义
Tonelli–Shanks 算法是基于离散对数求解同余方程
令
证明
而
所以
若
所以
剩下的问题是如何计算
因为
正确性显然。
习题
外部链接
参考文献
Daniel. J. Bernstein. Faster Square Roots in Annoying Finite Fields. ↩
S. Müller, On the computation of square roots in finite fields, Design, Codes and Cryptography, Vol.31, pp. 301-312, 2004 ↩
A. Menezes, P. van Oorschot and S. Vanstone. Handbook of Applied Cryptography, 1996. ↩
Alin Bostan, Ryuhei Mori.A Simple and Fast Algorithm for Computing the N-th Term of a Linearly Recurrent Sequence. ↩
本页面最近更新:2023/5/27 22:46:55,更新历史
发现错误?想一起完善? 在 GitHub 上编辑此页!
本页面贡献者:hly1204, ShaoChenHeng, Chrogeek, Enter-tainer, Great-designer, iamtwz, monkeysui, nanmenyangde, sshwy, StudyingFather, TachikakaMin, Tiphereth-A, Xeonacid, xyf007
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用