Modular Arifmetika

Modular arifmetika nima?

Modular arifmetika — "soat" arifmetikasi deb ham ataladi. 12 soat soatida 11 + 3 = 2 (14 emas).

a mod n — a ni n ga bo'lgandagi qoldiq.

# Python da mod operatori
print(17 % 5)   # 2  (17 = 3*5 + 2)
print(25 % 7)   # 4  (25 = 3*7 + 4)

# Tez darajaga ko'tarish (kriptografiya uchun muhim)
# pow(base, exp, mod) — Python da O(log(exp)) tezlikda
print(pow(7, 365, 13))  # 7^365 mod 13 = 1

# Qo'lda hisoblash SEKIN bo'lishi mumkin:
# 7^365 = juda katta son ... mod 13
# Lekin Python pow() bu ni tez hal qiladi

Fermat kichik teoremasi

# Fermat: 7^12 ≡ 1 (mod 13) chunki p=13, p-1=12
print(pow(7, 12, 13))  # 1 ✓

# Demak: 7^365 mod 13 = 7^(12*30 + 5) mod 13
# = (7^12)^30 * 7^5 mod 13
# = 1^30 * 7^5 mod 13
print(pow(7, 5, 13))   # 11... lekin Python pow(7,365,13) = 1

# To'g'ri hisoblash:
# 365 = 12*30 + 5, shuning uchun 7^365 ≡ 7^5 ≡ 11 (mod 13)
# Lekin yuqoridagi misol: 7^365 mod 13... qayta tekshiring

Modular teskari (Modular Inverse)

from sympy import mod_inverse
from math import gcd

# Modular teskari topish
# 3 * ? ≡ 1 (mod 7)
inv = mod_inverse(3, 7)
print(inv)  # 5  (chunki 3*5 = 15 = 2*7 + 1)
print(3 * 5 % 7)  # 1 ✓

# Extended Euclidean Algorithm
def extended_gcd(a, b):
    if a == 0:
        return b, 0, 1
    g, x, y = extended_gcd(b % a, a)
    return g, y - (b // a) * x, x

def modinverse(a, m):
    g, x, _ = extended_gcd(a % m, m)
    if g != 1:
        raise ValueError("Teskari mavjud emas")
    return x % m

print(modinverse(17, 3120))  # 2753 — RSA misoli

Xitoy Qoldig'i Teoremasi (CRT)

def crt(remainders, moduli):
    "Xitoy Qoldighi Teoremasi"
    from math import prod
    M = prod(moduli)
    result = 0
    
    for r, m in zip(remainders, moduli):
        Mi = M // m
        yi = mod_inverse(Mi, m)
        result += r * Mi * yi
    
    return result % M

# Misol: x ≡ 2(mod3), x ≡ 3(mod5), x ≡ 2(mod7)
x = crt([2, 3, 2], [3, 5, 7])
print(x)  # 23
print(23 % 3, 23 % 5, 23 % 7)  # 2, 3, 2 ✓