2
$\begingroup$

Given a large (100+ digit) semiprime $N$, I want to find the least positive integer $A$ such that $N + A^2$ is a perfect square. For example, if $N = 299$, then I want $A = 5$, because $299 + 5^2 = 18^2$. (Equivalently, I want to find the least perfect square $s$ where $s - N$ is also a perfect square. In the previous example, $s = 18^2 = 324$.)

Thus far, I've only managed to do this with guess-and-check, which is computationally intensive for larger values of $N$; so I'm looking for an efficient algorithm.

Finding an efficient algorithm for this would allow the quick factorization of large semiprimes.

$\endgroup$
6
$\begingroup$

In your example, let $N = 299$, $A^2 = 324$, and $B^2 = 25$. Then we have $N + B^2 = A^2$. Thus $N = A^2 - B^2 = (A - B) \cdot (A + B)$.

What's left is to look at the pairs of divisors of $N$. If $N = X \cdot Y$, we have $A - B = X$ and $A + B = Y$. So $A = (Y + X) / 2$ and $B = (Y - X) / 2$.

The simple formulas above suggest that there is a tight and straightforward relation between this question and the general case of integer factorization. Looks like one is not easier or harder than the other. In particular, in you can factor $N$, then you can solve your problem. Conversely, if there's a fast solution to your problem, it helps factor $N$. So, while the formulation as in the question may help, it's still very close to a long-standing hard problem.

Note that Fermat's factorization method is based on the representation of an odd integer as the difference of two squares, much like this question is. (Link suggested by Apass.Jack)

$\endgroup$
  • $\begingroup$ Is there any way to do it without knowing the values of X and Y? My main problem is finding A and B for very large values of N of which the factors are unknown. $\endgroup$ – Nick Jewett Feb 24 at 20:10
  • $\begingroup$ I was mainly looking to use this as a potential methodology for quickly factoring the product of two large primes (100+ digits). $\endgroup$ – Nick Jewett Feb 24 at 20:18
  • $\begingroup$ If you can factor $N$, how can you solve the problem? $\endgroup$ – xskxzr Feb 25 at 4:30
  • $\begingroup$ @xskxzr Loop over pairs of divisors ($X$ and $Y$ in $N = X \cdot Y$), select the minimum. Perhaps the minimum can be obtained using the closest pair of divisors, so no looping will be necessary, except maybe for finding that pair. Anyway, factoring is harder than this part. $\endgroup$ – Gassa Feb 25 at 9:37
3
$\begingroup$

This problem is as hard as factoring. Factoring has been intensely studied, and it is believed that there is unlikely to be an efficient algorithm for factoring. It follows that there is unlikely to be an efficient algorithm for your problem, either.

Justification: If there was an efficient algorithm for your problem, we could use it to factor $N$. In particular, since $N+A^2=B^2$, we have $N=(B-A)(B+A)$, so with high probability we will have found a non-trivial factor for $N$.

This reduction establishes that there is unlikely to be any simple and efficient algorithm for your problem. If there were a simple and efficient algorithm for your problem, there would be a simple and efficient algorithm for factoring, and we probably would have found it already.

The basic fact -- if we can write $N$ as a difference of squares we can use it to factor $N$ -- is well known to researchers working on factoring. For instance, it is used in Fermat's factoring method, the quadratic sieve, and other factoring methods. So, you are heading down a well-trodden path, one that factoring researchers have already spent a lot of time on. I don't think it's a promising direction. Some new idea would be needed. Progress on factoring has come largely from deep number-theoretic insights; this kind of very simple algebraic fact doesn't seem to be enough.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.