- 在线时间
- 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
 |
二次剩余值的关联计算(上)
2 ]5 g( G& M; V+ h5 p
4 X2 S3 x% N2 E2 ^2 ` { 一、 二次剩余中\frac{1}{2} 相关值的计算:( f9 Q9 t4 d O [- {
对于完全平方公式:
5 F& H. u; W4 \8 s$ ^) H (1/2 -m)^2 = 1/4 -m+m^2 = 1/4 +m(m-1) (m≥1) (1-1)! b8 ~# s0 O- y P3 p! A0 ?
# z" i8 L" ]% [' i5 g" G" }% ^
在n为奇数时, 上式的同余可以分为:$ P! i" ?7 u* A: T, d
① 当n=4k-1时,对(1-1)求同余得:
6 E3 a2 W* y/ g& d4 c8 F. l3 b (1/2-m)^2 ≡ (2k-m)^2 ≡ k+m(m-1) (mod n) (1-2)
* E; [9 Z" _/ T/ W7 L* K ② 当n=4k+1时, 对(1-1)求同余得: & Y/ d) J$ @$ r3 ?
(1/2 -m)^2 ≡ (2k+1-m)^2 ≡ -k+m(m-1) ≡ n-k+m(m-1) (mod n) (1-3), W7 N" n/ r* {' ?, I4 o- D
+ K1 m; K5 {. u7 ~0 K' z8 W& y# ] 为以后叙述方便,我们对 1/2-1 1/2-2 ... 1/2-m (m >=1) 这类数称为二次剩余的后序序列, 即1/2 减小的方向的数列.2 e8 m# g! s) r' }% E
% |8 v" C; r$ |5 d8 M, C
二次剩余后序序列的二次剩余值有个特点, 与k(k>0)值相关, 是k值与两个连续整数积的和,与k值同奇同偶。
6 i+ ]9 R z5 w+ N- W* N 如n=299=4*75-1 k=75 2k=150 , 二次剩余后序序列为:
' i# @; O9 c. |1 i% n (150-1)^2 ≡ 75+1*(1-1) ≡ 75 +0 ≡ 75 (mod 299) => 149^2 ≡ 75 (mod 299)
% ^, a$ n5 e% R/ j, ` (150-2)^2 ≡ 75+2*(2-1) ≡ 75 +2 ≡ 77 (mod 299) => 148^2 ≡ 77 (mod 299)
4 @8 n0 a4 w, b+ I' d* t; K u, k (150-3)^2 ≡ 75+3*(3-1) ≡ 75 +6 ≡ 81 (mod 299) => 147^2 ≡ 81 (mod 299)
. `" h0 r* t2 P2 C2 i
1 g; L9 n3 x7 P7 w | .4 q. [3 N- m0 b8 z( t
.* \4 _/ s$ ]! D* I3 P" r
根据后序序列,可以得到一个分解整数的方法:
$ k5 }* p+ j: Z# J; P" a; h% [, X# R 设n为奇合数, 如果 c^2-k=m(m-1) m>0 => (2k-m)^2 ≡ c^2 (mod n) , 或者
8 j2 @2 w( B0 U2 G. g c^2-k=m(m-1) => 4c^2-4k+1=4m(m-1)+1 => (2c)^2 ≡ (2m-1)^2 (mod n) + n7 J- v% \: @% s' b1 ^8 d. C8 Q
上述等式,由费马分解即可得到n的因子, 不过效率较低.+ Y. v- g5 z) P) v9 [( R
例1: n=299-4*75-1 , k=75& s/ }) m1 _; J, c% W- X
根据后序序列,大于75且与75同奇同偶的完全平方:9^2-810 j# ^; y3 o4 ]% A y
81-75=6=2*3 为连续两个整数积,在后序序列上7 t! S0 M) n0 {3 p
∴ (150-3)^2≡81 (mod 299) => 147^2≡81 (mod 299)4 f" v# `2 B h: x
或者 (2*9)^2≡(2*2+1)^2 (mod 299) => 18^2≡5^2(mod 299)
1 V& [' P6 b. h& h7 n- y: w" j6 o% y. _2 Q! z: I* X& x* ]
二、连续两个整数积的分解方法$ W4 L) a" U" F
1、分解方法介绍; y7 b& l" B1 ^0 ^
例2: n=299=4*75-1
2 t5 m/ W7 ^3 K6 e+ o" v 25^2 ≡ 27 (mod 299) =>
' I2 Q9 W0 s9 U7 m: Q 25^2 ≡ 25+2 (mod 299) => / Z0 l5 h. d5 @! a2 U
25^2-25-2 ≡ 0 (mod 299) => 9 z$ t1 f6 i- T
(25-2)(25+1) ≡ 0 (mod 299) =>
0 I6 k M4 o& _+ [, K, Y 23*26 ≡ 0 (mod 299) & E3 M+ g$ V7 f- f. m
(23,299)=23 (26,299)=13 299=13*23
1 ?& M" [& Q6 a; G0 @ G v( l; H: E. H2 b
分解方法: 设n为奇合数, a^2 ≡ b (mod n) , 如果 b=a+i(i+1) (i ≥ 0 ) , 则可得到:
% \. G4 O* u8 z( e) \ a^2 ≡ b (mod n) => # w1 g) P U0 ` W% [; S
a^2-b-i(i+1) ≡ 0 (mod n) =>
- D" d6 Q x1 ~! E Z+ J( m (a-(i+1))(a+i) ≡ 0 (mod n)
4 w$ s, a$ k3 Q! Q \ (a-(i+1),n)>1 (a+i , n)>1 即可分解n
- Z" N5 ]/ Z/ w, s5 y# |# r+ n# }
* E4 z3 g6 f: L) L- H9 V. S1 M/ Q 2、分解方法的另一个解释
( h" ]* \* e8 `! u+ ^ 设n为奇数, a^2 ≡ b(mod n), 如果m=a, 则由(1-1)公式得:
% ]. h* v: K" L2 \7 g/ b (1/2 -a)^2 ≡ 1/4 +a^2-a (mod n) => * M8 j& V. L* h- f c
(1/2 -a)^2 ≡ 1/4 +b-a (mod n) (2-1) 0 U3 Y( t" e# d2 [
# g# M# I2 J+ D0 z. s
① n=4k-1 , 2-1式得:
: L% d- _3 H. Q6 M; L/ } (2k-a)^2 ≡ k+b-a(mod n) (2-2)
, e' s* m7 m$ ^7 g1 P ① n=4k+1 , 2-1式得:
% f: ~9 J# ?8 A }2 ]2 u (2k+1-a)^2 ≡ n-k+b-a (mod n) (2-3)# t- b; ]" D2 K' _' N( @( ]
0 p0 o) b6 {4 q' t% R: P0 a4 y8 h3 A 从(2-1(式, 可知二次剩余的计算, 在[1,1/4]范围内, 计算出[1,n-1]的二次剩余值. 1 n/ K+ B/ n& \: W3 I
在例2中, 按(2-2)式的计算, 可得: + B% s& \0 I3 R) V* y
(150-25)^2 ≡ 75+27-25 (mod 299) => 125^2 ≡ 77 (mod 299)
" ]0 f" ^, [; z9 `5 O# B8 D" b0 c9 S 所以, a^2 ≡ b (mod n) ,如果b=a+i(i+1) ,其相对1/2的剩余值在后序序列上.5 P) Y3 k5 X2 Y! |' }" X, O5 Q
0 S- z: x0 Z' X( P8 [# j 三、1/j (j >=3)的计算方法
" |4 a- c+ c5 X1 I+ C# I 上面的是计算 1/2, 即j=2, 如果j>2时, 有如下的1/j计算方法:8 E9 u( C9 c3 w( v" e6 L
(1/j ± ij)^2 = (ij)^2 ± 2i + (1/j)^2 (i >= 1 ) (j ≥3) (3-1), W ^ J! y2 W& |
+ B7 t; n" m, q; U2 M+ @- z" ?9 I+ @$ U 而对于\frac{1}{j}相邻, 有两种计算,
7 l6 ?" A2 w+ t6 E" A/ Q3 x 1) 1/j 1+1/j 2+1/j ... t+1/j (t<j)
/ ^( }% e. {9 p! g8 j 2) t-1/j ... 1-1/j 1/j 1+1/j ... t+1/j (t < j/2) : t# j3 O( ^# Q: i& T6 B
t+1/j= (1+tj)/j = m/j , m=1+tj
3 k0 G- z) q2 _7 D
+ m5 a' Y. b. P8 ~4 P* J2 m7 ] 按m/j , (3-1)式变成:
& I2 u( G" e" Y9 h f (m/j± ij )^2 = (ij)^2 ± 2mi + (m/j )^2 (i≥ 1 ) (j ≥ 3) (3-2)
1 }: ~: D ~. K9 n% M" l0 \
* Z8 B. X1 C1 P! `; X3 O 例3: n=299 \frac{1}{3} ≡ 100 (mod 299) 100^2 ≡ 133 (mod 299) 4 _: k, }* \0 B3 g8 A* m9 R
(100-3)^2 ≡ 3^2-2+133 (mod 299) => 97^2 ≡ 140 (mod 299)
8 g8 e6 U$ X7 k0 B8 L (100+3)^2 ≡ 3^2+2+133 (mod 299) => 103^2 ≡ 144 (mod 299)
0 n7 t) l0 ]( H: w 1+1/3=4/3 ≡ 1+100=101 (mod 299) 101^2 ≡ 35 (mod 299)
6 d: |3 T* A* z$ d8 s (101-3)^2 ≡ 3^2-2*4+35 (mod 299) => 98^2 ≡ 36 (mod 299)
/ ?- f! C) i0 u8 j2 m1 l' _ (101+3)^2 ≡ 3^2+2*4+35 (mod 299) => 104^2 ≡ 52 (mod 299)
* H2 v0 m+ B6 o4 M( O( i 1-1/3=-2/3 ≡ 1-100=-99 (mod 299) 99^2 ≡ 233 (mod 299) 1 ?) n, Z7 a* Q1 T
(99-3)^2 ≡ 3^2-2*(-2)+233 (mod 299) => 96^2 ≡ 246 (mod 299) 2 V' Z0 a$ R; u* j, b
(101+3)^2 ≡ 3^2+2*(-2)+233 (mod 299) => 102^2 ≡ 238 (mod 299) , H0 P! F) a- J2 c' w
按2+1/3也能得到相同结果,这里不在验证.6 Z- A7 R5 ^: n: e/ c
3 n% b+ |! Q# u" { 当然如果j=2s, 即为偶数, 可以计算一半的值, (3-2)式得 :
6 Z4 q4 O2 n2 b! `# X, J6 j (m/j ± i*s)^2=(is)^2±mi+(m/j)^2 (i ≥ 1) (j ≥ 3) (3-3)
$ |: c. Q5 J- b" ] 更一般的公式: 当为 g/j g <j/2 , (g, j)=1, 这里就不再给出.) b& ^$ a: I6 v( Q0 h
+ H4 L8 S8 Y+ M* z3 C* ~8 \ [
|
zan
|