Define the intersection points of polynomials

Herc11 · 2013-07-22 05:33:22

true i think

bobbym · 2013-07-22 05:41:50

Here is another one:

We get x = 5, which corresponds to solving that equation over GF(19)

Herc11 · 2013-07-22 05:43:10

I verified it with the calculator. It seems right!

bobbym · 2013-07-22 05:43:59

I changed post #252, so please check again.

Herc11 · 2013-07-22 05:47:31

It is 135=2mod19 which is right. (Always I think..)

bobbym · 2013-07-22 05:57:35

Okay, then for the sake of argument because we have nothing else to go on let's assume Mathematica can solve your equations over the GF you want. This is a pragmatic decision, if we assume it can not we are done right here. Let's proceed with the assumption and see what the heck happens.

Herc11 · 2013-07-22 05:58:14

Ok!

bobbym · 2013-07-22 06:00:18

Now, I can continue to ask the remaining questions.

GF(p) what is p going to be? I would very much like to have a p smaller than 2^128. Is this possible?

Herc11 · 2013-07-22 06:02:15

Yes try a small prime number. I think if it is solvable for small p it will be solavble for larger p's..pick 113 i think it is prime

bobbym · 2013-07-22 06:05:56

This is what we agree on:

So the leading coefficients of each of the 4 given polynomials will be ∈ GF. The points given will have x's and y's that are ∈ GF. Now you are requiring the points of intersection of the 4 quadratics to also be ∈ GF?

A Gf(113) will be used.

Agreed?

Herc11 · 2013-07-22 06:09:23

Yes. I want to know if we can find the intersection points of the polynomial as syou didi wi th real numbers

bobbym · 2013-07-22 06:11:13

I understand the problem well enough to work on it. I am currently a little busy with 4 other problems and will start modifying the cubic code that I used to solve the other problems. This will take some time.

Herc11 · 2013-07-22 06:16:55

Ok!!!

bobbym · 2013-07-22 07:51:51

So far I have found it very difficult to even construct 4 quadratics and 2 points of intersection all of them over Z let alone GF(113).

Herc11 · 2013-07-22 07:53:11

why?

Last edited by Herc11 (2013-07-22 07:54:45)

bobbym · 2013-07-22 07:55:39

It is a little early to say. But it does suggest they are rare. That means that getting an answer to them in the required form is very rare.

Herc11 · 2013-07-22 07:57:25

If the set is small maybe is a good choce to use a bigger p.

Herc11 · 2013-07-22 08:03:07

You can use Newton Interpolation i.e the formulas for a that I have posted eralier to compute the polynomials.

What I mean is that you can preselect the common x_0 y_0 x_1 y_1 for the four polynomials. Then You can use the postedd formulas for recovering a_0 a_1. Then for each polynomial you can select a different x_3 y_3. Then by the posted formula again you can compute a_3.

After that tou will have 4 polynomials and the set of equations is ready.

The problem is to "pretend" that you do not know the 2 intersection points x_0x_1 y_0 y_1 and try to solve the previous system.

bobbym · 2013-07-22 08:09:53

I can do all that. The trouble is the answers are not coming back as integers let alone 1 - 113.

Herc11 · 2013-07-22 08:14:08

What do you mean?They have to return as elements. If not something is wrong...

bobbym · 2013-07-22 08:24:11

I think I have a method now that is working to generate the problems. I will go back to work on the solutions.

Half way through with it. I need a little sleep, see you later hopefully with a full solution.

bobbym · 2013-07-22 21:16:29

Hi;

I have 4 parabolas that intersect at two points. The leading coefficients are 5, 22 17, 29. I have 4 points on those 4 parabolas, 1 on each parabola.

They are:

(3,13), (3,47), (3,37), (3,61)

You can see that so far all the conditions have been met. Now I must calculate from this information the points of intersection modulo 112.

The first idea to solve it failed completely. I think I see what went wrong.

Herc11 · 2013-07-22 22:01:24

What went wrong?? mod113

Last edited by Herc11 (2013-07-22 22:02:03)

bobbym · 2013-07-22 22:10:52

That will be a problem when I get to that.

What went wrong first is the choice of points. You notice the x's are all 3. This caused the system to not have a unique solution. Why? I do not know! I will have to adjust the test problem to use all different or at least some different x's.

Herc11 · 2013-07-22 22:14:30

The choice of same x's would a problem if wou were solving the problem over real numbers?

Dιδ you used x=3 for creating the parabolas?

How did you construct the parabolas?Can you be sure that they have 2 intersection points? Are the intersection points known?

Last edited by Herc11 (2013-07-22 22:19:53)

Math Is Fun Forum

#251 2013-07-22 05:33:22

Re: Define the intersection points of polynomials

#252 2013-07-22 05:41:50

Re: Define the intersection points of polynomials

#253 2013-07-22 05:43:10

Re: Define the intersection points of polynomials

#254 2013-07-22 05:43:59

Re: Define the intersection points of polynomials

#255 2013-07-22 05:47:31

Re: Define the intersection points of polynomials

#256 2013-07-22 05:57:35

Re: Define the intersection points of polynomials

#257 2013-07-22 05:58:14

Re: Define the intersection points of polynomials

#258 2013-07-22 06:00:18

Re: Define the intersection points of polynomials

#259 2013-07-22 06:02:15

Re: Define the intersection points of polynomials

#260 2013-07-22 06:05:56

Re: Define the intersection points of polynomials

#261 2013-07-22 06:09:23

Re: Define the intersection points of polynomials

#262 2013-07-22 06:11:13

Re: Define the intersection points of polynomials

#263 2013-07-22 06:16:55

Re: Define the intersection points of polynomials

#264 2013-07-22 07:51:51

Re: Define the intersection points of polynomials

#265 2013-07-22 07:53:11

Re: Define the intersection points of polynomials

#266 2013-07-22 07:55:39

Re: Define the intersection points of polynomials

#267 2013-07-22 07:57:25

Re: Define the intersection points of polynomials

#268 2013-07-22 08:03:07

Re: Define the intersection points of polynomials

#269 2013-07-22 08:09:53

Re: Define the intersection points of polynomials

#270 2013-07-22 08:14:08

Re: Define the intersection points of polynomials

#271 2013-07-22 08:24:11

Re: Define the intersection points of polynomials

#272 2013-07-22 21:16:29

Re: Define the intersection points of polynomials

#273 2013-07-22 22:01:24

Re: Define the intersection points of polynomials

#274 2013-07-22 22:10:52

Re: Define the intersection points of polynomials

#275 2013-07-22 22:14:30

Re: Define the intersection points of polynomials

Board footer