Math Is Fun Forum

Lehona

Member

Registered: 2016-10-22

Posts: 16

Lagrange Interpolation in a finite Field

As part of my bachelor, I'm currently working on a presentation on this paper:

https://eprint.iacr.org/2016/539/20160531:151703

You probably don't need to look at the paper, because the important part (the one I don't quite understand) is here:

If I'm not mistaken, the interpolation polynomial is a closed form for

(choosing the one corresponding to k). Note: For some reason LaTeX doesn't like my apostrophe, so I will just leave it out.

Now, when I actually try to compute the corresponding values using the polynomials, I don't get the correct results. The first column is obviously correct - all these polynomials map 0 to 0. Let's look at k=0, so the first row.
1 is, even in this representation, simply 1, so the polynomial evaluates to 15, right?
I'm not quite sure how to interpret that number, but any way I've tried has lead to a solution that does not equal 5. If I interpret this as a member of GF(2³), I get

Which obviously doesn't equal 5.

I'm really at a loss here, as these polynomials don't seem to form any relation with the given table?

Help will be appreciated,
Lehona

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Lagrange Interpolation in a finite Field

Hi;

What is figure 4b?

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Lehona

Member

Registered: 2016-10-22

Posts: 16

Re: Lagrange Interpolation in a finite Field

It shouldn't have anything to do with the question though, which I think is a much more fundamental misunderstanding on my part.

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Lagrange Interpolation in a finite Field

I'm really at a loss here, as these polynomials don't seem to form any relation with the given table?

I do not see the relationship either...

Do you have any example of how those interpolating polynomials were formed? What was the data?

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Lehona

Member

Registered: 2016-10-22

Posts: 16

Re: Lagrange Interpolation in a finite Field

I do not see the relationship either...

Do you have any example of how those interpolating polynomials were formed? What was the data?

Well, the data is right there in the table?

(The first value corresponds to x=0, the second one to x=1, ...)

Given that this is GF(2³), there are no more possible data points, as x is inbetween 0 and 7.

Edit: For k=3 and k=4 

yet the polynomials evaluate to 20 and 18 respectively... Something fishy seems to be going on here.

Last edited by Lehona (2016-10-22 10:23:32)

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Lagrange Interpolation in a finite Field

I was afraid you would say that. It looks like the coefficients have been reduced by  mod 8? Unfortunately, I do not remember how to interpolate with a mod. I am reading up on it but in the meantime have you tried the SE?

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Lehona

Member

Registered: 2016-10-22

Posts: 16

Re: Lagrange Interpolation in a finite Field

Note my edit.

I assume SE means stackexchange? I have not, but I will for sure.

Even if they are reduced, I don't think that should change anything (after all, the congruence is what makes modular arithmetic so useful).

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Lagrange Interpolation in a finite Field

Yes, MathS.E. might be able to help.

I agree, I do not know what is going on there.

Please post the link when you post there, I would like to follow the discussion and welcome to the forum.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Lehona

Member

Registered: 2016-10-22

Posts: 16

Re: Lagrange Interpolation in a finite Field

/u/ImYourWenis was able to decipher the problem: The notation used in the paper is just really unintuitive!

This really comes from mixing up the polynomial and elements of GF(2³) (To any aspiring authors out there: Don't use x for both!).
Anyway, I'm glad it's clearing up, because that was really giving me a bad headache.

Last edited by Lehona (2016-10-22 13:02:50)

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Lagrange Interpolation in a finite Field

Hi;

Thanks for the link.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.