# 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