- 在线时间
- 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
 |
二次剩余值的关联计算(上)9 V# F: }" y2 I
( G5 ] X3 Q7 a6 N% b. c
一、 二次剩余中\frac{1}{2} 相关值的计算:! c. D% c' l% C& g
对于完全平方公式:
$ z) G( h5 O; `( s# D (1/2 -m)^2 = 1/4 -m+m^2 = 1/4 +m(m-1) (m≥1) (1-1)1 M% h4 t& h, v
4 }) O2 r- a( ]" J; o% ~$ I. D
在n为奇数时, 上式的同余可以分为:
0 i6 L; a! E, C ① 当n=4k-1时,对(1-1)求同余得:
; ^. {6 n+ S, w. I4 d (1/2-m)^2 ≡ (2k-m)^2 ≡ k+m(m-1) (mod n) (1-2)0 u% Q& X6 `6 [1 m" I
② 当n=4k+1时, 对(1-1)求同余得:
& ]. ~2 {+ H0 _5 D6 Y, I; W5 ~ (1/2 -m)^2 ≡ (2k+1-m)^2 ≡ -k+m(m-1) ≡ n-k+m(m-1) (mod n) (1-3)
$ a2 F3 I" Q$ M2 l, r; k g8 C& z$ z2 i6 {% U6 i/ M& z& H8 {0 V& u
为以后叙述方便,我们对 1/2-1 1/2-2 ... 1/2-m (m >=1) 这类数称为二次剩余的后序序列, 即1/2 减小的方向的数列.: D4 M7 Z4 P1 n" W. ~8 _1 @
Z6 p+ v. L0 N+ ~ 二次剩余后序序列的二次剩余值有个特点, 与k(k>0)值相关, 是k值与两个连续整数积的和,与k值同奇同偶。8 i: X- v1 j& k: @/ [! N6 Y- \( t! i
如n=299=4*75-1 k=75 2k=150 , 二次剩余后序序列为:
/ y! {# {7 b+ M1 f5 Y& J" q" W1 s+ C7 X (150-1)^2 ≡ 75+1*(1-1) ≡ 75 +0 ≡ 75 (mod 299) => 149^2 ≡ 75 (mod 299)
: i+ M3 E5 V8 i' P, B( { (150-2)^2 ≡ 75+2*(2-1) ≡ 75 +2 ≡ 77 (mod 299) => 148^2 ≡ 77 (mod 299) . L8 L1 ~, `# F7 J
(150-3)^2 ≡ 75+3*(3-1) ≡ 75 +6 ≡ 81 (mod 299) => 147^2 ≡ 81 (mod 299)
6 K. S( i- `! ~" i8 p" k
9 O- P( _ U- ?) M$ ?# p .
6 Z; b' B" x [5 l .
% \4 }- G: S$ P: T$ r1 r 根据后序序列,可以得到一个分解整数的方法:
( B* z5 |7 m& A' k 设n为奇合数, 如果 c^2-k=m(m-1) m>0 => (2k-m)^2 ≡ c^2 (mod n) , 或者
) x0 q. E2 X: ]0 B6 k- d- x. L c^2-k=m(m-1) => 4c^2-4k+1=4m(m-1)+1 => (2c)^2 ≡ (2m-1)^2 (mod n)
# A2 s, ^8 Z, Z; h5 H+ \+ D1 Y 上述等式,由费马分解即可得到n的因子, 不过效率较低.8 y" p9 P8 a# e# ]" }3 C6 w- `
例1: n=299-4*75-1 , k=75
) ]( H" b9 Z8 Z: p y) B3 x 根据后序序列,大于75且与75同奇同偶的完全平方:9^2-81
- c7 E9 A6 h2 X 81-75=6=2*3 为连续两个整数积,在后序序列上
7 D5 A% @- y+ N) p ∴ (150-3)^2≡81 (mod 299) => 147^2≡81 (mod 299)
* G* C) @ s9 W 或者 (2*9)^2≡(2*2+1)^2 (mod 299) => 18^2≡5^2(mod 299)
# C7 i' X L( T, u3 f+ A
6 \, O, {6 {$ P/ j- E8 F 二、连续两个整数积的分解方法
, q/ U: M8 b. `/ q4 d 1、分解方法介绍; @; ~7 l, G0 t9 M$ \8 j; c5 {( C* A
例2: n=299=4*75-10 I. U4 L6 E6 b( X: `( x @
25^2 ≡ 27 (mod 299) =>
* y I# }! @; D& L: C4 Y* u, v1 t! |& M/ [ 25^2 ≡ 25+2 (mod 299) =>
1 @9 Q! ~2 W! }% L 25^2-25-2 ≡ 0 (mod 299) => & D2 `7 Y9 z' j6 R4 W
(25-2)(25+1) ≡ 0 (mod 299) =>
1 C, ]" o' Y& o' H) U" ? g6 Q$ p8 G 23*26 ≡ 0 (mod 299)
5 ?8 Z, |/ P, L# c; `9 q7 N (23,299)=23 (26,299)=13 299=13*236 b6 P9 X, O2 E& }+ _3 X
% b' a' W' {/ k+ i3 u4 e
分解方法: 设n为奇合数, a^2 ≡ b (mod n) , 如果 b=a+i(i+1) (i ≥ 0 ) , 则可得到:
' v0 D! S+ s. D2 b6 v6 X a^2 ≡ b (mod n) =>
4 k. l. X N) V( t a^2-b-i(i+1) ≡ 0 (mod n) =>
5 {6 s; K. s, I) ~ (a-(i+1))(a+i) ≡ 0 (mod n)
! |9 |$ l# Q6 ]/ W6 \) P1 \' z (a-(i+1),n)>1 (a+i , n)>1 即可分解n) G. Z* J( l4 T
/ P) ]& A8 ?* v `: v4 }, a 2、分解方法的另一个解释
9 o( h' ?, I- w2 Q, D7 u8 C 设n为奇数, a^2 ≡ b(mod n), 如果m=a, 则由(1-1)公式得:
[. \5 P n7 L0 \ (1/2 -a)^2 ≡ 1/4 +a^2-a (mod n) =>
+ Z% ]# _8 F& N$ j (1/2 -a)^2 ≡ 1/4 +b-a (mod n) (2-1)
7 [4 T) |9 {$ J8 v" B+ n% g 9 V, X! ?7 q0 K& S# G c+ A
① n=4k-1 , 2-1式得:
5 `' [" _$ ]; v5 m) Y1 I (2k-a)^2 ≡ k+b-a(mod n) (2-2) X& _1 `. i* `, S, ]; \
① n=4k+1 , 2-1式得:
! Q$ v0 L) N- d. X; I+ g6 v (2k+1-a)^2 ≡ n-k+b-a (mod n) (2-3); H/ g, W3 C: V
: D C9 E6 ]- _! ^ 从(2-1(式, 可知二次剩余的计算, 在[1,1/4]范围内, 计算出[1,n-1]的二次剩余值. . i# l2 t/ `) J2 N& B
在例2中, 按(2-2)式的计算, 可得:
& d n+ L4 B" ^5 @ (150-25)^2 ≡ 75+27-25 (mod 299) => 125^2 ≡ 77 (mod 299) - u- d9 J4 ^5 w4 b( A
所以, a^2 ≡ b (mod n) ,如果b=a+i(i+1) ,其相对1/2的剩余值在后序序列上.
: ^- G) z* R' ~8 P. ?/ U9 s) c; s# K4 k
& ]$ L' o0 q# s$ H, L$ y 三、1/j (j >=3)的计算方法 $ G) s; q1 U0 z5 ^
上面的是计算 1/2, 即j=2, 如果j>2时, 有如下的1/j计算方法:8 f% b/ f L0 N- K; [6 z ^
(1/j ± ij)^2 = (ij)^2 ± 2i + (1/j)^2 (i >= 1 ) (j ≥3) (3-1)! \4 w+ g" K- c
5 ~' J" Z D; d" n) t 而对于\frac{1}{j}相邻, 有两种计算,
2 M7 K4 d* j8 v3 t 1) 1/j 1+1/j 2+1/j ... t+1/j (t<j) 6 B. u2 I6 c- ~ p4 F6 z
2) t-1/j ... 1-1/j 1/j 1+1/j ... t+1/j (t < j/2) - F% W. Z3 w2 d# m$ P5 Z d
t+1/j= (1+tj)/j = m/j , m=1+tj
, ?: X: G( |, i6 Z- h% c- o$ `5 E4 A6 U Z. r7 n$ A. u* v
按m/j , (3-1)式变成: * H# u& B" n% ]$ J* Q9 v
(m/j± ij )^2 = (ij)^2 ± 2mi + (m/j )^2 (i≥ 1 ) (j ≥ 3) (3-2)4 k, `" D- o& G' L8 o5 C# G
% G" L: j$ u9 C) t! W6 f1 R3 m
例3: n=299 \frac{1}{3} ≡ 100 (mod 299) 100^2 ≡ 133 (mod 299) ' M8 b5 U' [( T2 `& R4 b3 g
(100-3)^2 ≡ 3^2-2+133 (mod 299) => 97^2 ≡ 140 (mod 299)
& {9 m! P' h- a4 W2 U (100+3)^2 ≡ 3^2+2+133 (mod 299) => 103^2 ≡ 144 (mod 299)+ @" i3 U& C5 l( ]3 i
1+1/3=4/3 ≡ 1+100=101 (mod 299) 101^2 ≡ 35 (mod 299)$ \1 G+ X% j7 y8 i4 t
(101-3)^2 ≡ 3^2-2*4+35 (mod 299) => 98^2 ≡ 36 (mod 299) 9 H1 t* G8 N+ y7 o5 G
(101+3)^2 ≡ 3^2+2*4+35 (mod 299) => 104^2 ≡ 52 (mod 299)
8 E$ F) U2 K) n3 i, A* M3 z 1-1/3=-2/3 ≡ 1-100=-99 (mod 299) 99^2 ≡ 233 (mod 299)
% p: U q5 L/ w: R5 R( H' z (99-3)^2 ≡ 3^2-2*(-2)+233 (mod 299) => 96^2 ≡ 246 (mod 299) 8 y' H6 P. @: ~% b
(101+3)^2 ≡ 3^2+2*(-2)+233 (mod 299) => 102^2 ≡ 238 (mod 299)
$ F6 T6 _* ~6 ]4 V- K 按2+1/3也能得到相同结果,这里不在验证.
' j, K: ~/ t' r
& E- I2 _3 Z q# w5 O 当然如果j=2s, 即为偶数, 可以计算一半的值, (3-2)式得 :
( q% d0 g/ D% p& D7 K$ t (m/j ± i*s)^2=(is)^2±mi+(m/j)^2 (i ≥ 1) (j ≥ 3) (3-3)
f0 V" q, t, a 更一般的公式: 当为 g/j g <j/2 , (g, j)=1, 这里就不再给出.
! M8 t$ K# q5 y: Z8 l! O, ?+ I) C4 P* Z1 M& U& J( _7 L
|
zan
|