### Discrete logarithm
### ==================


### ---------------------------------------------------------------------------
### Exercise 1: Modular exponentiation
###
### Calculate a^n mod m using simple repeated modular multiplication
### (the "naive" way), but without calculating a^n as an integer.

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

def test1 ():
    print("1. Modular exponentiation")
    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()


### ---------------------------------------------------------------------------
### Exercise 2: Fast exponentiation
###
### Calculate a^n mod m using fast exponentiation.

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

def test2 ():
    print("2. Fast exponentiation")
    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()


### ---------------------------------------------------------------------------
### Exercise 3: Order
###
### Calculate the order of the given integer 'a' modulo p (where p is prime).

def order (a, p):
    pass #TODO

def test3 ():
    print("3. Order")
    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()


### ---------------------------------------------------------------------------
### Exercise 4: Discrete logarithm
###
### Calculate the discrete logarithm of 'a' to the base g modulo p.

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

def test4 ():
    print("4. Discrete logarithm")
    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  # different 'a' would be much slower
    n = dislog(a, g, p)
    print(f"ind_{g} {a} = {n} (mod {p})")
    assert power_mod(g, n, p) == a
    print()
#test4()

### Bonus exercise (advanced, only if you are ready with everything else):
### solve the discrete logarithm using the "baby-step giant-step" algorithm
### (see the PDF). (It should work efficiently for any 'a' in the test above.)


### ---------------------------------------------------------------------------
### Exercise 5: Diffie-Hellman key exchange

### a) Simulate the Diffie-Hellman key exchange, i.e. execute the steps of both
### participants, and calculate the common secret in both ways.
### (The function doesn't return anything, just prints the secret both ways.)
def diffie_hellman (p, g):
    pass #TODO
    #print("Alice:", ...)
    #print("Bob:  ", ...)

### b) Break the Diffie-Hellman key exchange using the discrete logarithm.
### (It will of course only work for small enough numbers).
### The function receives the publicly observable parameters (p, g, g^a, g^b),
### and calculates the common secret from them.
def break_dh (p, g, ga, gb):
    pass #TODO

def test5 ():
    print("5. Diffie-Hellman key exchange")
    print("a)")
    diffie_hellman(23, 5)
    diffie_hellman(12345678923, 5)
    common = break_dh(23, 5, 17, 14)  # example from the PDF
    if common != None:
        print("b) Broken secret:", common)
        assert common == 19
    print()
#test5()


### ---------------------------------------------------------------------------
### Exercise 6: Random numbers

### a) Implement the following pseudorandom number generator:
###    xn := 48271^n * x0 mod 2147483647,
### where xn is the n'th generated number, and x0 is the seed (an arbitrary
### initial number). The function mod_rng() must calculate the next number (xn)
### knowing only the previous number, but NOT x0 or n.

### x: the previous value
def mod_rng (x):
    pass #TODO

### b) How "random" are the generated numbers?
### Ideally, each bit of the generated numbers would be 1 or 0 with 50%-50%
### probability. Generate 1000 random numbers (from n=1 to 1000) using the
### above mod_rng(), and print statistics about the bits of the numbers
### (i.e. their digits in binary), for example:
###    Bit 0: 500 (0), 500 (1)
###    Bit 1: 491 (0), 509 (1)
###    ...
###    Bit 30: 511 (0), 489 (1)
### (Smaller numbers with less than 31 bits should be treated as if the missing
### bits were 0.)

def examine_rng ():
    x0 = 123456789
    pass #TODO

def test6 ():
    print("6. Random numbers")
    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()