AnswerBun.com

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$).

Tiling example

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?

Add your own answers!

Related Questions

Prime number checker formula

2  Asked on January 7, 2022 by mondo-duke

     

Why this map is birational?

0  Asked on January 7, 2022

   

Ask a Question

Get help from others!

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