Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#301 2013-07-23 22:54:29

Herc11
Member
Registered: 2013-06-19
Posts: 169

Re: Define the intersection points of polynomials

I thought so...

Offline

#302 2013-07-23 22:57:33

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 86,228

Re: Define the intersection points of polynomials

You could spend your life looking at it and never break the surface.

It appears that you have the equations as well as the leading coefficient. The quadratic looks like this

a2 x^2 + a1 x + a0, am I right?


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

#303 2013-07-23 23:03:26

Herc11
Member
Registered: 2013-06-19
Posts: 169

Re: Define the intersection points of polynomials

No, a0 a1 a2 are the newton coef. the formula tha associates the newton coef. with polynomial's coef is:

But I dont think that you need the above formula.

The only thing is to solve the set of the 4  a2's.

Last edited by Herc11 (2013-07-23 23:23:32)

Offline

#304 2013-07-23 23:23:36

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 86,228

Re: Define the intersection points of polynomials

Okay, running off the calculation now.

Unfortunately, I could not find any points of intersections that were integers, let alone GF(p). Please check the hexadecimal values you posted.


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

#305 2013-07-23 23:49:55

Herc11
Member
Registered: 2013-06-19
Posts: 169

Re: Define the intersection points of polynomials

Ok I ll chek it. But it is impossible if the paraneteres of the problem are set correctly to return non integer values.

Offline

#306 2013-07-23 23:51:30

Herc11
Member
Registered: 2013-06-19
Posts: 169

Re: Define the intersection points of polynomials

You used GF operations didnt you?

Offline

#307 2013-07-23 23:52:20

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 86,228

Re: Define the intersection points of polynomials

Why should the points of intersection of 4 quadratics be integers just because the coefficients are?


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

#308 2013-07-24 00:00:08

Herc11
Member
Registered: 2013-06-19
Posts: 169

Re: Define the intersection points of polynomials

Bec ause all operations are executed on a Galois Field. Operations defined on GF return results of GF. This means that will return an element of GF.

It is impossible to return something else. I think that  you do not set the problem correctly.

I told you that there are not integers. There are elements of GF.

Last edited by Herc11 (2013-07-24 00:00:59)

Offline

#309 2013-07-24 00:07:44

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 86,228

Re: Define the intersection points of polynomials

The coefficients have to be numbers do they not? A GF is just a subset of N as far as we can compute them. remember they must be coefficients and x y coordinates. It is true that all simple operations like + - / * might be closed in the GF but intersections of quadratics is not a simple operation. It is easy to find 4 quadratics with coefficients like you want and a point on each like you want that do not have 2 points of intersection whose x y coordinates are even integers, let alone Gf(p). This proves that the GF is not closed under the intersection of the 4 quadratics.


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

#310 2013-07-24 00:15:24

Herc11
Member
Registered: 2013-06-19
Posts: 169

Re: Define the intersection points of polynomials

Coefficients must be GF elements. The set is defined on a GF, there is nothing else than GF. Only GF elements do exist for our problem.

See post #295. The 4 polynomials that I constructed have in common the intersection points x0y0 x1y1 and the x2y2 is different for each polynomial. Thus, I have preset and thus I am sure that their intersection points exist and they are the x0y0 x1y1.

When you set the problem you know a_2 for each polynomial and x2_y2 and you have to discover the x0 y0 I gave you.

I am not sure that you can find x0y0 x1y1 but it is simpossible if the operations are executed correctly non GF elements to be returned.

http://infoshako.sk.tsukuba.ac.jp/jcca/GaloisField/

Offline

#311 2013-07-24 00:19:48

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 86,228

Re: Define the intersection points of polynomials

I see no reason that the points of intersection have to be GF elements or any other type of elements.

The 4 polynomials that I constructed have in common the intersection points x0y0 x1y1 and the x2y2

What polynomials? Please produce your four polynomials and show that they have 2 points of intersection with the x's and y coordinates being GF elements.


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

#312 2013-07-24 00:32:09

Herc11
Member
Registered: 2013-06-19
Posts: 169

Re: Define the intersection points of polynomials

In post #295 I wrote 4 sets of coef. a0 a1 a2.  Each set of Newton coef. define a polynomial.

x0 x1 y0 y1 a0 and a1 are common to all of them. So x0 x1 y0 y1 are the intersection points as they are common to all polynomials.


a2 x2 y2 are unique for each polynomial.
All the coefficients are generated by Newton Interpolation based on x0 x1 y0 y1 x2 y2.

Offline

#313 2013-07-24 00:36:20

Herc11
Member
Registered: 2013-06-19
Posts: 169

Re: Define the intersection points of polynomials

If you want to recover the polynomials in the form of #303 you can compute:

and find the b's.

Last edited by Herc11 (2013-07-24 00:36:41)

Offline

#314 2013-07-24 00:41:08

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 86,228

Re: Define the intersection points of polynomials

That is what I was asking before.

Okay, I will do that and check to see whether that actually intersects at the points you say.

Right now I am napping, see you later.


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

#315 2013-07-24 00:45:13

Herc11
Member
Registered: 2013-06-19
Posts: 169

Re: Define the intersection points of polynomials

It is sure that they intercept at those points because the way that the set was constructed. The keypoint is if we can find the solution of this set (which in this case is known to us)..

Offline

#316 2013-07-24 03:26:01

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 86,228

Re: Define the intersection points of polynomials

For the first of the 4 quadratics:

b0 = 3532013428986237192873119375732903841826161800807175630263233579248271193664082785199313240683451908515944502746

b1=-410850838489261385759305566804597381684932406009429767177788799531275112939

b2 =11513183104216305498486345940371433157

b0 and b1 are obviously not members of GF(p). What do you want to do?


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

#317 2013-07-24 04:07:11

Herc11
Member
Registered: 2013-06-19
Posts: 169

Re: Define the intersection points of polynomials

Ok. Now it is sure that the operations are not well defined. The elements that I gave you are in polynomial basis. Addition and Substraction on GF2^128 are the same operation and it is acomplished by xoring the elements. e.g. 0x78(XOR)0x5=0x7d. There is no way the result to be negative.

I cant explaint you the GF theory and there is the problem.

This is a very good start http://www.dragonwins.com/domains/getteched/crypto/polynomial_arithmetic_in_gf%28p%5En%29.htm

Last edited by Herc11 (2013-07-24 04:11:48)

Offline

#318 2013-07-24 04:16:07

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 86,228

Re: Define the intersection points of polynomials

Hi;

Okay, then you might try here. They might know

http://math.stackexchange.com/

Or if it is for research you might consider acquiring Mathematica for yourself then you would be able to compute the answer for yourself.


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

#319 2013-07-24 04:36:46

Herc11
Member
Registered: 2013-06-19
Posts: 169

Re: Define the intersection points of polynomials

ok! thanks for your time...

Have you got the algorithm for solving the set of equations on reals?

Offline

#320 2013-07-24 04:43:56

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 86,228

Re: Define the intersection points of polynomials

Yes, they can solved over Reals.


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

#321 2013-07-24 04:52:40

Herc11
Member
Registered: 2013-06-19
Posts: 169

Re: Define the intersection points of polynomials

Can you give me the code?

Offline

#322 2013-07-24 05:23:37

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 86,228

Re: Define the intersection points of polynomials

May I ask what you plan to do with it?


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

#323 2013-07-24 05:26:34

Herc11
Member
Registered: 2013-06-19
Posts: 169

Re: Define the intersection points of polynomials

I will try to transform it for the problem over gF

Offline

#324 2013-07-24 05:32:15

bobbym
Administrator
From: Bumpkinland
Registered: 2009-04-12
Posts: 86,228

Re: Define the intersection points of polynomials

I have destroyed the code already and I am sorry but I am unable to recreate it.

It was written in Mathematica and it is extremely unlikely that it can be converted into any other language.


In mathematics, you don't understand things. You just get used to them.
Of course that result can be rigorously obtained, but who cares?
Combinatorics is Algebra and Algebra is Combinatorics.

Offline

#325 2013-07-24 05:40:14

Herc11
Member
Registered: 2013-06-19
Posts: 169

Re: Define the intersection points of polynomials

ok!

Offline

Board footer

Powered by FluxBB