- 在线时间
- 7 小时
- 最后登录
- 2024-8-19
- 注册时间
- 2023-11-2
- 听众数
- 3
- 收听数
- 0
- 能力
- 0 分
- 体力
- 58 点
- 威望
- 0 点
- 阅读权限
- 20
- 积分
- 23
- 相册
- 0
- 日志
- 0
- 记录
- 0
- 帖子
- 12
- 主题
- 6
- 精华
- 0
- 分享
- 0
- 好友
- 0
升级   18.95% TA的每日心情 | 郁闷 2023-12-11 09:00 |
|---|
签到天数: 7 天 [LV.3]偶尔看看II
 |
二次剩余值的关联计算(上)7 [; l- D4 p: _: B4 F; O
+ Q9 ]) K( V; U c 一、 二次剩余中\frac{1}{2} 相关值的计算:
4 ^( |) Q8 {: `0 L1 w7 @ 对于完全平方公式:. j4 T0 Y7 X$ {
(1/2 -m)^2 = 1/4 -m+m^2 = 1/4 +m(m-1) (m≥1) (1-1)" ?* | ]5 U, r) W2 ?+ T9 j) e
! Q! c. v8 L9 {! d8 w- L2 V) x 在n为奇数时, 上式的同余可以分为:
3 a/ f3 [' i) E# N \9 Q9 Z* O1 X% T ① 当n=4k-1时,对(1-1)求同余得:
( J# e" W ]# V (1/2-m)^2 ≡ (2k-m)^2 ≡ k+m(m-1) (mod n) (1-2)
" l, \- j+ Q2 H ② 当n=4k+1时, 对(1-1)求同余得:
( b5 O3 [6 l: m, C: }# T (1/2 -m)^2 ≡ (2k+1-m)^2 ≡ -k+m(m-1) ≡ n-k+m(m-1) (mod n) (1-3)
2 F& O w) o$ Q; g
2 u5 \0 A2 S Q 为以后叙述方便,我们对 1/2-1 1/2-2 ... 1/2-m (m >=1) 这类数称为二次剩余的后序序列, 即1/2 减小的方向的数列.0 e! [2 J- E, y
8 o2 Q& T s' J& F 二次剩余后序序列的二次剩余值有个特点, 与k(k>0)值相关, 是k值与两个连续整数积的和,与k值同奇同偶。
+ H5 Q8 p- m4 B4 u0 Y2 D$ f4 o 如n=299=4*75-1 k=75 2k=150 , 二次剩余后序序列为:
( |& T- p% c8 n o3 I. f! @+ A( Y (150-1)^2 ≡ 75+1*(1-1) ≡ 75 +0 ≡ 75 (mod 299) => 149^2 ≡ 75 (mod 299) - b' [$ B4 m* u, N! C% l
(150-2)^2 ≡ 75+2*(2-1) ≡ 75 +2 ≡ 77 (mod 299) => 148^2 ≡ 77 (mod 299) 7 v4 b# l1 l) \; O2 t/ R# F
(150-3)^2 ≡ 75+3*(3-1) ≡ 75 +6 ≡ 81 (mod 299) => 147^2 ≡ 81 (mod 299)
2 m0 E- R% t0 v/ R N7 r6 @! U( T6 X4 {2 {2 U! T
.
v$ N: }3 V' e0 C .0 u& [& F& ]6 j0 Y, [9 j S
根据后序序列,可以得到一个分解整数的方法:
X4 H. P# ~; F5 Z0 `+ L 设n为奇合数, 如果 c^2-k=m(m-1) m>0 => (2k-m)^2 ≡ c^2 (mod n) , 或者
* E5 h' \6 R0 a8 l; v c^2-k=m(m-1) => 4c^2-4k+1=4m(m-1)+1 => (2c)^2 ≡ (2m-1)^2 (mod n) 2 q( y4 G6 e. \& M* r/ C" f
上述等式,由费马分解即可得到n的因子, 不过效率较低. ]2 W( ~2 s& u! k
例1: n=299-4*75-1 , k=75' I. [* H4 E! v0 N
根据后序序列,大于75且与75同奇同偶的完全平方:9^2-81
$ s; ^" c) C0 b7 Z( a 81-75=6=2*3 为连续两个整数积,在后序序列上
* {& K' k1 a$ P% I ∴ (150-3)^2≡81 (mod 299) => 147^2≡81 (mod 299)# e, h; |: \+ U7 z. H3 U% R! Y/ i
或者 (2*9)^2≡(2*2+1)^2 (mod 299) => 18^2≡5^2(mod 299)
% n( z1 R$ O, r5 Y* r+ [/ M2 d" d- N9 d8 S! |2 e% W: f; z8 ~' ?
二、连续两个整数积的分解方法
+ t8 k. r8 v1 Q 1、分解方法介绍. S; i8 {' F) z6 J9 T( B
例2: n=299=4*75-1
9 f+ k4 N% I+ P( l/ I4 v8 F" ~ 25^2 ≡ 27 (mod 299) => . m H/ H, Y2 o; U( E- S
25^2 ≡ 25+2 (mod 299) =>
# \' H# i5 p) P4 c. t9 |2 D 25^2-25-2 ≡ 0 (mod 299) => " k9 J1 }. W0 a- X
(25-2)(25+1) ≡ 0 (mod 299) => 7 d! M& C) {# N/ u- ^
23*26 ≡ 0 (mod 299) ! o% _" q$ n* C
(23,299)=23 (26,299)=13 299=13*23* R, t+ Y# ?9 h
5 @- f, q$ i) ]' }2 j3 k# X
分解方法: 设n为奇合数, a^2 ≡ b (mod n) , 如果 b=a+i(i+1) (i ≥ 0 ) , 则可得到:3 i* t# @! J2 b; p. Q
a^2 ≡ b (mod n) => 9 L5 o2 {3 v- D
a^2-b-i(i+1) ≡ 0 (mod n) =>
6 o( V1 B$ E1 _ (a-(i+1))(a+i) ≡ 0 (mod n)
" k W% R' Z% h) e$ p3 C4 w* [2 p3 E (a-(i+1),n)>1 (a+i , n)>1 即可分解n) w1 K: I9 ]; H5 E1 G, W! @- C
; u8 k1 M+ `0 w, c, ?& K
2、分解方法的另一个解释
, X; P' i4 o, p$ F% D6 C6 h 设n为奇数, a^2 ≡ b(mod n), 如果m=a, 则由(1-1)公式得: ' [- a! y0 D2 w- u/ W2 t
(1/2 -a)^2 ≡ 1/4 +a^2-a (mod n) => $ x4 F. C$ C! |" K. ]8 n
(1/2 -a)^2 ≡ 1/4 +b-a (mod n) (2-1) 4 T7 j6 f; d0 J/ d% h; T+ \
7 F6 T! q+ s( Z4 L! ~/ R+ h7 p
① n=4k-1 , 2-1式得:
. W" I6 ^) C$ G) d: s$ H (2k-a)^2 ≡ k+b-a(mod n) (2-2)
% {- _1 Z! ?% L0 s) k8 j ① n=4k+1 , 2-1式得:! t: A9 O# F9 |0 k8 K$ m3 |# M. z
(2k+1-a)^2 ≡ n-k+b-a (mod n) (2-3)
+ W% y' D& g/ I8 @/ f$ F2 P5 W
4 Y# _7 V: d4 B/ O, i0 G! s. s 从(2-1(式, 可知二次剩余的计算, 在[1,1/4]范围内, 计算出[1,n-1]的二次剩余值.
! o8 W7 b% |5 O( V" r0 Y 在例2中, 按(2-2)式的计算, 可得:
+ }$ }6 h0 H* L$ X8 ^1 M- z (150-25)^2 ≡ 75+27-25 (mod 299) => 125^2 ≡ 77 (mod 299) % p: N& T! f' s3 ?, R% [
所以, a^2 ≡ b (mod n) ,如果b=a+i(i+1) ,其相对1/2的剩余值在后序序列上.
0 h! ?' J/ Q5 D
( r, D0 ~- f6 r 三、1/j (j >=3)的计算方法 7 j% R) r, B& P
上面的是计算 1/2, 即j=2, 如果j>2时, 有如下的1/j计算方法:
3 R! K1 v& @. C7 I (1/j ± ij)^2 = (ij)^2 ± 2i + (1/j)^2 (i >= 1 ) (j ≥3) (3-1)
d4 [9 J* Y- H7 `* S, b
% p* V) \5 L* K$ K5 O0 L- s) A 而对于\frac{1}{j}相邻, 有两种计算,
# z( m& B* a6 S' u; W: {% B( z$ q 1) 1/j 1+1/j 2+1/j ... t+1/j (t<j) ) k! k1 v# ^$ o3 i# k- v6 B& G
2) t-1/j ... 1-1/j 1/j 1+1/j ... t+1/j (t < j/2)
2 k2 n ~6 }* y9 Y* T1 a8 a4 R/ y8 \ t+1/j= (1+tj)/j = m/j , m=1+tj5 j* p8 P2 z$ m4 y
/ I. g$ {1 b0 z, }! S
按m/j , (3-1)式变成: . ^ W+ }6 l) [$ X( k! O9 P
(m/j± ij )^2 = (ij)^2 ± 2mi + (m/j )^2 (i≥ 1 ) (j ≥ 3) (3-2)5 Z: V$ G" F* n" ~4 W4 r- a+ D- w1 W
" z& A- ? K; r- x0 ]6 v+ n$ F 例3: n=299 \frac{1}{3} ≡ 100 (mod 299) 100^2 ≡ 133 (mod 299) 0 H* R B6 o. Q6 x
(100-3)^2 ≡ 3^2-2+133 (mod 299) => 97^2 ≡ 140 (mod 299)
6 H3 E v+ C d* s# ]4 u* }! @ (100+3)^2 ≡ 3^2+2+133 (mod 299) => 103^2 ≡ 144 (mod 299)
! b( j. R1 ]2 ~ 1+1/3=4/3 ≡ 1+100=101 (mod 299) 101^2 ≡ 35 (mod 299)& I! g1 a U5 F+ G+ b3 d% p
(101-3)^2 ≡ 3^2-2*4+35 (mod 299) => 98^2 ≡ 36 (mod 299) 0 q7 I* K( s$ \1 B
(101+3)^2 ≡ 3^2+2*4+35 (mod 299) => 104^2 ≡ 52 (mod 299) " T9 X' E7 S9 c: G4 S6 Y
1-1/3=-2/3 ≡ 1-100=-99 (mod 299) 99^2 ≡ 233 (mod 299)
, J& m% P( e1 a+ C( ], @) I! z (99-3)^2 ≡ 3^2-2*(-2)+233 (mod 299) => 96^2 ≡ 246 (mod 299) ; y+ } ~* Z- D5 Q6 m1 y' _
(101+3)^2 ≡ 3^2+2*(-2)+233 (mod 299) => 102^2 ≡ 238 (mod 299) ! a* ]' |; f2 c9 T
按2+1/3也能得到相同结果,这里不在验证.) M! N. s2 g" L/ s# V1 R
+ y7 e7 g' G Z/ ]* T5 P% Y( E3 E
当然如果j=2s, 即为偶数, 可以计算一半的值, (3-2)式得 : 7 B# N Z1 }- k4 w+ f
(m/j ± i*s)^2=(is)^2±mi+(m/j)^2 (i ≥ 1) (j ≥ 3) (3-3)
. R5 J7 J! t8 H2 j4 f& t- d 更一般的公式: 当为 g/j g <j/2 , (g, j)=1, 这里就不再给出." f3 l0 q; V5 ~
! k9 ^6 ^# H4 D( m" p* @ |
zan
|