### Diszkrét logaritmus
### ===================


### ---------------------------------------------------------------------------
### 1. feladat: Moduláris hatványozás
###
### Számítsuk ki a^n mod m-et egyszerű ismétléses moduláris szorzással
### (a "naív" módszerrel), de anélkül, hogy kiszámítanánk a^n-t egész számként.

def power_simple (a, n, m):
    r = a % m
    for i in range(1, n):   # n-1-szer
    	r = (r * a) % m
    return r

def test1 ():
    print("1. Moduláris hatványozás")
    for m in range(2, 8):
        for a in range(m):
            for n in range(1, 10):
                assert power_simple(a, n, m) == power_mod(a, n, m), f"{a}^{n} mod {m}"
        print(f"m={m} OK")
    a, n, m = 666, 999999, 11
    r = power_simple(a, n, m)
    print(f"{a}^{n} = {r} (mod {m})")
    assert r == power_mod(a, n, m)
    print()
test1()


### ---------------------------------------------------------------------------
### 2. feladat: Gyorshatványozás
###
### Számítsuk ki a^n mod m-et a gyorshatványozás módszerével.

def power_fast (a, n, m):
    pass #TODO

def test2 ():
    print("2. Gyorshatványozás")
    for m in range(2, 8):
        for a in range(m):
            for n in range(1, 10):
                assert power_fast(a, n, m) == power_mod(a, n, m), f"{a}^{n} mod {m}"
        print(f"m={m} OK")
    a, n, m = 123456789, 999999999, 987654321
    r = power_fast(a, n, m)
    print(f"{a}^{n} = {r} (mod {m})")
    assert r == power_mod(a, n, m)
    print()
#test2()


### ---------------------------------------------------------------------------
### 3. feladat: Rend
###
### Számítsuk ki egy adott 'a' egész szám rendjét modulo p (prímszám).

def order (a, p):
    pass #TODO

def test3 ():
    print("3. Rend")
    for p in [2, 3, 5, 7]:
        for a in range(1, p):
            n = order(a, p)
            print(f"ord_{p} {a} = {n}")
            assert power_mod(a, n, p) == 1
            assert n == multiplicative_order(mod(a, p))
    print()
#test3()


### ---------------------------------------------------------------------------
### 4. feladat: Diszkrét logaritmus
###
### Számítsuk ki a-nak a g-alapú diszkrét logaritmusát modulo p.

def dislog (a, g, p):
    pass #TODO

def test4 ():
    print("4. Diszkrét logaritmus")
    for (p,g) in [(2,1), (3,2), (5,2), (5,3), (7,3), (7,5), (11,2)]:
        for n in range(p-1):
            a = power_mod(g, n, p)
            #print(f"ind_{g} {a} = {n} (mod {p})")
            assert dislog(a, g, p) == n, f"dislog({a}, {g}, {p})"
    print("OK")
    p, g = 12345678923, 2
    a = 9718522932  # véletlen a-ra sokkal lassabb lenne
    n = dislog(a, g, p)
    print(f"ind_{g} {a} = {n} (mod {p})")
    assert power_mod(g, n, p) == a
    print()
#test4()

### Bónusz feladat (haladó, csak annak, aki már minden mással készen van):
### oldjuk meg a diszkrét logaritmust a "baby-step giant-step" algoritmussal is
### (lásd a PDF-et). (Ennek a tesztben más a-kra is hatékonynak kell lennie.)


### ---------------------------------------------------------------------------
### 5. feladat: Diffie–Hellman-kulcscsere

### a) Szimuláljuk a Diffie–Hellman-kulcscserét, azaz hajtsuk végre mindkét fél
### műveleteit, majd számítsuk ki a közös titkot mindkét módon.
### (A függvény nem ad vissza semmit, hanem kiírja a két fél közös titkát.)
def diffie_hellman (p, g):
    pass #TODO
    #print("Alíz:", ...)
    #print("Bob: ", ...)

### b) Törjük fel a Diffie–Hellman-kulcscserét a diszkrét logaritmussal.
### (Ez nyilván csak kisebb számokra fog működni).
### A függvény a nyilvánosan látható paramétereket kapja meg (p, g, g^a, g^b),
### és azokból kiszámítja a közös titkot.
def break_dh (p, g, ga, gb):
    pass #TODO

def test5 ():
    print("5. Diffie–Hellman-kulcscsere")
    print("a)")
    diffie_hellman(23, 5)
    diffie_hellman(12345678923, 5)
    common = break_dh(23, 5, 17, 14)  # jegyzet példája
    if common != None:
        print("b) Feltört titok:", common)
        assert common == 19
    print()
#test5()


### ---------------------------------------------------------------------------
### 6. feladat: Véletlen számok

### a) Implementáljuk a következő pszeudovéletlenszám-generátort:
###    xn := 48271^n * x0 mod 2147483647,
### ahol xn az n-ik generált szám, és x0 tetszőleges kezdőszám.
### A generálásnál mindig az előző (n-1-ik) értékből számítsuk ki a következő
### (n-ik) számot, az x0 és az n ismerete nélkül.

### x: az előző érték
def mod_rng (x):
    pass #TODO

### b) Mennyire "véletlenek" a fent előállított számok?
### Ideális esetben a generált számok minden bitje 50%-50% valószínűséggel lesz
### 1 vagy 0. Generáljunk 1000 véletlen számot (n=1-től 1000-ig) a fent megírt
### mod_rng() függvénnyel, és írjunk ki egy statisztikát a számok bitjeiről
### (kettes számrendszerbeli számjegyeiről), például:
###    0. bit: 500 (0), 500 (1)
###    1. bit: 491 (0), 509 (1)
###    ...
###    30. bit: 511 (0), 489 (1)
### (A kisebb számoknak, amelyeknek nincs 31 bitjük, a hiányzó bitjeit 0-nak
### tekintsük.)

def examine_rng ():
    x0 = 123456789
    pass #TODO

def test6 ():
    print("6. Véletlen számok")
    print("a)")
    x = 123456789 # x0
    for n in range(1, 11):
        x = mod_rng(x)
        print(f"x{n} = {x}")
    print("b)")
    examine_rng()
    print()
#test6()