You are not logged in.

- Topics: Active | Unanswered

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

true i think

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 106,382

Here is another one:

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

**In mathematics, you don't understand things. You just get used to them.****If it ain't broke, fix it until it is.****No great discovery was ever made without a bold guess. **

Offline

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

I verified it with the calculator. It seems right!

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 106,382

I changed post #252, so please check again.

**In mathematics, you don't understand things. You just get used to them.****If it ain't broke, fix it until it is.****No great discovery was ever made without a bold guess. **

Offline

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

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

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 106,382

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.

**In mathematics, you don't understand things. You just get used to them.****If it ain't broke, fix it until it is.****No great discovery was ever made without a bold guess. **

Offline

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

Ok!

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 106,382

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?

**In mathematics, you don't understand things. You just get used to them.****If it ain't broke, fix it until it is.****No great discovery was ever made without a bold guess. **

Offline

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

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

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 106,382

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?

**In mathematics, you don't understand things. You just get used to them.****If it ain't broke, fix it until it is.****No great discovery was ever made without a bold guess. **

Offline

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

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

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 106,382

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.

**In mathematics, you don't understand things. You just get used to them.****If it ain't broke, fix it until it is.****No great discovery was ever made without a bold guess. **

Offline

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

Ok!!!

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 106,382

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

**In mathematics, you don't understand things. You just get used to them.****If it ain't broke, fix it until it is.****No great discovery was ever made without a bold guess. **

Offline

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

why?

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

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 106,382

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.

**In mathematics, you don't understand things. You just get used to them.****If it ain't broke, fix it until it is.****No great discovery was ever made without a bold guess. **

Offline

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

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

Offline

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

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.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 106,382

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

**In mathematics, you don't understand things. You just get used to them.****If it ain't broke, fix it until it is.****No great discovery was ever made without a bold guess. **

Offline

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

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

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 106,382

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.

**In mathematics, you don't understand things. You just get used to them.****If it ain't broke, fix it until it is.****No great discovery was ever made without a bold guess. **

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 106,382

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.

**In mathematics, you don't understand things. You just get used to them.****If it ain't broke, fix it until it is.****No great discovery was ever made without a bold guess. **

Offline

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

What went wrong?? mod113

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

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 106,382

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.

**In mathematics, you don't understand things. You just get used to them.****If it ain't broke, fix it until it is.****No great discovery was ever made without a bold guess. **

Offline

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

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

Offline