0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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)

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks - I think you mean that the second is well-known and the first is a variant on it $\endgroup$ – Charles Gaskell Apr 26 '15 at 22:14
  • $\begingroup$ Thanks - I think you mean that the second is well-known and the first is a variant on it. I wasn't sure whether the particular variant in algorithm 1 had been specified that way before. I like the way that apart from the initial calculations of 2 square roots, everything is either "adds" or "compares". Note that is you can guess roughly how far apart the two factors are (or at least what the lower bounds are), Fermat's factorization method can be very/relatively efficient $\endgroup$ – Charles Gaskell Apr 26 '15 at 22:26

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.