二次剩余值的关联计算(上)
二次剩余值的关联计算(上)一、 二次剩余中\frac{1}{2} 相关值的计算：
对于完全平方公式：
(1/2 -m)^2 = 1/4 -m+m^2 = 1/4 +m(m-1) (m≥1) (1-1)
在n为奇数时, 上式的同余可以分为:
① 当n=4k-1时，对(1-1)求同余得:
(1/2-m)^2 ≡ (2k-m)^2 ≡ k+m(m-1) (mod n) (1-2)
② 当n=4k+1时, 对(1-1)求同余得:
(1/2 -m)^2 ≡ (2k+1-m)^2 ≡ -k+m(m-1) ≡ n-k+m(m-1) (mod n) (1-3)
为以后叙述方便，我们对 1/2-1 1/2-2 ... 1/2-m (m >=1) 这类数称为二次剩余的后序序列, 即1/2 减小的方向的数列.
二次剩余后序序列的二次剩余值有个特点, 与k(k>0)值相关, 是k值与两个连续整数积的和，与k值同奇同偶。
如n=299=4*75-1 k=75 2k=150 , 二次剩余后序序列为:
(150-1)^2 ≡ 75+1*(1-1) ≡ 75 +0 ≡ 75 (mod 299) => 149^2 ≡ 75 (mod 299)
(150-2)^2 ≡ 75+2*(2-1) ≡ 75 +2 ≡ 77 (mod 299) => 148^2 ≡ 77 (mod 299)
(150-3)^2 ≡ 75+3*(3-1) ≡ 75 +6 ≡ 81 (mod 299) => 147^2 ≡ 81 (mod 299)
.
.
根据后序序列，可以得到一个分解整数的方法:
设n为奇合数, 如果 c^2-k=m(m-1) m>0 => (2k-m)^2 ≡ c^2 (mod n) , 或者
c^2-k=m(m-1) => 4c^2-4k+1=4m(m-1)+1 => (2c)^2 ≡ (2m-1)^2 (mod n)
上述等式，由费马分解即可得到n的因子, 不过效率较低.
例1: n=299-4*75-1 , k=75
根据后序序列，大于75且与75同奇同偶的完全平方：9^2-81
81-75=6=2*3 为连续两个整数积，在后序序列上
∴ (150-3)^2≡81 (mod 299) => 147^2≡81 (mod 299)
或者 (2*9)^2≡(2*2+1)^2 (mod 299) => 18^2≡5^2(mod 299)
二、连续两个整数积的分解方法
1、分解方法介绍
例2: n=299=4*75-1
25^2 ≡ 27 (mod 299) =>
25^2 ≡ 25+2 (mod 299) =>
25^2-25-2 ≡ 0 (mod 299) =>
(25-2)(25+1) ≡ 0 (mod 299) =>
23*26 ≡ 0 (mod 299)
(23,299)=23 (26,299)=13 299=13*23
分解方法: 设n为奇合数, a^2 ≡ b (mod n) , 如果 b=a+i(i+1) (i ≥ 0 ) , 则可得到:
a^2 ≡ b (mod n) =>
a^2-b-i(i+1) ≡ 0 (mod n) =>
(a-(i+1))(a+i) ≡ 0 (mod n)
(a-(i+1),n)>1 (a+i , n)>1 即可分解n
2、分解方法的另一个解释
设n为奇数, a^2 ≡ b(mod n), 如果m=a, 则由(1-1)公式得:
(1/2 -a)^2 ≡ 1/4 +a^2-a (mod n) =>
(1/2 -a)^2 ≡ 1/4 +b-a (mod n) (2-1)
① n=4k-1 , 2-1式得：
(2k-a)^2 ≡ k+b-a(mod n) (2-2)
① n=4k+1 , 2-1式得：
(2k+1-a)^2 ≡ n-k+b-a (mod n) (2-3)
从(2-1(式, 可知二次剩余的计算, 在范围内, 计算出的二次剩余值.
在例2中, 按(2-2)式的计算, 可得:
(150-25)^2 ≡ 75+27-25 (mod 299) => 125^2 ≡ 77 (mod 299)
所以, a^2 ≡ b (mod n) ，如果b=a+i(i+1) ,其相对1/2的剩余值在后序序列上.
三、1/j (j >=3)的计算方法
上面的是计算 1/2， 即j=2, 如果j>2时, 有如下的1/j计算方法:
(1/j ± ij)^2 = (ij)^2 ± 2i + (1/j)^2 (i >= 1 ) (j ≥3) (3-1)
而对于\frac{1}{j}相邻, 有两种计算,
1) 1/j 1+1/j 2+1/j ... t+1/j (t<j)
2) t-1/j ... 1-1/j 1/j 1+1/j ... t+1/j (t < j/2)
t+1/j= (1+tj)/j = m/j , m=1+tj
按m/j , (3-1)式变成:
(m/j± ij )^2 = (ij)^2 ± 2mi + (m/j )^2 (i≥ 1 ) (j ≥ 3) (3-2)
例3: n=299 \frac{1}{3} ≡ 100 (mod 299) 100^2 ≡ 133 (mod 299)
(100-3)^2 ≡ 3^2-2+133 (mod 299) => 97^2 ≡ 140 (mod 299)
(100+3)^2 ≡ 3^2+2+133 (mod 299) => 103^2 ≡ 144 (mod 299)
1+1/3=4/3 ≡ 1+100=101 (mod 299) 101^2 ≡ 35 (mod 299)
(101-3)^2 ≡ 3^2-2*4+35 (mod 299) => 98^2 ≡ 36 (mod 299)
(101+3)^2 ≡ 3^2+2*4+35 (mod 299) => 104^2 ≡ 52 (mod 299)
1-1/3=-2/3 ≡ 1-100=-99 (mod 299) 99^2 ≡ 233 (mod 299)
(99-3)^2 ≡ 3^2-2*(-2)+233 (mod 299) => 96^2 ≡ 246 (mod 299)
(101+3)^2 ≡ 3^2+2*(-2)+233 (mod 299) => 102^2 ≡ 238 (mod 299)
按2+1/3也能得到相同结果，这里不在验证.
当然如果j=2s, 即为偶数, 可以计算一半的值, (3-2)式得 :
(m/j ± i*s)^2=(is)^2±mi+(m/j)^2 (i ≥ 1) (j ≥ 3) (3-3)
更一般的公式: 当为 g/j g <j/2 , (g, j)=1, 这里就不再给出.
页:
[1]