Consider the following diophantine equation.
$$x^2 - a^2y^2 = -4n$$ $a$ and n are positive integers and $n$ is a large semi prime whose factors are not readily available. If the factors of n were known we could fairly quickly solve this equation. Could someone please shed some light on how to go about solving this problem assuming one can't quickly factor $n$.
One could reduce the original equation to (x+ay)(x-ay) = -4n but how to proceed from here assuming that n cannot be readily factored.
Yes, you can solve it easy without the need to factor $n$ by simply factoring $-4 n$ which can be factored in pairs as $(-1,4 n)$ ,$(-2,2 n)$ ,$(-4,n)$,$(1,-4 n)$,$(2,-2 n)$ and $(4,-n)$, but surly without knowing the factors of $n$ you will miss a couple of valid answer, lets move on : for example , given $a=3 ,n =77 =7*11$ but we don't know that $77=7*11$ for the sake of giving you the answer you are looking for.
so you have two linear diophantine equation which can be solved using Extended Euclid algorithm which are :
$x + a y = 4*77$ and $x-a y=-1$ which have no integer solutions.
or
$x + a y = 2*77$ and $x-a y=-2$ which have a solution $x=76,y=26$
or
$x + a y = 1*77$ and $x-a y=-4$ which have no integer solutions.
or
$x + a y = -4*77$ and $x-a y=1$ which have no integer solutions.
or
$x + a y = -2*77$ and $x-a y=2$ which have a solution $x=-76,y=-26$
or
$x + a y = -1*77$ and $x-a y=4$ which have no integer solutions.
now if you do it for different $a$ and $n$ and the $6$ linear equations did not produces a solution, that does not necessarily mean the $x^2-a^2 y^2 =-4 n$ does not have a solution, it just say that we don't know how to factor integers in fast(polynomial time) way.