Čí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]

Nech $m_{1}, m_{2}, \dots, m_{n}$ sú po dvoch nesúdeliteľné prirodzené čísla väčšie ako 1. Nech $a_{1}, a_{2}, \dots, a_{n}$ sú ľubovoľné celé čísla. Potom existuje riešenie x sústavy kongruencií

\begin{matrix} x & \equiv & a_{1} (mod m_{1}) \\ x & \equiv & a_{2} (mod m_{2}) \\ ⋮ & ⋮ & ⋮ \\ x & \equiv & a_{n} (mod m_{n}) \end{matrix}},

pričom všetky takéto riešenia x sú navzájom kongruentné modulo $M : = m_{1} m_{2} \dots m_{n}$ .

Dôkaz^[1]

Existencia

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

\begin{matrix} x & \equiv & 0 (mod m_{1}) \\ ⋮ & ⋮ & ⋮ \\ x & \equiv & 0 (mod m_{i - 1}) \\ x & \equiv & 1 (mod m_{i}) \\ x & \equiv & 0 (mod m_{i + 1}) \\ ⋮ & ⋮ & ⋮ \\ x & \equiv & 0 (mod m_{n}) \end{matrix}} .

Nech $k_{i} = m_{1} m_{2} \dots m_{i - 1} m_{i + 1} \dots m_{n}$ . Čísla $m_{i}$ a $k_{i}$ sú zrejme nesúdeliteľné, čo znamená, že existujú celé čísla r,s také, že platí

r k_{i} + s m_{i} = 1,

z čoho vyplývajú kongruencie

\begin{matrix} r k_{i} & \equiv & 0 (mod k_{i}) \\ r k_{i} & \equiv & 1 (mod m_{i}) \end{matrix}} .

Keďže sú ale všetky čísla $m_{1}, m_{2}, \dots, m_{i - 1}, m_{i + 1}, \dots, m_{n}$ deliteľmi čísla $k_{i}$ , z uvedenej sústavy dvoch kongruencií vyplýva platnosť sústavy

\begin{matrix} r k_{i} & \equiv & 0 (mod m_{1}) \\ ⋮ & ⋮ & ⋮ \\ r k_{i} & \equiv & 0 (mod m_{i - 1}) \\ r k_{i} & \equiv & 1 (mod m_{i}) \\ r k_{i} & \equiv & 0 (mod m_{i + 1}) \\ ⋮ & ⋮ & ⋮ \\ r k_{i} & \equiv & 0 (mod m_{n}) \end{matrix}},

čo znamená, že hodnota $x_{i} : = r k_{i}$ 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

x : = a_{1} x_{1} + a_{2} x_{2} + \dots + a_{n} x_{n},

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

Jednoznačnosť modulo $M$

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

x - x^{'} \equiv 0 (mod m_{i}) .

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

x \equiv x^{'} (mod M),

čo bolo treba dokázať.

Referencie

↑ ^1,0 ^1,1 ^1,2 ^1,3 Yan, S. Y.: Number Theory for Computing. 2. vydanie, Springer, 2002.
↑ Koblitz, N.: A Course in Number Theory and Cryptography. 2. vydanie, Springer-Verlag, 1994.
↑ Paj's Home: Cryptography: RSA: Mathematics

Externé odkazy

Čínska veta o zvyškoch - Wolfram MathWorld Šablóna:Eng icon.
Čínska veta o zvyškoch - Cut-The-Knot Šablóna:Eng icon.

[yan-1] 1,0 ^1,1 ^1,2 ^1,3 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

[1]

[2]

[3]

Čínska zvyšková veta

Obsah

Znenie vety^[1]

Dôkaz^[1]

Existencia

Jednoznačnosť modulo $M$

Referencie

Externé odkazy

Navigačné menu

Čínska zvyšková veta

Znenie vety[1]

Dôkaz[1]

Existencia

Jednoznačnosť modulo M

Referencie

Externé odkazy

Navigačné menu

Hľadať

Znenie vety^[1]

Dôkaz^[1]

Jednoznačnosť modulo $M$