Mathematics Asked by vvg on December 10, 2020

Is there a method we could use for solving the Diophantine equation $x^2 +2ax – y^2 = b$?

**Background:**

Consider a very large integer $z$ that we want to factor (not necessarily prime factorization, but finding $pq = z$).

Say we have $z$ unit square tiles. We start laying them out as squares.

The squares up to the green ones in the layout is the largest square we are able to form with $z$ tiles and the square tiles that are enclosed in thick black border are the residual tiles that are not part of a complete square.

i.e,. $z = s^2 + c, s=lfloor sqrt z rfloor, c = z mod s$.

Now we start removing the green squares (the green squares after removal are shown in yellow in the figure above) and place them around the square of dimension $s^2$. After the yellow squares are placed, we are showing them in blue in the figure above.

So, we have the equation

$x^2 + 2sx – c = y^2$

Rearranging,

$x^2 +2sx – y^2 = c$

This is a Diophantine equation of the form $x^2 + 2ax – y^2 = b$ given in the question where the coefficients on the LHS and the constant on the RHS have been replaced with $s, c$ respectively.

**Approach so far:**

In general, if we are free to choose $s$ such that $z = s^2 + c, c ge 0$, we could choose $s$ from the range $[1, lfloor sqrt z rfloor]$.

Noticing that the LHS is a quadratic form, we can choose $y$ as a parameter where $-y^2 = uv$ for integers $u, v$ and $u + v = 2s$. If we are able to find such a $y, u, v$, we can represent the LHS as the product of two linear factors in $x$. We would have reduced the factoring of a large $z$ into a smaller problem of factoring hopefully a small $c$.

We could then recursively perform factorization of $c$ using the same procedure until we get to a $c lt beta$, a smooth bound where we could just do trial division.

**Questions:**

- Is there an intelligent search procedure for $s$ and $c$ that helps us in factoring $z$ in polynomial time?

Get help from others!

Recent Answers

- Joshua Engel on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?
- haakon.io on Why fry rice before boiling?
- Jon Church on Why fry rice before boiling?
- Peter Machado on Why fry rice before boiling?

Recent Questions

- How can I transform graph image into a tikzpicture LaTeX code?
- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP