First time here? Check out the FAQ!

Ask Your Question
0

Partial evaluation of a MV Polynomial.

asked 3 years ago

cryptoqs gravatar image

updated 3 years ago

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?

Preview: (hide)

1 Answer

Sort by » oldest newest most voted
0

answered 3 years ago

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,

Preview: (hide)
link

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 ( 3 years ago )

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 ( 3 years ago )

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 ( 3 years ago )

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

Emmanuel Charpentier gravatar imageEmmanuel Charpentier ( 3 years ago )

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: 3 years ago

Seen: 327 times

Last updated: Mar 05 '22