Can Cryptographic Methods Help Solve Quadratic Diophantine Equations?

[Math100]

Homework Statement

Solve the equation: x^2-55y-26=0.

Relevant Equations

None.

I know that the answer is x=46, y=38. Because 46^2=2116 and 55*38=2090, and 2116-2090=26.
But the question is, how to find out x and y? I just cannot think of a way to solve this type of problem. If this equation only has one unknown variable, then I would know how to solve for it. But this equation has two.

 

[fresh_42]

... or $(9,1),(24,10),(31,17)$ and infinitely many other integer solutions, and infinitely many real solutions, since its graph is a parabola.

This shows that there is a massive lack of information, if only $(46,38)$ is considered a solution.

 

[sysprog]

@fresh_42 $-$ if that's really the homework statement, then couldn't @Math100 present, along with an explanation, something like this?

 

[MidgetDwarf]

Homework Statement:: Solve the equation: x^2-55y-26=0.
Relevant Equations:: None.

I know that the answer is x=46, y=38. Because 46^2=2116 and 55*38=2090, and 2116-2090=26.
But the question is, how to find out x and y? I just cannot think of a way to solve this type of problem. If this equation only has one unknown variable, then I would know how to solve for it. But this equation has two.

There are many ways. The simplest, by simplest I mean, not using calculus and above. Is to solve the equation you have for y, then complete the square, so that you graph/visualize the parabola.

You can also find the x- intercept (set y=0), then solve for x.

But as Fresh pointed out the possible integer solutions (this is a very interesting topic in mathematics). You have not given the full problem statement, so any further information provided would be mute. Can you please write the full statement as it appears in the book/worksheet or wherever you got the problem from.

 

[Math100]

x^2 \equiv 26 (mod 55)

 

[Math100]

I was trying to solve this square congruence equation, and that's where x^2-55 y-26=0 came from.

 

[MidgetDwarf]

I was trying to solve this square congruence equation, and that's where x^2-55 y-26=0 came from.

Yes, but if you did not mention that, then it would be impossible to help!

 

[Mark44]

Yes, but if you did not mention that, then it would be impossible to help!

Amen to that!

@Math100, if you post a problem you want help with, you need to make more of an effort to provide us with all of the information. The equation you posted, as already mentioned, has an infinite number of real number solutions -- every point on the parabola it represents. You didn't mention at all that this was part of a congruence problem.

 

[fresh_42]

x^2 \equiv 26 (mod 55)

In which case you should look up Legendre symbols, Jacobi symbols, and the Euler criterion.

 

[anuttarasammyak]

x^2 \equiv 26 (mod 55)

So I observe
$$x^2 \equiv 1 (mod\ 5)$$ and
$$x^2 \equiv 4 (mod\ 11)$$
Further we can express x by mod 5 and mod 11.
$$x\equiv 1,4(mod\ 5)$$
$$x=5n \pm 1=\{1,4,6,9,11,14,16,19,21,24,26,29,31,34,36,39,41,44,46,49,51\}$$
Here I take 0 < x < 55 because all the other solutions are written as x+55m.
And
$$x\equiv 2,9(mod\ 11)$$
$$x=11n \pm 2 =\{9,13,20,24,31,35,42,46,53\}$$
You see common numbers.

 

[bpet]

x^2 \equiv 26 (mod 55)

This page has some theory for this type of equation:
Quadratic residue - Wikipedia

 

[docnet]

I know a useful protocol for finding square roots mod $n=pq$. It is from Laurence Trappe's introduction to cryptography with coding theory. If you know the factorization of $n$, this protocol will work when $p \equiv 3(mod 4)$ and $q \equiv 3(mod 4)$.

For a problem

$$x^2 \equiv a(mod pq)$$

compute

$$α\equiv a^{\frac{p+1}{4}}(mod p)$$
$$β\equiv a^{\frac{q+1}{4}}(mod q)$$

then use the chinese remainder theorem to solve the two system of congruences

$$x\equiv α(mod p), x\equiv β(mod q)$$
$$x\equiv -α(mod p), x\equiv β(mod q)$$

edited for grammar