二次剩余Cipolla算法 【转载a_crazy_czy】

2019-04-14 18:39发布

站内文章 / 模拟电子
17446 0 1317

大佬博客传送门

首先我们要弄清楚什么叫二次剩余，其实就是对于给定的p(p∈P)和n，如果有x满足x2≡n(modp)，那么n在模p意义下就是二次剩余。说白了就是模意义下能否开根号。 
我们只讨论p为奇素数的情况。 
我们先定义Fp，这是一个数域，其实就是0到p−1这p个数与模p意义下加减乘除运算构成的集合。
  • 定理1：对于x2≡n(modp)，总共有p−12个的n能使该方程有解（将n=0情况除去，由于该情况显然有x=0）。
  • 证明：我们只用考虑所有x2。如果存在不同的两个数u、v，它们的平方在模p意义下同余，那么显然有p

热门文章