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