--- Begin Message ---
Subject:
Factoring 38 nines
Date:
Fri, 05 Feb 2016 08:47:47 +0100
User-agent:
Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.6.0
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
--- End Message ---
--- Begin Message ---
Subject:
Re: bug#22567: Factoring 38 nines
Date:
Fri, 5 Feb 2016 10:55:15 -0700
User-agent:
Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101 Thunderbird/38.5.0
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
--- End Message ---