import math
import random

from math import *

def rozklad(x):
    if x<=0:
        return 0
    i=2
    e=floor(sqrt(x))
    r=[] #używana jest tablica (lista), nie bepośrednie wypisywanie
    while i<=e:
        if x%i==0:
            r.append(i)
            x/=i
            e=floor(sqrt(x))
        else:
            i+=1
    if x>1: r.append(x)
    r = list(dict.fromkeys(r))
    return r


print(rozklad(73))



def fme(a, k, n):

    b = bin(k)[2:] # list of bits
    m = len(b)
    r = 1 # result
    x = a % n

    for i in range(m - 1, -1, -1):
        if b[i] == '1':
            r = r * x % n

        x **= 2
        x  %= n

    return r


def calc_r(n, fermat_results):
    for r in range(1, n-1):
            good = True
            for j in fermat_results:
               if(fme(r,int((n-1)/j),n) == 1):
                   good = False
                   break
            if(good):
                return r

def generate_key(n):
    if rozklad(n)==[n]:
        fermat_results=rozklad(n-1)
        print("ferm results: "+ str(fermat_results))
        r = calc_r(n,fermat_results)
        print(r)
        #k = random.randint(1, n-1)
        k = 6739
        a = fme(r,k,n)
        print("a: ", a," r: ",r," k: ",k)
        return [n,r,a,k]

    else:
        print("n musi być liczbą pierwszą")

def encode(t,n,r,a):
    print("a",str(a))
    #j = random.randint(1, n-1)
    j=34310
    print("j: ",j)
    c1 = fme(r,j,n)
    c2 = ((t%n)* (fme(a,j,n)))%n
    return c1,c2

def decode(c1,c2,n,k):
    print(c1,n)
    print(fme(c1,n-1-k,n))
    return  ((c2%n)*(fme(c1,n-1-k,n)))%n





n = 37813
key = generate_key(n)
print("key")
print(key)
message = int(300)
secret1, secret2 = encode(message,key[0],key[1],key[2])

print("encoded message : "+ str(secret1),str(secret2))
decoded = decode(secret1,secret2,key[0],key[3])
print("decoded message : " + str(decoded))