際際滷

際際滷Share a Scribd company logo

MATMA - Chuong3 thuat toan

Download as PPT, PDF
Sai Lemovom
Sai Lemovom
1 of 7
Downloaded 54 times
CH働NG 3 M畛T S畛 THU畉T TON
T鱈nh cn b畉c hai trong Zp Thu畉t to叩n t狸m cn b畉c hai modulo s畛 nguy棚n t畛 p VO: s畛 nguy棚n t畛 l畉 p v s畛 nguy棚n a, 1 a p 1 RA: hai cn b畉c hai c畛a a modulo p, gi畉 thi畉t r畉ng a l th畉ng d動 b狸nh ph動董ng modulo p. 錚a錚 錚 a錚 T鱈nh k鱈 hi畛u Legendre 錚 p 錚. N畉u 錚 錚 = 1 th狸 tr畉 v畛 a kh担ng c坦 cn b畉c 錚 錚 錚 p錚 錚 錚 錚 錚 hai modulo p) v d畛ng Ch畛n ng畉u nhi棚n b, 1 b p 1 cho 畉n khi t狸m 動畛c b v畛i 錚 b 錚 = 1 (b 錚 錚 錚 p錚 錚 錚 l kh担ng th畉ng d動 b狸nh ph動董ng modulo p) B畉ng c叩ch chia li棚n ti畉p cho 2, vi畉t p 1 = 2st v畛i t l畉 T鱈nh a-1 mod p b畉ng thu畉t to叩n c董lit m畛 r畛ng c bt mod p v r a(t+1)/2 mod p
T鱈nh cn b畉c hai trong Zp For i from 1 to s 1 do 2 1 2 s i 1 mod p T鱈nh d = ( r .a ) If d -1 (mod p) then r r.c mod p Set c c2 mod p Return (r, -r)
T鱈nh cn b畉c hai trong Zp Thu畉t to叩n t鱈nh cn b畉c hai modulo p khi p 3 (mod 4) VO: s畛 nguy棚n t畛 l畉 p v畛i p 3 (mod 4) v a Qp RA: hai cn b畉c hai c畛a a mod p T鱈nh r = a(p+1)/4 mod p Tr畉 v畛 (r, - r)
T鱈nh cn b畉c hai trong Zp Thu畉t to叩n t鱈nh cn b畉c hai modulo p khi p 5 (mod 8) VO: s畛 nguy棚n t畛 l畉 p v畛i p 5 (mod 8) v a Qp RA: hai cn b畉c hai c畛a a mod p T鱈nh d = a(p+1)/4 mod p If d = 1 then r = a(p+3)/8 mod p If d = -1 then r = 2a(4a) (p-5)/8 mod p Return (r, - r)
T鱈nh cn b畉c hai trong Zp Thu畉t to叩n t鱈nh cn b畉c hai modulo n, v畛i n l h畛p s畛 VO: s畛 nguy棚n n, c叩c nh但n t畛 nguy棚n t畛 c畛a n坦 p v q, a Qn RA: b畛n cn b畉c hai c畛a a mod n T狸m cn b畉c hai c畛a a modulo p l r v r (theo thu畉t to叩n 畛 tr棚n) T狸m hai cn b畉c hai c畛a a modulo q l s v s S畛 d畛ng thu畉t to叩n c董lit m畛 r畛ng 畛 t狸m c叩c s畛 nguy棚n c v d sao cho cp+dq = 1 x (rdq + scp) mod n v y (rdq - scp) mod n Return (賊x mod n, 賊y mod n)
T鱈nh cn b畉c hai trong Zp V鱈 d畛 叩p d畛ng: Trong h畛 m畉t Rabin, gi畉 s畛 p = 199, q = 211. X叩c 畛nh 4 cn b畉c hai c畛a 1 mod n, trong 坦 n = p.q. T鱈nh b畉n m達 c畛a 32767. X叩c 畛nh 4 b畉n gi畉i m達 c坦 th畛 c畛a b畉n m達 tr棚n

More Related Content

MATMA - Chuong3 thuat toan

  • 1. CH働NG 3 M畛T S畛 THU畉T TON
  • 2. T鱈nh cn b畉c hai trong Zp Thu畉t to叩n t狸m cn b畉c hai modulo s畛 nguy棚n t畛 p VO: s畛 nguy棚n t畛 l畉 p v s畛 nguy棚n a, 1 a p 1 RA: hai cn b畉c hai c畛a a modulo p, gi畉 thi畉t r畉ng a l th畉ng d動 b狸nh ph動董ng modulo p. 錚a錚 錚 a錚 T鱈nh k鱈 hi畛u Legendre 錚 p 錚. N畉u 錚 錚 = 1 th狸 tr畉 v畛 a kh担ng c坦 cn b畉c 錚 錚 錚 p錚 錚 錚 錚 錚 hai modulo p) v d畛ng Ch畛n ng畉u nhi棚n b, 1 b p 1 cho 畉n khi t狸m 動畛c b v畛i 錚 b 錚 = 1 (b 錚 錚 錚 p錚 錚 錚 l kh担ng th畉ng d動 b狸nh ph動董ng modulo p) B畉ng c叩ch chia li棚n ti畉p cho 2, vi畉t p 1 = 2st v畛i t l畉 T鱈nh a-1 mod p b畉ng thu畉t to叩n c董lit m畛 r畛ng c bt mod p v r a(t+1)/2 mod p
  • 3. T鱈nh cn b畉c hai trong Zp For i from 1 to s 1 do 2 1 2 s i 1 mod p T鱈nh d = ( r .a ) If d -1 (mod p) then r r.c mod p Set c c2 mod p Return (r, -r)
  • 4. T鱈nh cn b畉c hai trong Zp Thu畉t to叩n t鱈nh cn b畉c hai modulo p khi p 3 (mod 4) VO: s畛 nguy棚n t畛 l畉 p v畛i p 3 (mod 4) v a Qp RA: hai cn b畉c hai c畛a a mod p T鱈nh r = a(p+1)/4 mod p Tr畉 v畛 (r, - r)
  • 5. T鱈nh cn b畉c hai trong Zp Thu畉t to叩n t鱈nh cn b畉c hai modulo p khi p 5 (mod 8) VO: s畛 nguy棚n t畛 l畉 p v畛i p 5 (mod 8) v a Qp RA: hai cn b畉c hai c畛a a mod p T鱈nh d = a(p+1)/4 mod p If d = 1 then r = a(p+3)/8 mod p If d = -1 then r = 2a(4a) (p-5)/8 mod p Return (r, - r)
  • 6. T鱈nh cn b畉c hai trong Zp Thu畉t to叩n t鱈nh cn b畉c hai modulo n, v畛i n l h畛p s畛 VO: s畛 nguy棚n n, c叩c nh但n t畛 nguy棚n t畛 c畛a n坦 p v q, a Qn RA: b畛n cn b畉c hai c畛a a mod n T狸m cn b畉c hai c畛a a modulo p l r v r (theo thu畉t to叩n 畛 tr棚n) T狸m hai cn b畉c hai c畛a a modulo q l s v s S畛 d畛ng thu畉t to叩n c董lit m畛 r畛ng 畛 t狸m c叩c s畛 nguy棚n c v d sao cho cp+dq = 1 x (rdq + scp) mod n v y (rdq - scp) mod n Return (賊x mod n, 賊y mod n)
  • 7. T鱈nh cn b畉c hai trong Zp V鱈 d畛 叩p d畛ng: Trong h畛 m畉t Rabin, gi畉 s畛 p = 199, q = 211. X叩c 畛nh 4 cn b畉c hai c畛a 1 mod n, trong 坦 n = p.q. T鱈nh b畉n m達 c畛a 32767. X叩c 畛nh 4 b畉n gi畉i m達 c坦 th畛 c畛a b畉n m達 tr棚n