Kínai maradéktétel

1. Sablon:Label

Kínai maradéktétel (Chinese Remainder Theorem)

Definíció

A **kínai maradéktétel** (CRT) egy matematikai tétel, amely az egész számok moduláris kongruenciájával foglalkozik. Ha egy számot több páratlanul osztható (relatív prím) modullal veszünk kongruenssé, akkor létezik egy egyértelmű megoldás egy adott intervallumban.

Formális Meghatározás

Legyenek:

• $n_1,n_2,\dots ,n_k$ egymással relatív prím számok ($\text{gcd}(n_i,n_j)=1$ minden $i\ne j$-re),
• $a_1,a_2,\dots ,a_k$ egész számok.

A kínai maradéktétel állítása szerint a következő kongruenciarendszer: $x\equiv a_1(\mathrm{mod}{n}_1)$ $x\equiv a_2(\mathrm{mod}{n}_2)$ $⋮$ $x\equiv a_k(\mathrm{mod}{n}_k)$ mindig egyértelmű megoldással rendelkezik modulo $N=n_1\cdot n_2\cdot \dots \cdot n_k$.

Lépések a Megoldáshoz

1. Kiszámítjuk a $N=n_1\cdot n_2\cdot \dots \cdot n_k$ értéket.
2. Kiszámítjuk minden modul $N_i=\frac{N}{n_i}$ értékét.
3. Keresünk egy fordított modult $y_i$-re, amely teljesíti:

  $N_i\cdot y_i\equiv 1(\mathrm{mod}{n}_i)$

1. Kiszámítjuk az $x$ megoldást:

  $x=\sum _{i=1}^k{a}_i\cdot N_i\cdot y_i(\mathrm{mod}N)$

Példa

Kongruenciarendszer: $x\equiv 2(\mathrm{mod}3)$ $x\equiv 3(\mathrm{mod}5)$ $x\equiv 2(\mathrm{mod}7)$

Megoldás:

1. $N=3\cdot 5\cdot 7=105$
2. $N_1=\frac{105}{3}=35,N_2=\frac{105}{5}=21,N_3=\frac{105}{7}=15$
3. Keresünk $y_i$-ket:

  * $y_1$: $35\cdot y_1\equiv 1(\mathrm{mod}3)⟹y_1=2$,
  * $y_2$: $21\cdot y_2\equiv 1(\mathrm{mod}5)⟹y_2=1$,
  * $y_3$: $15\cdot y_3\equiv 1(\mathrm{mod}7)⟹y_3=1$.

1. Az $x$ megoldása:

  $x=(2\cdot 35\cdot 2)+(3\cdot 21\cdot 1)+(2\cdot 15\cdot 1)(\mathrm{mod}105)$
  $x=(140)+(63)+(30)(\mathrm{mod}105)$
  $x=233(\mathrm{mod}105)=23$

Megoldás: $x\equiv 23(\mathrm{mod}105)$.

Python Implementáció

Az alábbi Python kód implementálja a kínai maradéktételt:

from functools import reduce

def modular_inverse(a, m):
    """
    Kiszámítja a modulinverzt a mod m alatt.
    """
    a = a % m
    for x in range(1, m):
        if (a * x) % m == 1:
            return x
    return None

def chinese_remainder(n, a):
    """
    Kínai maradéktétel megoldása.
    
    Args:
        n: Modulok listája.
        a: Kongruenciák listája.
        
    Returns:
        Az x megoldás, amely megfelel a kongruenciarendszernek.
    """
    N = reduce(lambda x, y: x * y, n)  # Az összes modul szorzata
    x = 0
    for n_i, a_i in zip(n, a):
        N_i = N // n_i
        y_i = modular_inverse(N_i, n_i)
        x += a_i * N_i * y_i
    return x % N

# Példa használat
n = [3, 5, 7]  # Modulok
a = [2, 3, 2]  # Kongruenciák

result = chinese_remainder(n, a)
print("Megoldás:", result)

Kimenet

Megoldás: 23

Alkalmazások

1. Kriptográfia:

  * RSA titkosítás optimalizálása.

1. Hálózatok és Időzítés:

  * Moduláris ütemezési problémák megoldása.

1. Számítógépes algebra:

  * Nagy számítások modularizálása több maradékosztályba.

Előnyök

• Egyszerű megoldást nyújt kongruenciarendszerekre.
• Segítségével könnyen kezelhetők nagy számokkal végzett műveletek.

Összegzés

A **kínai maradéktétel** rendkívül hasznos eszköz matematikai, számítástechnikai és kriptográfiai problémák megoldására. A Python implementációval egyszerűen megoldhatók moduláris kongruenciarendszerek, és könnyen érthetővé válik a tétel alkalmazása.

• Sablon:En: Sablon:T
• Sablon:Ru: Sablon:T