Solving the Diophantine equation $x^2 +2ax - y^2 = b$ in relation to Integer Factoring

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?

Related Questions

Why should this result be true? If $f: [0,1] to mathbb{R}$ is differentiable, $g$ is continuous, and $f'(t) = g(f(t)),$ then $f$ is monotonic.

1  Asked on January 7, 2022

Evaluate $int_0^1frac{mathrm{e}^{12x}-mathrm{e}^{-12x}}{mathrm{e}^{12x}+mathrm{e}^{-12x}},mathrm{d}x$

4  Asked on January 7, 2022

Find an example of sets of cosets of different cardinality

3  Asked on January 7, 2022

Prime number checker formula

2  Asked on January 7, 2022 by mondo-duke

About holomorph of a finite group being the normalizer of regular image

1  Asked on January 7, 2022

How do you generally tell the independence of events in a probability problem when it is not outright stated?

0  Asked on January 7, 2022

Why this map is birational?

0  Asked on January 7, 2022

Relationship between multivariate Bernoulli random vector and categorical random variable

1  Asked on January 7, 2022

Can’t argue with success? Looking for “bad math” that “gets away with it”

41  Asked on January 7, 2022

The topology generated by open intervals of rational numbers

1  Asked on January 7, 2022 by roslavets

If the solutions of $X’=AX$ have a constant norm then $A$ is skew symmetric.

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

An interesting identity involving the abundancy index of divisors of odd perfect numbers

1  Asked on January 7, 2022

Prove the series converges almost everywhere

1  Asked on January 7, 2022 by christopher-rose

Prove that the functional in $C_c^0(Omega)$ is a Radon measure

1  Asked on January 7, 2022

How can I evaluate ${lim_{hto 0}frac{cos(pi + h) + 1}{h}}$?

4  Asked on January 7, 2022 by dcdaking

Estimate $f(b)$ using Taylor Expansion for $f'(x) = cos(x^2)$

1  Asked on January 7, 2022 by brucemcmc

If $f ∈ C^∞(M)$ has vanishing first-order Taylor polynomial at $p$, is it a finite sum of $gh$ for $g, h ∈ C^∞(M)$ that vanish at $p$?

1  Asked on January 7, 2022 by fred-akalin

$sum_{n=1}^infty csc^2(omegapi n)= frac{A}{pi} +B$

2  Asked on January 7, 2022 by hwood87

Show that $f$ is a strong contraction when $f$ is continuously differentiable.

2  Asked on January 7, 2022

Decomposition of a linear operator to a partially orthogonal operator and a semi-definite self-adjoint operator

1  Asked on January 7, 2022 by zhanxiong