### Kongruenciák
### ============


### ---------------------------------------------------------------------------
### 1. feladat: Egyszerű számlálás
###
### Hány prímszám van 2800000-ig, amely kongruens 7-tel modulo 235?

def kongr_szaml ():
    pass #TODO

def test1 ():
    print("1. Egyszerű számlálás")
    print(kongr_szaml())
    print()
#test1()


### ---------------------------------------------------------------------------
### 2. feladat: Lineáris kongruencia
###
### Oldjuk meg az a*x ≡ b (mod m) lineáris kongruenciát adott a, b, m számokra
### az alábbi módszerekkel. A visszatérési érték minden esetben egy lista,
### amely az összes megoldást tartalmazza 0 és m-1 között (növekvő sorrendben).
### (Ne használjuk a Sage egyenletmegoldó függvényeit.)

### a) Egyszerű kereséssel ("brute force"):
def linkon_keres (a, b, m):
    pass #TODO

### b) Bővített euklideszi algoritmussal:
def linkon_eukl (a, b, m):
    pass #TODO

def test2 ():
    print("2. Lineáris kongruencia")
    tests = [(3,5,8), (6,6,15), (12,9,18), (21,14,35), (100,40,260)]
    for fv in [linkon_keres, linkon_eukl]:
        if fv(1,2,3) == None: continue
        print(f"{fv.__name__}()")
        for (a,b,m) in tests:
            mo = fv(a,b,m)
            print(f"   {a}*x = {b} ({m}) :", mo)
            for xx in mo:
                assert (a*xx - b) % m == 0, f"{xx} nem megoldás"
        tests.append((30517578125, 33729082272, 999999999999)) # csak eukl
    print()
#test2()


### ---------------------------------------------------------------------------
### 3. feladat: Moduláris inverz
###
### Számítsuk ki adott 'a' szám inverzét modulo m (adott a és m egészekre) az
### alábbi módszerekkel. Ha nem invertálható, akkor None-t adjunk vissza.

### a) Egyszerű kereséssel ("brute force"):  (ne keressünk tovább, mint kell)
def inv_keres (a, m):
    pass #TODO

### b) Bővített euklideszi algoritmussal:
def inv_eukl (a, m):
    pass #TODO

def test3 ():
    print("3. Moduláris inverz")
    for fv in [inv_keres, inv_eukl]:
        if fv(1,2) == None: continue
        for m in range(2, 100):
            for a in range(0, m):
                try: inv = inverse_mod(a, m)
                except: inv = None
                assert fv(a, m) == inv, f"{fv.__name__}({a}, {m})"
        print(f"{fv.__name__}() OK")
        if fv == inv_eukl:
            a, m = 987654321, 79590490282399
            inv = fv(a, m)
            print(f"{fv.__name__}({a}, {m}) ==", inv)
            assert inv == inverse_mod(a, m)
    print()
#test3()


### ---------------------------------------------------------------------------
### 4. feladat: Bankszámlaszám
###
### Az alábbi részfeladatokban a bankszámlaszámokat a számjegyeinek listával
### adjuk meg (16 vagy 24 számjegy hosszúak), például:
###    [1,0,4,0,2,1,9,6,5,0,5,2,6,7,6,5,8,1,7,7,1,0,0,6].

### a) Döntsük el, hogy a bankszámlaszám helyes-e (az ellenőrzőösszeg alapján).
def ban_ok (ban):
    pass #TODO

### b)-c) Javítsuk ki a megadott (potenciálisan) hibás bankszámlaszámot, ha
### tudjuk, melyik számjegye a hibás (j: a hibás számjegy indexe 0-tól 23-ig).
### A feladatot kétféleképpen oldjuk meg, az alábbiak szerint.
### Feltételezhetjük, hogy ez az egyetlen hibás számjegye (ha van egyáltalán).
### Adjuk vissza a helyes bankszámlaszámot.

### b) Egyszerű próbálgatással oldjuk meg (a hibás számjegy helyén).
def ban_fix_1 (ban, j):
    pass #TODO

### c) Lineáris kongruencia (vagy inverz) segítségével oldjuk meg.
### (Az ellenőrzőösszeg egyszeri kiszámításán kívül ne használjunk ciklust!)
def ban_fix_2 (ban, j):
    pass #TODO

def test4 ():
    print("4. Bankszámlaszám")
    def to_str (ban):
        ban = "".join(map(str, ban))
        return "-".join([ban[i:i+8] for i in range(0, len(ban), 8)])
    good_ban = [1,0,7,0,0,5,0,5,7,0,3,4,7,9,1,5,5,1,3,0,0,0,0,9]
    print("jó:   ", to_str(good_ban), "->", ban_ok(good_ban))
    wrong_ban = [1,0,4,0,2,1,9,6,5,0,5,2,6,7,6,5,8,1,7,7,1,0,0,6]
    print("rossz:", to_str(wrong_ban), "->", ban_ok(wrong_ban))
    fixed1 = ban_fix_1(wrong_ban, 6)
    if fixed1 != None:
        print(to_str(wrong_ban), "->", to_str(fixed1))
        assert ban_ok(fixed1), f"ban_ok({to_str(fixed1)})"
    fixed2 = ban_fix_2(wrong_ban, 6)
    if fixed2 != None:
        print(to_str(wrong_ban), "->", to_str(fixed2))
        assert ban_ok(fixed2), f"ban_ok({to_str(fixed2)})"
    ban = good_ban[:]
    for i in range(len(ban)):
        for d in range(10):
            if d == good_ban[i]: continue
            ban[i] = d
            assert not ban_ok(ban), f"ban_ok({to_str(ban)})"
            if fixed1: assert ban_fix_1(ban, i) == good_ban, f"ban_fix_1({to_str(ban)}, {i})"
            if fixed2: assert ban_fix_2(ban, i) == good_ban, f"ban_fix_2({to_str(ban)}, {i})"
        ban[i] = good_ban[i]
    print()
#test4()


### ---------------------------------------------------------------------------
### 5. feladat: Kínai maradéktétel
###
### Implementáljuk a kínai maradéktételt (PDF, 6. szakasz) két kongruenciára:
###    x ≡ a (mod m)
###    x ≡ b (mod n)
### Az eredmény az (x,r) pár legyen, ahol x a (legkisebb nemnegatív) megoldás,
### és r a megoldás modulusa. Ha nincs megoldás, akkor None-t adjunk vissza.
### (Ne használjuk a crt()-t és a Sage egyéb egyenletmegoldó függvényeit.)

def kinai_maradek (a, b, m, n):
    pass #TODO

def test5 ():
    print("5. Kínai maradéktétel")
    if kinai_maradek(1,1,2,3) == None: return
    for (a,b, m,n) in [
        (2,5, 7,8),
        (2,2, 3,5),
        (3,5, 10,6),
        (8,4, 10,15),
        (6789,789, 12345,123456),
    ]:
        print(f"x = {a} ({m}) /\\ x = {b} ({n}) ==> ", end="")
        res = kinai_maradek(a, b, m, n)
        if res == None:
            print(res)
        else:
            x,r = res
            print(f"x = {x} ({r})")
            assert x % m == a and x % n == b, "nem megoldás"
            assert x == crt(a, b, m, n), "nem a legkisebb megoldás"
            assert (x+r) % m == a and (x+r) % n == b, "r={r} hibás"
            for rr in divisors(r):
                assert r == rr or (x+rr) % m != a or (x+rr) % n != b, f"r={r} túl nagy"
    print()
#test5()