Ask Your Question
1

Fast evaluation of big polynomials

asked 2015-11-22 16:15:59 -0500

Pro gravatar image

updated 2015-11-22 16:23:22 -0500

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 flag offensive close merge delete

Comments

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.

slelievre gravatar imageslelievre ( 2015-11-24 02:00:47 -0500 )edit

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()

Pro gravatar imagePro ( 2015-11-25 15:02:59 -0500 )edit

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?

Pro gravatar imagePro ( 2015-11-27 12:02:32 -0500 )edit

2 answers

Sort by » oldest newest most voted
2

answered 2015-11-22 16:32:13 -0500

tmonteil gravatar image

updated 2015-11-22 16:33:22 -0500

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 ?

edit flag offensive delete link more

Comments

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

Pro gravatar imagePro ( 2015-11-22 17:12:48 -0500 )edit

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 ?

tmonteil gravatar imagetmonteil ( 2015-11-23 05:23:27 -0500 )edit

With 10000 terms, i got timings of 77.4 ms.

tmonteil gravatar imagetmonteil ( 2015-11-23 05:33:49 -0500 )edit

Example added under previous comment

Pro gravatar imagePro ( 2015-11-25 15:03:26 -0500 )edit

Better exaple added. Can U help me?

Pro gravatar imagePro ( 2015-11-27 12:04:16 -0500 )edit
1

answered 2015-11-30 18:21:35 -0500

A.P. gravatar image

updated 2015-11-30 18:29:37 -0500

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.

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2015-11-22 16:15:59 -0500

Seen: 246 times

Last updated: Nov 30 '15