Factorization and the difference of two squares

Question

While contemplating on the mathematics behind RSA cryptography, I tried to play around how to possibly find the factors $p,q$ in a rather more algebraic and elementary way. What I initially found out that I can manage to factor any odd number $c$ if I could somehow manage to find integer solutions to $a^2 – b^2 = c$. If non trivial solution exists, then if $c=p \cdot q$ then $p=a-b$ and $q=a+b$. This is of course provided that $c$ is not a perfect square so that $p$ and $q$ will be distinct.

Example: $$c=15=3\cdot5$$ $$p,q=3,5$$ $$a,b=4,1$$ $$4^2 – 1^2 = 15$$

My questions are:

1. Is this approach to factorization trivial and not at all new?

2. In terms of computational algorithms, is this more efficient or worse than other factorization algorithm?

PS: This technique can also be extended to factorization of any odd non perfect square number. The trivial solution will be: if $c=2k+1$, then $a=k+1$ is a solution.

Answer 1

I know this is an old question... but

1. Is this approach to factorization trivial and not at all new?

Whether it's trivial is subjective, but it's not new. For instance, An Introduction to Mathematical Cryptography's Chapter 3.6 explains a fairly comprehensive approach based on this idea.

2. In terms of computational algorithms, is this more efficient or worse than other factorization algorithm?

As Peter says in the comment, it's statistically impossible to find a non-trivial difference by randomly trying a number. So, the idea isn't efficient as is.