I have a large number $n$ (1250 decimal digits), which is a product of 2 prime numbers, which happen to be Germain prime numbers. I have to find the two prime numbers, have been given a quadratic equation $2x^2+x-n = 0$.
To apply the quadratic formula, you will need to find the square root of the discriminant D as an exact integer.
How do I find the discriminant without knowing the Phi value, which I cannot calculate since n is too large, cannot use Factorization either.
Any help would be much appreciated. Stuck on this problem for a while.
As Henno says in the comments, square roots that happen to be exact integers are easy to find. The reason is this: not-so-bad approximations of square roots are easy to find and once you have a non-so-bad approximation, you can just test which of the most nearby integers is the squareroot by trial and error (i.e. squaring them).
There are various algorithms for approximating square roots. I like the following one (allegedly invented by the ancient Babylonians) because it is easy to understand why it works:
1) Guess a first approximation $a_1$. It need not be a good guess, even something that is obviously wrong like $a_1 = 54$ might do.
2) Compute a second approximation $b_1$ by $b_1 = D/a_1$, where $D$ is the number you want to take the square root of. (So in your case $D = 8n + 1$)
If $a_1$ was too small (that is $a_1 < \sqrt{D}$), then $b_1$ is too big and if $a_1$ was too big then $b_1$ is to small. This suggest a way to find a second approximation $a_2$ that is a better approximation of $\sqrt{D}$ than $a_1$ was:
3) Compute $a_2 = \frac{a_1 + b_1}{2}$
4) Compute $b_2 = D/a_2$
Just as we like to believe that $a_2$ is closer to $\sqrt{D}$ than $a_1$ was, we believe that $b_2$ is closer to $\sqrt{D}$ than $b_1$ was. And again, if $a_2$ was an underestimation of $\sqrt{D}$ then $b_2$ is an overestimation and vice versa, so we can get an even better approximation by computing:
5) $a_3 = \frac{a_2 + b_2}{2}$
6) $b_3 = D/a_3$
7) $a_4 = \frac{a_3 + b_3}{2}$
etc etc.
You will be surprised how quickly these approximations of $\sqrt{D}$ get better, as can be seen for instance from the shrinking distance between $a_i$ and $b_i$.
Of course once you arrive at a point that there is only a single integer between $a_i$ and $b_i$ you know that this integer must be your answer (unless you made computing error somewhere).