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?

1 Asked on January 7, 2022

4 Asked on January 7, 2022

3 Asked on January 7, 2022

2 Asked on January 7, 2022 by mondo-duke

1 Asked on January 7, 2022

abstract algebra finite groups group actions group theory holomorph

0 Asked on January 7, 2022

1 Asked on January 7, 2022

41 Asked on January 7, 2022

1 Asked on January 7, 2022 by roslavets

3 Asked on January 7, 2022 by as-soon-as-possible

1 Asked on January 7, 2022

arithmetic functions divisor sum number theory ordinary differential equations perfect numbers

1 Asked on January 7, 2022 by christopher-rose

lebesgue integral measure theory real analysis sequences and series

1 Asked on January 7, 2022

continuity distribution theory measure theory sobolev spaces topological vector spaces

4 Asked on January 7, 2022 by dcdaking

1 Asked on January 7, 2022 by brucemcmc

1 Asked on January 7, 2022 by fred-akalin

differential geometry manifolds smooth manifolds taylor expansion

2 Asked on January 7, 2022 by hwood87

2 Asked on January 7, 2022

1 Asked on January 7, 2022 by zhanxiong

Get help from others!

Recent Questions

Recent Answers

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

© 2022 AnswerBun.com. All rights reserved. Sites we Love: PCI Database, MenuIva, UKBizDB, Menu Kuliner, Sharing RPP