ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Tue, 01 Dec 2015 01:21:35 +0100Fast evaluation of big polynomialshttps://ask.sagemath.org/question/30971/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 YouSun, 22 Nov 2015 23:15:59 +0100https://ask.sagemath.org/question/30971/fast-evaluation-of-big-polynomials/Comment by slelievre for <p>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:</p>
<pre><code>values = [0, 1, 1, 0, ... , 1]
polynomial = x1x45x12x47x125x47x214x255 + ... + x3x25x32x47x122x47x234x250
tmp = polynomial(*values)
</code></pre>
<p>The problem is that it lasts too long.
Is there some faster way?
Thank You</p>
https://ask.sagemath.org/question/30971/fast-evaluation-of-big-polynomials/?comment=31002#post-id-31002Please 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.Tue, 24 Nov 2015 09:00:47 +0100https://ask.sagemath.org/question/30971/fast-evaluation-of-big-polynomials/?comment=31002#post-id-31002Comment by Pro for <p>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:</p>
<pre><code>values = [0, 1, 1, 0, ... , 1]
polynomial = x1x45x12x47x125x47x214x255 + ... + x3x25x32x47x122x47x234x250
tmp = polynomial(*values)
</code></pre>
<p>The problem is that it lasts too long.
Is there some faster way?
Thank You</p>
https://ask.sagemath.org/question/30971/fast-evaluation-of-big-polynomials/?comment=31068#post-id-31068OK.
Here is exmple http://pastebin.com/5i4g5RRV
I added some comments. There are couple of functions and main. Interesting part is in function BlackBox()Wed, 25 Nov 2015 22:02:59 +0100https://ask.sagemath.org/question/30971/fast-evaluation-of-big-polynomials/?comment=31068#post-id-31068Comment by Pro for <p>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:</p>
<pre><code>values = [0, 1, 1, 0, ... , 1]
polynomial = x1x45x12x47x125x47x214x255 + ... + x3x25x32x47x122x47x234x250
tmp = polynomial(*values)
</code></pre>
<p>The problem is that it lasts too long.
Is there some faster way?
Thank You</p>
https://ask.sagemath.org/question/30971/fast-evaluation-of-big-polynomials/?comment=31107#post-id-31107OK.
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?Fri, 27 Nov 2015 19:02:32 +0100https://ask.sagemath.org/question/30971/fast-evaluation-of-big-polynomials/?comment=31107#post-id-31107Answer by tmonteil for <p>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:</p>
<pre><code>values = [0, 1, 1, 0, ... , 1]
polynomial = x1x45x12x47x125x47x214x255 + ... + x3x25x32x47x122x47x234x250
tmp = polynomial(*values)
</code></pre>
<p>The problem is that it lasts too long.
Is there some faster way?
Thank You</p>
https://ask.sagemath.org/question/30971/fast-evaluation-of-big-polynomials/?answer=30973#post-id-30973If 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 ?
Sun, 22 Nov 2015 23:32:13 +0100https://ask.sagemath.org/question/30971/fast-evaluation-of-big-polynomials/?answer=30973#post-id-30973Comment by Pro for <p>If i do the following, on a 5-year old laptop i got:</p>
<pre><code>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
</code></pre>
<p>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 ?</p>
https://ask.sagemath.org/question/30971/fast-evaluation-of-big-polynomials/?comment=30977#post-id-30977Polynomial that I need have to have far more terms.
Try
P = R.random_element(degree=8, terms=+infinity)Mon, 23 Nov 2015 00:12:48 +0100https://ask.sagemath.org/question/30971/fast-evaluation-of-big-polynomials/?comment=30977#post-id-30977Comment by tmonteil for <p>If i do the following, on a 5-year old laptop i got:</p>
<pre><code>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
</code></pre>
<p>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 ?</p>
https://ask.sagemath.org/question/30971/fast-evaluation-of-big-polynomials/?comment=30983#post-id-30983This 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 ?Mon, 23 Nov 2015 12:23:27 +0100https://ask.sagemath.org/question/30971/fast-evaluation-of-big-polynomials/?comment=30983#post-id-30983Comment by tmonteil for <p>If i do the following, on a 5-year old laptop i got:</p>
<pre><code>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
</code></pre>
<p>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 ?</p>
https://ask.sagemath.org/question/30971/fast-evaluation-of-big-polynomials/?comment=30984#post-id-30984With 10000 terms, i got timings of `77.4 ms`.Mon, 23 Nov 2015 12:33:49 +0100https://ask.sagemath.org/question/30971/fast-evaluation-of-big-polynomials/?comment=30984#post-id-30984Comment by Pro for <p>If i do the following, on a 5-year old laptop i got:</p>
<pre><code>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
</code></pre>
<p>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 ?</p>
https://ask.sagemath.org/question/30971/fast-evaluation-of-big-polynomials/?comment=31069#post-id-31069Example added under previous commentWed, 25 Nov 2015 22:03:26 +0100https://ask.sagemath.org/question/30971/fast-evaluation-of-big-polynomials/?comment=31069#post-id-31069Comment by Pro for <p>If i do the following, on a 5-year old laptop i got:</p>
<pre><code>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
</code></pre>
<p>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 ?</p>
https://ask.sagemath.org/question/30971/fast-evaluation-of-big-polynomials/?comment=31108#post-id-31108Better exaple added. Can U help me?Fri, 27 Nov 2015 19:04:16 +0100https://ask.sagemath.org/question/30971/fast-evaluation-of-big-polynomials/?comment=31108#post-id-31108Answer by A.P. for <p>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:</p>
<pre><code>values = [0, 1, 1, 0, ... , 1]
polynomial = x1x45x12x47x125x47x214x255 + ... + x3x25x32x47x122x47x234x250
tmp = polynomial(*values)
</code></pre>
<p>The problem is that it lasts too long.
Is there some faster way?
Thank You</p>
https://ask.sagemath.org/question/30971/fast-evaluation-of-big-polynomials/?answer=31218#post-id-31218 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.Tue, 01 Dec 2015 01:21:35 +0100https://ask.sagemath.org/question/30971/fast-evaluation-of-big-polynomials/?answer=31218#post-id-31218