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

You are not logged in.

#1 Re: Help Me ! » Define the intersection points of polynomials » 2013-07-24 23:08:20

Thanks again for your time.

I m telling you another one time that I am not sure If I can recover a known solution.

Ofcourse we can check it algebraically. You can not geometrically formulate Gfs. They have distinct elements etc...

Try to draw f(x) where x and f(x)  take values from  1,2,3,4,5,6,7. Will it be consistent?

#2 Re: Help Me ! » Define the intersection points of polynomials » 2013-07-24 22:57:06

First of all, I prove it for a system of 2 linear equations.

As for the 4 quadratics, I told you that I used Newton Interpolation to compute the coefficients of the polynomials. It is a basic problem of linear algebra (polynomial reconsruction.  I used two common points for all 4 quadratics. What does it mean common? That these are their intersection points. When the problem was defined over real numbers you solved it.

The problem is if you can find the solution in GFafter you know that there is a solution.
There can be no graphical illustration of the problem beacuse we work on GF not  on real numbers.

There are no lines that intercept only in our imagination.

If the system is not linear I can not compute roots etc..thats the problem!!!

#3 Re: Help Me ! » Define the intersection points of polynomials » 2013-07-24 22:38:15

In order to be sure that the system has  a solution I construt  the system of equations to have a common point  the x0 y0. i.e. I define the intersection point x0y0 and then I pretend that I do not know it..

That was the problem I posted yesterday. But in that problem the eq. were quadratics...So I used to construct it, two points x0x1 y0 y1. Then by knowing M1..M4 and the four unique X2 y2 for each polynomial andby pretending that you dont know the x0x1 y0 y1 you had to solve the system.
You said the system that hadn t got a solution in GF. As i have constructed the system I was sure that a solution existed.
Thats why I was sure that the system has a solution!!!! Because I knew the solution.

I was not sure If the solution can be found.

I said all that many times.

#4 Re: Help Me ! » Define the intersection points of polynomials » 2013-07-24 22:14:39

Hmmm. The equations were solved on GF 2^128. Want you try to solve it? i think that you can because you do not ser right the problem.

#6 Re: Help Me ! » Define the intersection points of polynomials » 2013-07-24 21:37:39

Ok for the set of linear equations that I said, I   solved it.

#7 Re: Help Me ! » Define the intersection points of polynomials » 2013-07-24 20:52:37

The first a_1 and the second a_1.

They are advanced in mathematics. The know that if theory is correct, numbers are never a problem.

Our problem is that we are not sure, we do not know the theory.

#8 Re: Help Me ! » Define the intersection points of polynomials » 2013-07-24 20:41:30

Ok. I understand that I can not give you clear answers because I also  do not understand many things.

I thought that you read my post where this set was described in detail and the solution is provided by another user user. This is a system of 2 linear equations. If we want to be mathematically correctly there is no geometrical representation of this problem in the GF.

I did not want to offend you, if I did.

#9 Re: Help Me ! » Define the intersection points of polynomials » 2013-07-24 20:21:46

I used the field 2^128 and also polynomial representation basis. Therefore, addition multiplication and division is not defined as it were on real numbers. I have tested it many times that these operations never return negative elements. It is not possible.

In math stack they all  said that the first problem where linear equation are empolyed, there is a solution on GF. Do you think that you can solve it?

My problem is that I dont have an algorithm to solve the second problem. I have the definitions of the operations but I

cannot  solve a system of 4 equations with 4 unknowns. I am not sure that there is a solution but I think tha there is. I do

I do not avoid any possibility but I think that believing that there is no solution is the easy but unhopefully the wrong way.

#10 Re: Help Me ! » Define the intersection points of polynomials » 2013-07-24 20:02:54

but not in the ways that the OP thinks it does

I thought that the filed plays a significant role to the solution of the system. And he says that it plays a role but not in the ways that I think.

There were many mistekes at the problem you tried to solve.

You chose negative integers that they do not exist in GF.
The operations returned non integers, which is not possible if the operations executed correctly.

you ve mixed real with GF.

In the problem where I provided you with a_0 a_1 a_2 and the intersection points etc. I used polynomial basis representation with a ceratin irreducoible polynomial.

You controlled the data as they were integers.

It was more than certain that no correct solution will ever be returned.

#12 Re: Help Me ! » Define the intersection points of polynomials » 2013-07-24 19:42:36

You read several comments. No I am not sure that I understood correctly what he wrote. But I think that I understood.

http://crypto.stackexchange.com/questions/9294/solve-a-system-of-non-linear-equations-over-gf

#13 Re: Help Me ! » Define the intersection points of polynomials » 2013-07-24 19:34:23

No. only one answer there was.

The author of this answer said that if the problem is constructed as I stated it can be solved for linear or even non linear systems in GF.

By the way, according to my calculations the system is always linear.

#14 Re: Help Me ! » Define the intersection points of polynomials » 2013-07-24 19:05:35

I didnt know that this information would be helpful. From my point of I retstated the same question in a way that would be more familiar to you.

""So far looking at what you posted elsewhere you kept much information from me. But that is water under the bridge.""

What was that helpful to you?

As the problem was set it surely has  a solution. I stated this many times. The problem is if there is a way to found the solution on GF.

"But what I do think is that if you can not find a solution in the reals then there is no solution in any other subset of the Reals."

This has no meaning as it is not the same system of equations. The latter system of equations is defined on GF so there is no relation to real.

#15 Re: Help Me ! » Define the intersection points of polynomials » 2013-07-24 08:05:03

Hi bobbym, the problem that you had solved (on real numbers) was linear?

#17 Re: Help Me ! » Define the intersection points of polynomials » 2013-07-24 05:26:34

I will try to transform it for the problem over gF

#19 Re: Help Me ! » Define the intersection points of polynomials » 2013-07-24 04:36:46

ok! thanks for your time...

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

#20 Re: Help Me ! » Define the intersection points of polynomials » 2013-07-24 04:07:11

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

#21 Re: Help Me ! » Define the intersection points of polynomials » 2013-07-24 00:45:13

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)..

#22 Re: Help Me ! » Define the intersection points of polynomials » 2013-07-24 00:36:20

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

and find the b's.

#23 Re: Help Me ! » Define the intersection points of polynomials » 2013-07-24 00:32:09

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.

#24 Re: Help Me ! » Define the intersection points of polynomials » 2013-07-24 00:15:24

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/

#25 Re: Help Me ! » Define the intersection points of polynomials » 2013-07-24 00:00:08

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.

Board footer

Powered by FluxBB