Have you seen these integer factorization algorithms before?

Question

I have two algorithms for finding two factors, $p$ & $q$, of a number $N$. The algorithms are (hopefully) obviously related. The pseudo-code for them follows:

Algorithm 1

IF N is divisible by two
   p = 2
   q = N / 2
ELSE
   IF int(sqrt(N)) = sqrt(N)
      p = sqrt(N)
      q = p
   ELSE
      a        = int(sqrt(N)) + 1
      a_square = a * a
      b        = int(sqrt(a_square - N))
      b_square = b * b
      a_incr   = 2.a + 1
      b_incr   = 2.b + 1
      try_perf = N + b_square
      DO WHILE try_perf <> b_square
         IF try_perf < b_square
            try_perf = try_perf + a_incr
            a        = a + 1
            a_incr   = a_incr + 2
         ELSE
            b_square = b_square + b_incr
            b        = b + 1
            b_incr   = b_incr + 2
         ENDIF
      ENDDO
      p = a + b
      q = a - b
   ENDIF
ENDIF
return p, q

Algorithm 2

IF N is divisible by two
   p = 2
   q = N / 2
ELSE
   a        = int(sqrt(N))
   a_incr   = 2.b + 1
   a_square = b * b
   IF N = a_square
      p = a
      q = a
   ELSE
      a        = a + 1
      a_square = a_square + a_incr
      a_incr   = a_incr + 2
      diff     = a_square - N
      DO WHILE diff is not a perfect square
         a        = a + 1
         a_square = a_square + a_incr
         a_incr   = a_incr + a
         diff     = a_square - N
      ENDDO
      b = sqrt(diff)
      p = a + b
      q = a - b
   ENDIF
ENDIF
return p, q

Several questions:

1) Are these "new" algorithms, or have I rediscovered something which someone else has already found (if so who)? I have tried a bit of research, but haven't found anything similar, though I'm not totally sure where to look.

2) Which is the more efficient? If the number $N$ has binary length $l$, then I believe that the worst-case efficiency is $O = n(2^l)$, though this applies only if the number is prime, and efficiency improves dramatically as the two factors $p$ and $q$ approach each other. Where $p - q = 2$, the efficiency is $O=n$. If we assume that $p$ and $q$ are odd and that the sizes of $p$ and $q$ are both half that of $N$ (i.e. $l/2$) then for algorithm 2, I believe that the worst-case efficiency is about $O = n(2^{l/2})$ and the average-case efficiency is about $O = n((2^{(l-2)/2} + 2) / 6)$

3) Does it make any difference to the efficiency the fact that the algorithm is susceptible to parallel processing - by choosing different suitable initial values of "a", the process can be run multiple times concurrently?

Answer 1

The first is well-known (and the second just a variant as far as I can tell) as Fermat's factorization method. Whether parallelized or not, it is especially suitable when the fators are "close" to $\sqrt N$ (and that is one of the many conditions that anyone producing primes for RSA encryption avoids)