Čínska zvyšková veta

z Wikipédie, slobodnej encyklopédie
Prejsť na: navigácia, hľadanie

Čí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ť | upraviť zdroj]

Nech m_1, m_2, \ldots, m_n sú po dvoch nesúdeliteľné prirodzené čísla väčšie ako 1. Nech a_1, a_2, \ldots, a_n sú ľubovoľné celé čísla. Potom existuje riešenie x sústavy kongruencií

\left.\begin{array}{ccl}x & \equiv & a_1\ (\text{mod } m_1) \\ x & \equiv & a_2\ (\text{mod } m_2) \\ \vdots & \vdots & \vdots \\ x & \equiv & a_n\ (\text{mod } m_{n}) \end{array}\right\},

pričom všetky takéto riešenia x sú navzájom kongruentné modulo M := m_1 m_2 \ldots m_n.

Dôkaz[1][upraviť | upraviť zdroj]

Existencia[upraviť | upraviť zdroj]

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

\left.\begin{array}{ccl}x & \equiv & 0\ (\text{mod } m_1) \\ \vdots & \vdots & \vdots \\ x & \equiv & 0\ (\text{mod } m_{i-1}) \\ x & \equiv & 1\ (\text{mod } m_{i}) \\ x & \equiv & 0\ (\text{mod } m_{i+1}) \\ \vdots & \vdots & \vdots \\ x & \equiv & 0\ (\text{mod } m_n) \\ \end{array}\right\}.

Nech k_i = m_1 m_2 \ldots m_{i-1} m_{i+1} \ldots 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

\left.\begin{array}{ccl}r k_i & \equiv & 0\ (\text{mod } k_i) \\ r k_i & \equiv & 1\ (\text{mod } m_i) \end{array}\right\}.

Keďže sú ale všetky čísla m_1, m_2, \ldots, m_{i-1}, m_{i+1}, \ldots, m_n deliteľmi čísla k_i, z uvedenej sústavy dvoch kongruencií vyplýva platnosť sústavy

\left.\begin{array}{ccl}r k_i & \equiv & 0\ (\text{mod } m_1) \\ \vdots & \vdots & \vdots \\ r k_i & \equiv & 0\ (\text{mod } m_{i-1}) \\ r k_i & \equiv & 1\ (\text{mod } m_{i}) \\ r k_i & \equiv & 0\ (\text{mod } m_{i+1}) \\ \vdots & \vdots & \vdots \\ r k_i & \equiv & 0\ (\text{mod } m_n) \\ \end{array}\right\},

č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 + \ldots + a_n x_n,

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

Jednoznačnosť modulo M[upraviť | upraviť zdroj]

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

x - x' \equiv 0\ (\text{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, \ldots, m_n delí x - x'. Ale keďže sú čísla m_1, \ldots, m_n po dvoch nesúdeliteľné, má tento najmenší spoločný násobok hodnotu M, čo znamená, že

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

čo bolo treba dokázať.

Referencie[upraviť | upraviť zdroj]

  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ť | upraviť zdroj]