Mô tả:
Ê
Ê
c
c Ê
3 b đӗng dư modulo n nӃu |3b| là bӝi sӕ cӫ3 n Tӭc: NӃu chi3 3 cho n; b chi3 cho
n thì nhұn cùng sӕ dư
3!"#$%
&'(: 13 !3 (mod 10) vì (13 ± 3) = 10 là bӝi sӕ cӫ3 10
Modulo có mӕi qu3n hӋ vӟi sӕ dư trong phép chi3 phép toán tìm sӕ dư đôi
khi cũng giӕng như phép toán modulo.
2 ! 14 ($ 12)
&'(: 2 ) 14 ($ 12)
Nhưng: 38 Ł 14 ($ 12) thì đúng nhưng 38 = 14 ($ 12) lҥi không đúng
*c +,+-.Ê
ӕ nghӏch đҧo cӫ3 10 là 1/10 bӣi vì 10 × 1/10=1. Trong sӕ hӑc modulo thì vҩn đӅ
nghӏch đҧo phӭc tҥp hơn.
4 × x Ł 1 mod 7
Phương trình trên tương đương vӟi tìm x và k s3o cho
4x = 7k+1
vӟi điӅu kiӋn là cҧ x và k đӅu là sӕ nguyên.
Vҩn đӅ chung đһt r3 tҥi đây là tìm x s3o cho
1 = (3 × x) mod n
có thӇ viӃt lҥi như s3u :
31 Ł x(mod n )
thu nhӓ vҩn đӅ Modulo là rҩt khó giҧi quyӃt. Đôi khi nó là mӝt vҩn đӅ nhưng
đôi khi lҥi không phҧi vұy.
Ví dө : nghӏch đҧo cӫ3 5 modulo 14 là 3 bӣi
5 × 3 = 15 Ł 1 (mod 14).
/(0+10023$45-60'++,+-.Ê
Giҧi thuұt s3u sӁ tính nghӏch đҧo modulo m cӫ3 3 và chӍ th c hiӋn vӟi các sӕ
nguyên m>3>0 biӇu diӉn bҵng giã mã:
1
R
c
Jcc J c
c
2 cccc
ccc
ccccc c
c
ccc
ccccc
c cc ccccccc
cccccc
c
cc
ccccc c c
ccccc
c
ccccc c
ccccc cccccc
ccccc c
ccc
cc c
c c c c c c
!"c
cc
c
cc# c!c
"$c
c %cc$&c c
&'(
Tìm sӕ nghӏch đҧo (nӃu có) cӫ3 30 theo môđun 101
Bưӟc i
0
1
2
3
4
5
$
9
30
11
8
3
2
KӃt quҧ tính toán trong bҧng cho t3
64. Vұy :9;$9)=>
3
:9
11
8
3
2
1
4
11
8
3
2
1
0
7
3
2
1
2
1
.
89
0
1
3
7
10
.
8
1
3
7
10
27
.
8
3
7
10
27
;:<
.
37. Lҩy sӕ đӕi cӫ3 37 theo mođun 101 đưӧc
2
:c 3.3"?30)"@$AB3CB
Trong đó e là sӕ mũ lӟn n là sӕ chi3 đӇ lҩy dư
&'( Tính 413(mod 497)
Cách tính đơn thuҫn: 413=67108864
67108864 mod 497 =445
e
@
NӃu b và e lӟn thì b sӁ rҩt lӟn và tính " $sӁ mҩt nhiӅu thӡi gi3n và tӕn bӝ
nhӟ. Có mӝt sӕ cách đӇ giҧi quyӃt vҩn đӅ đó. Trong nӝi dung cӫ3 tiӇu luұn chúng
tôi sӱ dөng giҧi pháp như s3u:
c Ł (3.b)(mod n) => ((3 (mod n)).(b (mod n))) (mod n)
Áp dөng công thӭc trên t3 có thuұt toán
L0
t0L0 Ł
1/ Gán c=1 e¶=0
2/ e¶=e¶+1
3/ c Ł (b.c) (mod m)
4/ NӃu e¶%
T3 thҩy N =pxq vӟi p q là sӕ nguyên tӕ. Trong toán hӑc đã chӭng minh đưӧc rҵng
nӃu N là sӕ nguyên tӕ thì công thӭc (4) sӁ có lӡi giҧi khi và chӍ khi:
PGP!#$ w %#T%
Trong đó w N =LCM(p1 q1 ).
(Lest Common Multiple) là bӝi sӕ chung nhӓ nhҩt .
Nói mӝt cách khác đҫu tiên ngưӡi nhұn B l 3 chӑn mӝt khó3 công kh3i KB mӝt
cách ngүu nhiên. Khi đó khó3 bí mұt kB đưӧc tính r3 bҵng công thӭc (5). ĐiӅu này
hoàn toàn tính đưӧc vì khi B biӃt đưӧc cһp sӕ nguyên tӕ (p q) thì sӁ tính đưӧc w N
Chӑn p và q
Tính N = p x q
Tính w N
Bҧn rõ P
KB
C = PKB (mod N)
Chӑn khó3 KP
Bҧn mã C
kB
Chӑn khó3 kP
P = CkB (mod N)
Bҧn rõ gӕc
M+<
-"B0+U+3D$E+F30+@0+100
&'(
N=11413=101x113 w (N) =100x112 =11200 =26x52x7. KB phҧi chӑn s3o cho không
chi3 hӃt cho 2 5 7. Chӑn chҷng hҥn KB =3533 khi đó
kB = KB1mod11200=6597. Và t3 có khó3 công kh3i là (N KB)=(11413 3533) khó3 bí
mұt là 6597. Phép lұp mã và giҧi mã là
5
EKB(P) =PKB (mod N) =P3533 (mod 11413)
DkB(C) =CkB (mod N) =C6579 (mod 11413)
?3-V00+100
c Chương trình đưӧc viӃt bҵng ngôn ngӳ lұp trình C# có chӭc năng mô phӓng
lҥi toàn bӝ quá trình mã hó3 và giҧi mã cӫ3 thuұt toán RA.
c |iӋn tҥi thuұt toán chӍ cài đһt mã hó3 các ký t ho3 không dҩu.
Gi3o diӋn cӫ3 chương trình
ëc w04M+I/WO3+04M++3
P: Nhұp văn bҧn cҫn mã hó3 vào ô ³Văn bҧn gӕc´
CO O TOAN
P*: Chương trình sӁ chuyӇn đәi văn bҧn đó thành chuӛi sӕ bҵng cách d 3 trên sӕ
thӭ t cӫ3 chӳ cái đó trong bҧng chӳ cái.
CO O TOAN > 03152719152720150114
P:: Mã hó3 chuӛi sӕ d 3 trên +F3$E và sӕ
03152719152720150114 > 64241131545795607113154579471131517289
P>: Giҧi mã d 3 trên +F33.3
64241131545795607113154579471131517289 > 03152719152720150114
PT: Đư3 r3 văn bҧn gӕc d 3 trên chuӛi sӕ đưӧc giҧi mã
6
- Xem thêm -