Chinese remainder theorem
hiina jäägiteoreem
olemus
arvuteoorias väide, et
ühistegurita arvude m ja n ning suvaliste jääkide a ja b korral
leidub vahemikus 1...mn parajasti üks selline arv, mis
m-ga jagamisel annab jäägi a ja
n-ga jagamisel annab jäägi b
- üldistab lihtsamat väidet, mis ütleb, et kui m ja n
on ühistegurita, siis on korrutis mn
vähim positiivne arv, mis jagub nii m-ga kui ka n-ga
- võimaldab peaaegu neljakordselt
kiirendada krüpteerimist RSA privaatvõtmega
Wiktionary:
(number theory) a theorem stating that, if one knows the remainders of the Euclidean division of an integer n by several integers, then one can determine uniquely the remainder of the division of n by the product of these integers, under the condition that the divisors are pairwise coprime
ülevaateid
https://en.wikipedia.org/wiki/Chinese_remainder_theorem
http://www-math.ucdenver.edu/~wcherowi/courses/m5410/crt.pdf
http://ramanujan.math.trinity.edu/rdaileda/teach/s18/m3341/CRT.pdf
rakendusi
http://www.worldscientific.com/worldscibooks/10.1142/3254
http://data.at.preempted.net/INDEX/articles/CRT.pdf
https://www.di-mgt.com.au/crt_rsa.html
https://www.cscjournals.org/manuscript/Journals/IJCSS/Volume10/Issue5/IJCSS-1289.pdf
https://asecuritysite.com/encryption/crackrsa3