-
-
[原创]整数分解随笔(六)
-
发表于:
2017-5-26 19:44
5975
-
整数分解随笔(六)
本次文中未注明处,n≥3,且为奇数。
一、平方剩余相邻两数除法的唯一性及互逆间的相互相关性:
1、相邻两数除法的唯一性
在随笔word版中,曾经推出相邻两数平方剩余除法的一个公式,这里把公式重新整理一下。
设a^2≡b(mod n),根据公式可知:
c≡(a-1)/(b-1) (mod n) =>
c^2≡d,(c+1)^2≡bd (mod n)
即根据a^2≡b(mod n)可以反推出该平方剩余是由哪两个相邻数相除得到,其中a、b、c∈(1,n-1),而且是唯一的。
以下证明唯一性:
设a^2≡b(mod n),(c+1)/c≡a(mod n),如果不唯一,即还存在另外一个相邻数的平方剩余(d+1)/d≡a(mod n),可得:
(c+1)/c≡(d+1)/d (mod n) =>
c≡d (mod n)
这里a、b、c、d∈[1,n-1]
即平方剩余的除法具有唯一性。
现在再对相邻两数平方剩余的除法进行相应的变化。
设a^2≡b(mod n),(a+1)^2≡c(mod n),两式相除得:
((a+1)/a)^2≡c/b(mod n) =>
(1+1/a)^2≡j(mod n) 这里j≡c/b(mod n)
如果两式相乘得:
(a^2+a)^2≡bc(mod n) =>
(a+b)^2≡bc(mod n)
又∵j≡c/b(mod n)
∴上式变为:(a+b)^2≡jb^2(mod n) =>
(1+a/b)^2≡j(mod n)
当然也可以由a^2≡b(mod n) =>
a/b≡1/a(mod n),其中(a,n)=1
得到上面两式是相等的。
举例说明三个公式:
例1、60^2≡12(mod 299)
a≡(60-1)/(12-1)≡59/11≡250(mod 299)
250^2≡9(mod 299)
251^2≡108(mod 299)
其中 9*12≡108(mod 299)
1+1/a≡60(mod 299) =>
a≡1/59(mod 299) =>
a≡223(mod 299)
223^2≡95(mod 299)
224^2≡243(mod 299)
其中 95*12≡243(mod 299)
1+a/b≡60(mod 299) =>
[招生]科锐逆向工程师培训(2024年11月15日实地,远程教学同时开班, 第51期)