# Fast evaluation of big polynomials

Hello. I am working on my Master thesis in cryptography where i need evaluate 256 really big boolean polynomials of 256 variables of degree 8. I use this kind of evaluation:

values = [0, 1, 1, 0, ... , 1]

polynomial = x1x45x12x47x125x47x214x255 + ... + x3x25x32x47x122x47x234x250

tmp = polynomial(*values)


The problem is that it lasts too long. Is there some faster way? Thank You

edit retag close merge delete

Please provide an actual example, and an actual timing. If it is too long to fit here, provide a link. For example, you could create a worksheet in a SageMathCloud project at https://cloud.sagemath.com, make the worksheet public, and provide a link to that worksheet.

OK. Here is exmple http://pastebin.com/5i4g5RRV I added some comments. There are couple of functions and main. Interesting part is in function BlackBox()

OK. That example is too complicated so I will try to simplified it.

R = BooleanPolynomialRing(256,'x')
polynomials = []
for _ in range(0,256):
polynomial = R.random_element(degree=8,terms=+infinity)
polynomials.append(polynomial)
output = 0
for i in range(0,256):
input = random_vector(GF(2), 256)
#--------------------This is problematic part------------------------------
output ^= polynomials[i](*input)
#-----------------------------------------------------------------------------------


Is there some other way or library?

Sort by » oldest newest most voted

If i do the following, on a 5-year old laptop i got:

sage: R = BooleanPolynomialRing(256,'x')
sage: P = R.random_element(degree=8, terms=100)
sage: L = [ZZ.random_element(2) for _ in range(256)]
sage: %timeit P(*L)
1000 loops, best of 3: 988 µs per loop


Which seems not so long, especially if you only have 256 polynomials to test. So, could you please be more precise on how you constructed your polynomials, what are your timings, and which timings do you expect ?

more

Polynomial that I need have to have far more terms. Try P = R.random_element(degree=8, terms=+infinity)

This is exactly why you should provide a more precise example, otherwise there is no way to know where the problem comes from, if any. Could you at lease tell how many terms do you have ?

With 10000 terms, i got timings of 77.4 ms.

The problem with the code sample you posted in your second comment isn't the part you highlighted, but the first loop, i.e. the generation of the polynomials.

Indeed, on my 5 year old Intel Core i5 2500K I get

sage: R = BooleanPolynomialRing(256,'x')
sage: %timeit R.random_element(degree=8,terms=10)
100 loops, best of 3: 11.3 ms per loop
sage: %timeit R.random_element(degree=8,terms=100)
10 loops, best of 3: 112 ms per loop
sage: %timeit R.random_element(degree=8,terms=1000)
1 loops, best of 3: 1.12 s per loop
sage: %timeit R.random_element(degree=8,terms=10000)
1 loops, best of 3: 11.3 s per loop
sage: %timeit R.random_element(degree=8,terms=100000)
1 loops, best of 3: 1min 52s per loop


which suggests that the time to generate a random polynomial of degree at most $8$ in $256$ variables scales linearly with the number of terms. Now, the total number of monomials of degree at most $8$ is

$$\sum_{k=0}^8 {{256}\choose{k}} = 423203101008289$$

(which I computed with sum(map(lambda k: binomial(256,k), range(0,9)))), thus the time needed to generate one polynomial with R.random_element(degree=8,terms=+infinity) should be

sage: t = 423203101008289/1000 * 1.12 * s
sage: t.convert(units.time.year)
15030.0441758398*year


On the other hand, you could try to speed this up with the choose_degree=True option, which helps a little bit

sage: %timeit R.random_element(degree=8, terms=1000, choose_degree=True)
10 loops, best of 3: 47.1 ms per loop
sage: %timeit R.random_element(degree=8, terms=10000, choose_degree=True)
1 loops, best of 3: 523 ms per loop
sage: %timeit R.random_element(degree=8, terms=100000, choose_degree=True)
1 loops, best of 3: 6.66 s per loop
sage: %timeit R.random_element(degree=8, terms=1000000, choose_degree=True)
1 loops, best of 3: 1min 28s per loop


although I almost ran out of my 8 GB of RAM with the last one, so unless you have access to lots of memory it is unlikely that you would be able to store the result of R.random_element(degree=8,terms=+infinity) even if you could compute it in a reasonable time, let alone $256$ of those...

Final note: If you don't need to use your polynomials more than once, you could try to directly generate their evaluation at some given point, although I fear that won't help much. Anyway, since this is for your master thesis I suggest you bring the problem up with your advisor.

more