### Congruences
### ===========


### ---------------------------------------------------------------------------
### Exercise 1: Simple counting
###
### How many prime numbers are there up to 2800000 which are congruent to 7
### modulo 235?

def congr_count ():
    pass #TODO

def test1 ():
    print("1. Simple counting")
    print(congr_count())
    print()
#test1()


### ---------------------------------------------------------------------------
### Exercise 2: Linear congruence
###
### Solve the linear congruence a*x ≡ b (mod m) for given a, b, m integers, as
### described below. Each result is a list, containing all solutions between
### 0 and m-1 (in increasing order). (Don't use Sage's solver functions.)

### a) Use brute force search.
def lincon_brute (a, b, m):
    pass #TODO

### b) Use the extended Euclidean algorithm.
def lincon_eucl (a, b, m):
    pass #TODO

def test2 ():
    print("2. Linear congruence")
    tests = [(3,5,8), (6,6,15), (12,9,18), (21,14,35), (100,40,260)]
    for fv in [lincon_brute, lincon_eucl]:
        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} is not a solution"
        tests.append((30517578125, 33729082272, 999999999999)) # only eucl
    print()
#test2()


### ---------------------------------------------------------------------------
### Exercise 3: Modular inverse
###
### Calculate the inverse of 'a' modulo 'm' (for the given integers a and m),
### using the methods given below. If 'a' is not invertible, then return None.

### a) Use brute force search.  (Don't search longer than necessary.)
def inv_brute (a, m):
    pass #TODO

### b) Use the extended Euclidean algorithm.
def inv_eucl (a, m):
    pass #TODO

def test3 ():
    print("3. Modular inverse")
    for fv in [inv_brute, inv_eucl]:
        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_eucl:
            a, m = 987654321, 79590490282399
            inv = fv(a, m)
            print(f"{fv.__name__}({a}, {m}) ==", inv)
            assert inv == inverse_mod(a, m)
    print()
#test3()


### ---------------------------------------------------------------------------
### Exercise 4: Bank account number
###
### The sub-exercises below are about the Hungarian bank account numbers, which
### are represented by the list of digits (of length 16 or 24), for example:
###    [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) Decide whether the given bank account number is correct (according to
### the checksum).
def ban_ok (ban):
    pass #TODO

### b)-c) Given a (potentially) incorrect bank account number and the index of
### the single incorrect digit (between 0 and 23), return the corrected number.
### Solve it in two different ways, as described below.
### You can assume that all other digits are correct.

### b) Use brute force search (i.e. a simple loop for the digit in question).
def ban_fix_1 (ban, j):
    pass #TODO

### c) Solve it using a linear congruence or modular inverse.
### (Don't use loops other than calculating the checksum once!)
def ban_fix_2 (ban, j):
    pass #TODO

def test4 ():
    print("4. Bank account number")
    def ban_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("good: ", ban_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("wrong:", ban_str(wrong_ban), "->", ban_ok(wrong_ban))
    fixed1 = ban_fix_1(wrong_ban, 6)
    if fixed1 != None:
        print(ban_str(wrong_ban), "->", ban_str(fixed1))
        assert ban_ok(fixed1), f"ban_ok({ban_str(fixed1)})"
    fixed2 = ban_fix_2(wrong_ban, 6)
    if fixed2 != None:
        print(ban_str(wrong_ban), "->", ban_str(fixed2))
        assert ban_ok(fixed2), f"ban_ok({ban_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({ban_str(ban)})"
            if fixed1: assert ban_fix_1(ban, i) == good_ban, f"ban_fix_1({ban_str(ban)}, {i})"
            if fixed2: assert ban_fix_2(ban, i) == good_ban, f"ban_fix_2({ban_str(ban)}, {i})"
        ban[i] = good_ban[i]
    print()
#test4()


### ---------------------------------------------------------------------------
### Exercise 5: Chinese remainder theorem
###
### Implement the Chinese remainder theorem (CRT) (see PDF, section 6)
### for two congruences:
###    x ≡ a (mod m)
###    x ≡ b (mod n)
### Return the pair (x, r), where x is the smallest nonnegative solution, and
### r is the modulus of the solution. If there is no solution, return None.
### (Don't use crt() or Sage's other equation solvers.)


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

def test5 ():
    print("5. Chinese remainder theorem")
    if chinese_rem(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 = chinese_rem(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, "not a solution"
            assert x == crt(a, b, m, n), "not the smallest solution"
            assert (x+r) % m == a and (x+r) % n == b, "r={r} is incorrect"
            for rr in divisors(r):
                assert r == rr or (x+rr) % m != a or (x+rr) % n != b, f"r={r} is too big"
    print()
#test5()