Çin qalıq teoremi
İki siferblat birlikdə fırlanır, biri m moduluna, digəri n moduluna görə, ta ki hər ikisi istədiyiniz qalıqları göstərsin. Sonra bütün tor işıqlanır.
İnteraktiv demonun içindəki yazılar hələlik ingilis dilindədir.
x0
0123456
00
1
2
3
4
1 / 35
Press play. Both dials advance by one each step; each x goes into the cell (x mod 5, x mod 7). Row 3 is the target for the first dial, column 4 for the second.
Nəyə diqqət etməli
- gcd(m, n) = 1 olanda sayğac m × n torunun hər xanasından düz bir dəfə keçir, buna görə hər (a, b) cütü üçün m·n-dən kiçik düz bir x var.
- m və n-i ortaq vuruqlu seçin, məsələn 4 və 6: torun yarısına heç vaxt çatılmır, bəzi sistemlərin isə həlli yoxdur.
- RSA-CRT məhz bundan istifadə edir: p və q modulları üzrə ayrı-ayrı hesablayıb nəticələri birləşdirir. Təxminən 4 dəfə sürətlidir.