uu3EZK88

1def balancedmod(f,q,n):
2    g = list(((f[i] + q//2) % q) - q//2 for i in range(n))  
3    return Zx(g)
4
5def randomMessage(n):
6    result = list(randrange(3) - 1 for j in range(n))
7    return Zx(result)
8def invertmodprime(f,p,n):
9    T = Zx.change_ring(Integers(p)).quotient(x^n-1)
10    return Zx(lift(1 / T(f)))
11def invertmodpowerof2(f,q,n):
12    assert q.is_power_of(2)
13    g = invertmodprime(f,2,n)
14    while True:
15        r = balancedmod(convolution(g,f,n),q,n)
16        if r == 1: return g
17        g = balancedmod(convolution(g,2 - r,n),q,n)
18
19
20def convolution(f,g,n):
21      return (f * g) % (x^n-1)
22
23
24def randompoly(n, d):
25    assert d <= n
26    result = n*[0]
27    for j in range(d):
28        while True:
29            r = randrange(n)
30            if not result[r]: break
31        result[r] = 1-2*randrange(2)
32    return Zx(result)
33    
34def encrypt(message, publickey, n, d, q):
35    r = randompoly(n,d)
36    return balancedmod(convolution(publickey,r,n) + message, q,n)
37
38def decrypt(ciphertext,secretkey,n):
39    f,f3 = secretkey
40    a = balancedmod(convolution(ciphertext,f,n),q,n)
41    return balancedmod(convolution(a,f3,n),3,n)
42
43def keypair(n,d,q):
44    Zx.<x> = ZZ[]
45    while True:
46        try:
47            f = randompoly(n,d)
48            f3 = invertmodprime(f,3,n)
49            fq = invertmodpowerof2(f,q,n)
50            break
51        except Exception as e:
52            pass
53    g = randompoly(n, d)
54    publickey = balancedmod(3 * convolution(fq,g,n),q,n)
55    secretkey = f,f3
56    return publickey,secretkey
57
58
59
60
61n = 743
62d = 495
63q = 2048
64for tests in range(10):
65    publickey,secretkey = keypair(n,d,q)
66    m = randomMessage(n)
67    c = encrypt(m,publickey,n,d,q)
68    print m == decrypt(c,secretkey,n)