iXvXP0iy

1Zx.<x> = ZZ[]
2n = 107
3d = 14
4q = 64
5
6def inv(f,p):
7    T = Zx.change_ring(Integers(p)).quotient(x^n-1)
8    x = Zx(lift(1 / T(f)))
9    return x
10
11def invert2(f,q):
12    assert q.is_power_of(2)
13    g = inv(f,2)
14    while True:
15        r = balancedmod(convolution(g,f),q)
16        if r == 1:
17            return g
18        g = balancedmod(convolution(g,2 - r),q)
19
20
21def convolution(f,g):
22    a = (f * g) % (x^n-1)
23    return a
24
25def balancedmod(f,q):
26    g = list(((f[i] + q//2) % q) - q//2 for i in range(n))
27    b = Zx(g)
28    return b
29
30def rpoly():
31    assert d <= n
32    result = n*[0]
33    for j in range(d):
34        while True:
35            r = randrange(n)
36            if not result[r]: break
37        result[r] = 1-2*randrange(2)
38    r = Zx(result)
39    return r
40
41
42
43
44def key():
45    flag = 1
46    while flag:
47        flag = 0
48        try:
49            f = rpoly()
50            f3 = inv(f,3)
51            fq = invert2(f,q)
52        except:
53            flag = 1
54    g = rpoly()
55    h = balancedmod(3 * convolution(fq,g),q)
56    secretkey = f,f3
57    return h,secretkey
58
59
60def rmessage():
61    result = list(randrange(3) - 1 for j in range(n))
62    r = Zx(result)
63    return r
64
65def enc(message,h):
66    r = rpoly()
67    balance = balancedmod(convolution(h,r) + message,q)
68    return balance
69
70
71def dec(ciphertext,secretkey):
72    f,f3 = secretkey
73    a = balancedmod(convolution(ciphertext,f),q)
74    balancedmod(convolution(a,f3),3)
75    return balance
76
77
78
79
80h, secretkey, = key()
81m = rmessage()
82c = enc(m, h)
83if m == dec(c, secretkey):
84    print " it 'working"
85else:
86    print "no it' s not working"