Ask Your Question
0

Partial evaluation of a MV Polynomial.

asked 2022-03-05 15:29:56 +0200

cryptoqs gravatar image

updated 2022-03-05 18:19:54 +0200

Emmanuel Charpentier gravatar image

I have a polynomial defined as:

q = next_prime(2^128)
P.< x1, x2, x3, x4, x5> = GF(q)[]
p = (x1*x2) + (x3*x4)

I would like to obtain the resulting polynomial by partially evaluating by some variables.

Example partial polynomial p' generated by evaluating p at x2 = 2:

p' = (2*x1) + (x3*x4)

Is there a way to accomplish this?

edit retag flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted
0

answered 2022-03-05 18:17:26 +0200

Emmanuel Charpentier gravatar image

Simple:

sage: q = next_prime(2^128)
sage: p = (x1*x2) + (x3*x4)
sage: p(x2=2)
x3*x4 + 2*x1

But note that :

sage: p.subs(x2==2)
x1*x2 + x3*x4

doesn't work.

HTH,

edit flag offensive delete link more

Comments

Thanks! I actually did p(x2=1) and got 0 as a result and thought it was wrong, it was actually working. However, I still can not evaluate the resulting polynomial with one less variable. It says the length is not correct

cryptoqs gravatar imagecryptoqs ( 2022-03-05 18:48:26 +0200 )edit

Alright, after working on it a little bit, I think that this behaviour is not implemented correctly. For p(x1, x2, x3) = x1*x2 + x3, if we evaluate it at x2 =0. The resulting object should be p'(x1, x3) = x3. However, what we obtain is p'(x3) = x3. The term x1 disappearing shouldn't mean a polynomial doesn't have that variable as an input. Is there a reason behind this?

cryptoqs gravatar imagecryptoqs ( 2022-03-05 20:44:10 +0200 )edit

The term x1 disappearing shouldn't mean a polynomial doesn't have that variable as an input.

Nothing "disappears" :

sage: p=x1*x2+x3
sage: p(x2=0)
x3
sage: p(x2=0)(x1=3)
x3
sage: p(x2=0, x1=3)
x3
sage: p(x4=17)
x1*x2 + x3

Any polynomial element of P can be evaluated for any value of any P coefficient, whether it appears explicitly in the polynomial or not. Furthermore :

sage: p(x2=3*x1-2*x4)
3*x1^2 + 340282366920938463463374607431768211505*x1*x4 + x3

As this latter example shows, integer constants are coerced into elements of the base ring... In other words :

sage: p(x2=0, x1=3).parent()
Multivariate Polynomial Ring in x1, x2, x3, x4, x5 over Finite Field of size 340282366920938463463374607431768211507

HTH,

Emmanuel Charpentier gravatar imageEmmanuel Charpentier ( 2022-03-05 21:13:04 +0200 )edit

I strongly recommend reading this book, freely available...

Emmanuel Charpentier gravatar imageEmmanuel Charpentier ( 2022-03-05 21:19:53 +0200 )edit

Your Answer

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

Add Answer

Question Tools

Stats

Asked: 2022-03-05 15:29:56 +0200

Seen: 171 times

Last updated: Mar 05 '22