- 在线时间
- 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
 |
二次剩余值的关联计算(上)
1 t9 `( t6 D1 P7 i& E- e C4 x1 R2 y1 g8 U% @8 J1 X
一、 二次剩余中\frac{1}{2} 相关值的计算:
: N) c8 v+ P8 O4 N; f; H, x6 v; |) j 对于完全平方公式:
8 E& z/ i- x8 @" Z/ f) ` (1/2 -m)^2 = 1/4 -m+m^2 = 1/4 +m(m-1) (m≥1) (1-1)
* {5 u9 u3 ^5 v9 _& u3 f' k1 p% U8 k6 J: q$ I$ G' B- _
在n为奇数时, 上式的同余可以分为:
6 p) }* I4 r8 B& Q6 d# y ① 当n=4k-1时,对(1-1)求同余得: 4 {2 C+ \# X C% V( C/ k# @0 h; C
(1/2-m)^2 ≡ (2k-m)^2 ≡ k+m(m-1) (mod n) (1-2)& i5 O7 V! r; R, r( j) O0 F
② 当n=4k+1时, 对(1-1)求同余得:
7 C: c. g2 o. w" i! W/ q (1/2 -m)^2 ≡ (2k+1-m)^2 ≡ -k+m(m-1) ≡ n-k+m(m-1) (mod n) (1-3)
" t5 x5 r1 p7 X8 n, X
2 F1 s+ S5 G5 D" [ }+ {2 e6 D 为以后叙述方便,我们对 1/2-1 1/2-2 ... 1/2-m (m >=1) 这类数称为二次剩余的后序序列, 即1/2 减小的方向的数列.
: M: ~+ w8 S( V; N" \7 h, E+ K2 M) s8 f1 w
二次剩余后序序列的二次剩余值有个特点, 与k(k>0)值相关, 是k值与两个连续整数积的和,与k值同奇同偶。 G1 M; K5 M" k. |* n% Z& v$ F4 Z
如n=299=4*75-1 k=75 2k=150 , 二次剩余后序序列为:
# F( N( ~8 E% J& ~ (150-1)^2 ≡ 75+1*(1-1) ≡ 75 +0 ≡ 75 (mod 299) => 149^2 ≡ 75 (mod 299)
: v9 }; }% R- ~1 g$ C& \! c (150-2)^2 ≡ 75+2*(2-1) ≡ 75 +2 ≡ 77 (mod 299) => 148^2 ≡ 77 (mod 299) 5 y' D C' v# K3 p& R
(150-3)^2 ≡ 75+3*(3-1) ≡ 75 +6 ≡ 81 (mod 299) => 147^2 ≡ 81 (mod 299) 3 L2 _* y, r- L F
1 T, [6 t( g: q6 N
.
( [$ B/ @: V L9 i .
' V" { c7 g7 ^0 X- r6 O {2 T 根据后序序列,可以得到一个分解整数的方法:
" n8 f( N/ l% Y 设n为奇合数, 如果 c^2-k=m(m-1) m>0 => (2k-m)^2 ≡ c^2 (mod n) , 或者 2 |, g6 e4 R/ D( [3 O6 i
c^2-k=m(m-1) => 4c^2-4k+1=4m(m-1)+1 => (2c)^2 ≡ (2m-1)^2 (mod n) ) H9 e& g7 i1 Z1 D
上述等式,由费马分解即可得到n的因子, 不过效率较低.
$ ?: u1 `% [0 A' c7 Q" ~ 例1: n=299-4*75-1 , k=756 U) z% s" d k+ B6 k
根据后序序列,大于75且与75同奇同偶的完全平方:9^2-81
) P; B" P9 N' K- S6 J 81-75=6=2*3 为连续两个整数积,在后序序列上# X' ?& H+ n8 q6 Z1 C: ]) B
∴ (150-3)^2≡81 (mod 299) => 147^2≡81 (mod 299)* I+ B, W3 x1 r# [# ]
或者 (2*9)^2≡(2*2+1)^2 (mod 299) => 18^2≡5^2(mod 299)
& Y: `8 d7 u4 S/ ?/ U( l
6 b! ?8 x e5 L 二、连续两个整数积的分解方法
! t$ \. J6 f, ]0 x* ^ 1、分解方法介绍' d3 S4 P! q+ I4 D' n
例2: n=299=4*75-1, `" \5 \: [) m' b- W/ Q, K) D( K
25^2 ≡ 27 (mod 299) =>
" N e0 ~6 ]8 T# m" a; N 25^2 ≡ 25+2 (mod 299) =>
2 W0 B' _( g% H% \& O7 r9 S- v9 O 25^2-25-2 ≡ 0 (mod 299) => % J7 |* O- v7 n
(25-2)(25+1) ≡ 0 (mod 299) =>
7 N' b! r1 q; F6 g S0 {6 n' T 23*26 ≡ 0 (mod 299)
: @6 _) a4 C, X0 p+ r% [, O (23,299)=23 (26,299)=13 299=13*23# P* n& w% H1 t
2 j: M9 c* W/ o2 V0 G
分解方法: 设n为奇合数, a^2 ≡ b (mod n) , 如果 b=a+i(i+1) (i ≥ 0 ) , 则可得到:
/ L [& b+ D6 m, B3 N a^2 ≡ b (mod n) => ' L' g# [2 J8 j$ @% g& W# ?
a^2-b-i(i+1) ≡ 0 (mod n) =>
/ A7 D7 V. K5 F3 ^4 b& C4 \: p (a-(i+1))(a+i) ≡ 0 (mod n)
u- I- X2 o4 @% v) Q (a-(i+1),n)>1 (a+i , n)>1 即可分解n/ _! J/ W9 |3 [* R- X. Y u
6 L! ^0 X/ t h# f
2、分解方法的另一个解释 7 r! K, o9 O2 s. N
设n为奇数, a^2 ≡ b(mod n), 如果m=a, 则由(1-1)公式得: t) @1 B$ e7 r8 I0 K' Z. ~4 R# ?% q
(1/2 -a)^2 ≡ 1/4 +a^2-a (mod n) =>
; {$ {4 H( |" [6 I' U (1/2 -a)^2 ≡ 1/4 +b-a (mod n) (2-1)
~: |1 j; J2 v# z
9 s, T; E5 c/ {: P) z, E- { ① n=4k-1 , 2-1式得:
0 }6 A# r* J2 `" g7 X8 L (2k-a)^2 ≡ k+b-a(mod n) (2-2)
! r! L" G- n9 y) ? ① n=4k+1 , 2-1式得:
% F# l) R( ^; M9 C% z4 X (2k+1-a)^2 ≡ n-k+b-a (mod n) (2-3)
0 d' n6 B1 w% k. `0 _( }
- z t) ]6 M% k9 V 从(2-1(式, 可知二次剩余的计算, 在[1,1/4]范围内, 计算出[1,n-1]的二次剩余值.
1 J" ^4 G: F3 _% J8 H. b 在例2中, 按(2-2)式的计算, 可得:
) e0 F% l3 H$ o' I (150-25)^2 ≡ 75+27-25 (mod 299) => 125^2 ≡ 77 (mod 299) 6 g& O/ f( W9 }6 I P5 d: K
所以, a^2 ≡ b (mod n) ,如果b=a+i(i+1) ,其相对1/2的剩余值在后序序列上.4 g1 ?5 u9 ?% N- c0 o; ?& T: I5 W! p
/ m3 a; E# F" c; T0 ]+ p% e0 z
三、1/j (j >=3)的计算方法
: K1 _# ]- H0 u$ m 上面的是计算 1/2, 即j=2, 如果j>2时, 有如下的1/j计算方法:
+ A \! A+ y7 s. D3 v$ L. p (1/j ± ij)^2 = (ij)^2 ± 2i + (1/j)^2 (i >= 1 ) (j ≥3) (3-1)
4 ?( p$ I% A7 |$ d$ J A2 ]$ z5 A. h; C3 i# l
而对于\frac{1}{j}相邻, 有两种计算, : F$ K- e2 i9 p4 @ K: S: H
1) 1/j 1+1/j 2+1/j ... t+1/j (t<j)
1 D" K/ p3 ?) Y 2) t-1/j ... 1-1/j 1/j 1+1/j ... t+1/j (t < j/2) ; v' x1 n- I% _3 B, {
t+1/j= (1+tj)/j = m/j , m=1+tj
5 k. y+ `0 q/ }( N5 q. E ~% P
. _) k, g" c4 M n3 y8 f! o 按m/j , (3-1)式变成: ' F6 }) B# i4 x$ S& l/ Y: c
(m/j± ij )^2 = (ij)^2 ± 2mi + (m/j )^2 (i≥ 1 ) (j ≥ 3) (3-2)8 R1 F& E2 }. f# b
: x: g3 O" I- A, z: u: u- K6 h) q, ~ 例3: n=299 \frac{1}{3} ≡ 100 (mod 299) 100^2 ≡ 133 (mod 299)
. m5 E5 g5 z0 C4 c. ?- g (100-3)^2 ≡ 3^2-2+133 (mod 299) => 97^2 ≡ 140 (mod 299)
8 z& C4 m- g1 r3 ] (100+3)^2 ≡ 3^2+2+133 (mod 299) => 103^2 ≡ 144 (mod 299)
- M3 V( L6 @9 w: A& P1 H 1+1/3=4/3 ≡ 1+100=101 (mod 299) 101^2 ≡ 35 (mod 299)
8 i$ p' T. K6 o c; _ (101-3)^2 ≡ 3^2-2*4+35 (mod 299) => 98^2 ≡ 36 (mod 299)
1 o' K& l4 n- K0 l/ B, |) | (101+3)^2 ≡ 3^2+2*4+35 (mod 299) => 104^2 ≡ 52 (mod 299)
, U* p r: s3 O 1-1/3=-2/3 ≡ 1-100=-99 (mod 299) 99^2 ≡ 233 (mod 299) 0 K, o- I5 M" v% I1 g$ w) v
(99-3)^2 ≡ 3^2-2*(-2)+233 (mod 299) => 96^2 ≡ 246 (mod 299) , [ p: h) ~) Q' k; y# Y
(101+3)^2 ≡ 3^2+2*(-2)+233 (mod 299) => 102^2 ≡ 238 (mod 299) 7 \+ w3 i! ^) {2 q
按2+1/3也能得到相同结果,这里不在验证.
+ ^( K* w0 c: w) J/ w7 A! g Y# q* ? f5 G
当然如果j=2s, 即为偶数, 可以计算一半的值, (3-2)式得 :
& @, h8 m7 G- I6 a' o3 J (m/j ± i*s)^2=(is)^2±mi+(m/j)^2 (i ≥ 1) (j ≥ 3) (3-3)
6 K/ d3 M" [' Q: R5 Y5 K* ~/ w 更一般的公式: 当为 g/j g <j/2 , (g, j)=1, 这里就不再给出.
1 j! c1 v* |2 M2 B4 q. G9 a8 K1 f) t0 r, U0 R1 T9 ^
|
zan
|