bug#22567: Factoring 38 nines

[Eric Blake]

tag 22567 notabug
thanks

On 02/05/2016 12:47 AM, SasQ wrote:
> 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.

The program is not hanging, just spending a LONG time.  Some numbers are
inherently easier to factor than others, when using currently-known
non-quantum algorithms.

On my machine:
$ time factor 99999999999999999999999999999999999999
99999999999999999999999999999999999999: 3 3 11 909090909090909091
1111111111111111111

real    0m45.630s
user    0m45.684s
sys     0m0.000s
$ time factor 18446744073709551557
18446744073709551557: 18446744073709551557

real    0m0.001s
user    0m0.000s
sys     0m0.001s


> 
> 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?

The source code is there for you to peruse.  The answer depends on part
whether you built coreutils with gmp support (in which case, we defer
the heavy lifting on to the numeric library writers), or if you are
stuck with an implementation that may not be as fast. Lots of
mathematical theory can be consulted on how to make factorization faster
on certain numbers (and in fact, such work is directly competing with
the use of large primes as the basis of cryptography), such as
Miller-Rabin probability filtering.  But for any given number, there's
no obvious formula for determining if it will be easy or hard.  (Of
course, someday we may be find ourselves using quantum computers, where
the rules of factoring are completely different, but that's a completely
different topic).

At any rate, although I'm marking this as not a bug, you may feel free
to add further comments to the thread.

-- 
Eric Blake   eblake redhat com    +1-919-301-3266
Libvirt virtualization library http://libvirt.org

signature.asc
Description: OpenPGP digital signature