bug#22567: Factoring 38 nines

[Eric Blake]

On 02/05/2016 10:55 AM, Eric Blake wrote:

A bit more commentary:

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

This one is VERY easy to factor. Since the largest factor is 5, very
little effort is expended, even by a grade-school algorithm.

>> It also works fine for a number one less:
>>   factor 99999999999999999999999999999999999998
>> factoring it as:
>>   2 7 277294097 25759138835390148450014993081

This one is a bit harder, but the fact that 277294097 is (relatively)
small means that the first three factors can be found quickly; meanwhile
277294097 is large enough that you have knocked off several bits from
the remaining value, and even with naive algorithms, every bit knocked
off cuts the search time in half for deciding if the remaining value is
prime.

>> and it also works for the biggest 64-bit prime:
>>   factor 18446744073709551557
>> just returning itself.

Again, the magic here is that this is one of the primes that quickly
falls to algorithm tests.  If we used ONLY a naive algorithm, it could
potentially take much longer; but you'll still notice that this value is
much smaller than 25759138835390148450014993081 so it still takes less
search time in a naive algorithm than what you would spend factoring
99999999999999999999999999999999999998.

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

Here, the two primes are fairly close in length, and both much larger in
magnitude than the earlier examples.  This means that it takes longer to
even find 909090909090909091 as a factor and prove that it is a prime,
and then the algorithm has to spend another length of time proving that
1111111111111111111 is prime.

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

signature.asc
Description: OpenPGP digital signature