Subject: Factoring 38 nines

From: SasQ <[email-masked]>
Date: Fri, 05 Feb 2016 08:47:47 +0100

Hello.
Looks like I found a bug in the `factor` command
(version 8.21 on Gentoo Linux). For the following input:
  factor 99999999999999999999999999999999999999
it hangs, but for a longer number:
  factor 100000000000000000000000000000000000000
it works fine, factoring it as 38 "2"s and 38 "5"s.
It also works fine for a number one less:
  factor 99999999999999999999999999999999999998
factoring it as:
  2 7 277294097 25759138835390148450014993081
and it also works for the biggest 64-bit prime:
  factor 18446744073709551557
just returning itself.
So the only problematic input is the string of 38 "9"s.

P.S.: I'm curious though: How does it work that it is able to factor
      such big numbers in such a short time without large prime tables?

-- 
SasQ