ffo.py/test.py at master · lducas/ffo.py · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
# ffo.py
# Public Domain
# Provided by Leo Ducas and Thomas Prest
# Reference implementation of algorithms proposed in
# [Fast Fourier Orthogonalization, Ducas and Prest]
# To be used for testing purposes only


import sys
import random
from numpy import array
from verif import create_verifier, verif_babai
from ffo_NaN import LDTree, ffBabai
from cyclo import embedding


k = 6
n = 2**k

print
print "testing ffo in the convolution ring R[x]/(x^64-1)"
print

x = [random.randint(-10,10) for i in range(n)]
f = array(x)
print "base: ", f
T = LDTree(f)
print "LD-Tree Constructed "
verifier = create_verifier(f)
print "Babai Verifier constructed (explicit QDR computation)"

print "Unit test ffBabai (1000 trials) ",

N = 1000
for a in range(1,N+1):
	c = array([random.uniform(-100,100) for i in range(n)])
	z = ffBabai(f,T,c)
	verif_babai(verifier, c, z)
	if ((10*a) % N == 0):
		print 100*a / N,"%" ,
		sys.stdout.flush()

print
print " Passed !"

print
print "testing ffo in the convolution ring R[x]/(x^32+1)"
print

x = [random.randint(-10,10) for i in range(n/2)]
f = embedding(array(x))
print "base: ", f
T = LDTree(f)
print "LD-Tree Constructed "
verifier = create_verifier(f)
print "Babai Verifier constructed (explicit QDR computation)"

print "Unit test ffBabai (1000 trials) ",

N = 1000
for a in range(1,N+1):
	c = array([random.uniform(-100,100) for i in range(n/2)])
	z = ffBabai(f,T,embedding(c))
	verif_babai(verifier, embedding(c), z)
	if ((10*a) % N == 0):
		print 100*a / N,"%" ,
		sys.stdout.flush()

print
print " Passed !"