Čínska zvyšková veta

Čínska zvyšková veta alebo čínska veta o zvyškoch je veta v teórii čísel objavená čínskym matematikom Sun-c' [1] hovoriaca o riešeniach systémov lineárnych kongruencií.[1][2] Medzi hlavné aplikácie vety patrí dôkaz bezpečnosti šifrovacieho algoritmu RSA.[3]

Znenie vety[1]

upraviť

Nech   sú po dvoch nesúdeliteľné prirodzené čísla väčšie ako 1. Nech   sú ľubovoľné celé čísla. Potom existuje riešenie x sústavy kongruencií

 

pričom všetky takéto riešenia x sú navzájom kongruentné modulo  .

Existencia

upraviť

Vyriešime najprv špeciálny prípad uvedenej sústavy kongruencií:

 

Nech  . Čísla   a   sú zrejme nesúdeliteľné, čo znamená, že existujú celé čísla r,s také, že platí

 

z čoho vyplývajú kongruencie

 

Keďže sú ale všetky čísla   deliteľmi čísla  , z uvedenej sústavy dvoch kongruencií vyplýva platnosť sústavy

 

čo znamená, že hodnota   je riešením uvedeného špeciálneho prípadu systému kongruencií. Z toho už ale triviálnou úvahou vyplýva, že riešenie všeobecného systému kongruencií má tvar

 

čo znamená, že existencia riešenia je dokázaná.

Jednoznačnosť modulo  

upraviť

Nech   sú riešenia uvedenej sústavy kongruencií. Z toho vyplýva, že pre každé i platí

 

Inými slovami, hodnota   delí   pre každé i. Z toho vyplýva, že aj najmenší spoločný násobok čísel   delí  . Ale keďže sú čísla   po dvoch nesúdeliteľné, má tento najmenší spoločný násobok hodnotu M, čo znamená, že

 

čo bolo treba dokázať.

Referencie

upraviť
  1. a b c d Yan, S. Y.: Number Theory for Computing. 2. vydanie, Springer, 2002.
  2. Koblitz, N.: A Course in Number Theory and Cryptography. 2. vydanie, Springer-Verlag, 1994.
  3. Paj's Home: Cryptography: RSA: Mathematics

Externé odkazy

upraviť