GNU bug report logs - #22567
Factoring 38 nines

Previous Next

To add a comment to this bug, you must first unarchive it, by sending
a message to control AT debbugs.gnu.org, with unarchive 22567 in the body.
You can then email your comments to 22567 AT debbugs.gnu.org in the normal way.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: SasQ <sasq1 <at> go2.pl>
To: bug-coreutils <at> gnu.org
Subject: Factoring 38 nines
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

Message #12 received at 22567-done <at> debbugs.gnu.org (full text, mbox):

From: Eric Blake <eblake <at> redhat.com>
To: SasQ <sasq1 <at> go2.pl>, 22567-done <at> debbugs.gnu.org
Subject: Re: bug#22567: Factoring 38 nines
Date: Fri, 5 Feb 2016 10:55:15 -0700

[Message part 1 (text/plain, inline)]

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 (application/pgp-signature, attachment)]

Message #15 received at 22567-done <at> debbugs.gnu.org (full text, mbox):

From: Eric Blake <eblake <at> redhat.com>
To: SasQ <sasq1 <at> go2.pl>, 22567-done <at> debbugs.gnu.org
Subject: Re: bug#22567: Factoring 38 nines
Date: Fri, 5 Feb 2016 11:05:12 -0700

[Message part 1 (text/plain, inline)]

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 (application/pgp-signature, attachment)]

Message #18 received at 22567-done <at> debbugs.gnu.org (full text, mbox):

From: SasQ <sasq1 <at> go2.pl>
To: Eric Blake <eblake <at> redhat.com>, 22567-done <at> debbugs.gnu.org
Subject: Re: bug#22567: Factoring 38 nines
Date: Fri, 05 Feb 2016 19:30:21 +0100

2016.02.05 @ 18:55, Eric Blake wrote:

> 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

OK, this convinces me this is not a bug. 4m30 on my machine.
But it's definitely a user-interface fail ;)
It should at least output some warning that the computations might
take longer, or display some progress status / estimated time along
the way.
Because otherwise the user can think it simply hangs.

> The source code is there for you to peruse.

There sure is, but analyzing it just to figure out the algorithm takes
much more time than refering the maual to see which particular
factorization algorithm or its variation is in use.

It took me a while to find the answer on StackOverflow:
http://stackoverflow.com/questions/11155331/what-is-the-algorithm-behind-the-factor-command-in-linux
so mentioning it in the man page wouldn't hurt.

Anyway, thanks for your detailed explanations.

-- 
SasQ

Message #21 received at 22567-done <at> debbugs.gnu.org (full text, mbox):

From: Eric Blake <eblake <at> redhat.com>
To: SasQ <sasq1 <at> go2.pl>, 22567-done <at> debbugs.gnu.org
Subject: Re: bug#22567: Factoring 38 nines
Date: Fri, 5 Feb 2016 12:29:59 -0700

[Message part 1 (text/plain, inline)]

On 02/05/2016 11:30 AM, SasQ wrote:

> 
> OK, this convinces me this is not a bug. 4m30 on my machine.
> But it's definitely a user-interface fail ;)
> It should at least output some warning that the computations might
> take longer, or display some progress status / estimated time along
> the way.

Estimated status is very hard to produce. I guess with trial division,
you could output a progress indicator comparing what number you are
trying in relation to the square root of the number being factored, as a
rough estimate; but there's still the annoying problem that any estimate
bar will not progress smoothly (once a factor is found, the time
remaining changes).  Progress indications should not be issued by
default, unfortunately, because it might break expectations of
applications that have grown used to no progress, so you'd have to make
it a new command line option - but then, how will people know to use the
new option?

> Because otherwise the user can think it simply hangs.

If a user is naive enough to think it is hanging on large input, how can
we expect them to also be aware that they can turn on an option to track
progress? And how will we explain that the progress meter may have no
bearing on the real amount of time required?

> 
>> The source code is there for you to peruse.
> 
> There sure is, but analyzing it just to figure out the algorithm takes
> much more time than refering the maual to see which particular
> factorization algorithm or its variation is in use.
> 
> It took me a while to find the answer on StackOverflow:
> http://stackoverflow.com/questions/11155331/what-is-the-algorithm-behind-the-factor-command-in-linux
> so mentioning it in the man page wouldn't hurt.

Well, it IS mentioned in the documentation (the info page, as the
preferred documentation for a GNU project); and the point of the man
page is to be a terse summary, not the full documentation.  But maybe
you have a valid point that adding a one-line blurb mentioning the
Pollar Rho algorithm in 'factor --help' (which in turn feeds the man
page) might be a useful change.

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

[signature.asc (application/pgp-signature, attachment)]

Message #24 received at 22567-done <at> debbugs.gnu.org (full text, mbox):

From: Jim Meyering <jim <at> meyering.net>
To: Eric Blake <eblake <at> redhat.com>
Cc: SasQ <sasq1 <at> go2.pl>, 22567-done <at> debbugs.gnu.org
Subject: Re: bug#22567: Factoring 38 nines
Date: Fri, 5 Feb 2016 12:35:22 -0800

On Fri, Feb 5, 2016 at 11:29 AM, Eric Blake <eblake <at> redhat.com> wrote:
> On 02/05/2016 11:30 AM, SasQ wrote:
>
>>
>> OK, this convinces me this is not a bug. 4m30 on my machine.
>> But it's definitely a user-interface fail ;)
>> It should at least output some warning that the computations might
>> take longer, or display some progress status / estimated time along
>> the way.
>
> Estimated status is very hard to produce. I guess with trial division,
> you could output a progress indicator comparing what number you are
> trying in relation to the square root of the number being factored, as a
> rough estimate; but there's still the annoying problem that any estimate
> bar will not progress smoothly (once a factor is found, the time
> remaining changes).  Progress indications should not be issued by
> default, unfortunately, because it might break expectations of
> applications that have grown used to no progress, so you'd have to make
> it a new command line option - but then, how will people know to use the
> new option?
>
>> Because otherwise the user can think it simply hangs.
>
> If a user is naive enough to think it is hanging on large input, how can
> we expect them to also be aware that they can turn on an option to track
> progress? And how will we explain that the progress meter may have no
> bearing on the real amount of time required?
>
>>
>>> The source code is there for you to peruse.
>>
>> There sure is, but analyzing it just to figure out the algorithm takes
>> much more time than refering the maual to see which particular
>> factorization algorithm or its variation is in use.
>>
>> It took me a while to find the answer on StackOverflow:
>> http://stackoverflow.com/questions/11155331/what-is-the-algorithm-behind-the-factor-command-in-linux
>> so mentioning it in the man page wouldn't hurt.
>
> Well, it IS mentioned in the documentation (the info page, as the
> preferred documentation for a GNU project); and the point of the man
> page is to be a terse summary, not the full documentation.  But maybe
> you have a valid point that adding a one-line blurb mentioning the
> Pollar Rho algorithm in 'factor --help' (which in turn feeds the man
> page) might be a useful change.

There is a deliberately hidden, three-hyphen ---debug
option that does provide a minimal progress indicator
(albeit still feels inadequate). This shows that it took
GNU factor 15 minutes to factor the 46-digit product
of two pretty large primes, M9 and M10:

$ M9=$(echo 2^61-1|bc) M10=$(echo 2^89-1|bc)
$ n=$(echo "$M9 * $M10" | bc)
$ env time -f '%U' factor ---debug $n
[using arbitrary-precision arithmetic] [trial division] [is number
prime?] [pollard-rho (1)] [trial division] [is number prime?] [trial
division] [is number prime?] [trial division] [is number prime?]
1427247692705959880439315947500961989719490561: 2305843009213693951
618970019642690137449562111
899.28

Message #27 received at 22567-done <at> debbugs.gnu.org (full text, mbox):

From: Leslie S Satenstein <lsatenstein <at> yahoo.com>
To: Eric Blake <eblake <at> redhat.com>, SasQ <sasq1 <at> go2.pl>, 
 "22567-done <at> debbugs.gnu.org" <22567-done <at> debbugs.gnu.org>
Subject: Re: bug#22567: Factoring 38 nines
Date: Fri, 5 Feb 2016 21:19:19 +0000 (UTC)

[Message part 1 (text/plain, inline)]

Works for me, but it took a long time  
 Regards 
 Leslie
 Mr. Leslie Satenstein
Montréal Québec, Canada



 
      From: Eric Blake <eblake <at> redhat.com>
 To: SasQ <sasq1 <at> go2.pl>; 22567-done <at> debbugs.gnu.org 
 Sent: Friday, February 5, 2016 2:29 PM
 Subject: bug#22567: Factoring 38 nines
   
On 02/05/2016 11:30 AM, SasQ wrote:

> 
> OK, this convinces me this is not a bug. 4m30 on my machine.
> But it's definitely a user-interface fail ;)
> It should at least output some warning that the computations might
> take longer, or display some progress status / estimated time along
> the way.

Estimated status is very hard to produce. I guess with trial division,
you could output a progress indicator comparing what number you are
trying in relation to the square root of the number being factored, as a
rough estimate; but there's still the annoying problem that any estimate
bar will not progress smoothly (once a factor is found, the time
remaining changes).  Progress indications should not be issued by
default, unfortunately, because it might break expectations of
applications that have grown used to no progress, so you'd have to make
it a new command line option - but then, how will people know to use the
new option?

> Because otherwise the user can think it simply hangs.

If a user is naive enough to think it is hanging on large input, how can
we expect them to also be aware that they can turn on an option to track
progress? And how will we explain that the progress meter may have no
bearing on the real amount of time required?

> 
>> The source code is there for you to peruse.
> 
> There sure is, but analyzing it just to figure out the algorithm takes
> much more time than refering the maual to see which particular
> factorization algorithm or its variation is in use.
> 
> It took me a while to find the answer on StackOverflow:
> http://stackoverflow.com/questions/11155331/what-is-the-algorithm-behind-the-factor-command-in-linux
> so mentioning it in the man page wouldn't hurt.

Well, it IS mentioned in the documentation (the info page, as the
preferred documentation for a GNU project); and the point of the man
page is to be a terse summary, not the full documentation.  But maybe
you have a valid point that adding a one-line blurb mentioning the
Pollar Rho algorithm in 'factor --help' (which in turn feeds the man
page) might be a useful change.

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


   

[Message part 2 (text/html, inline)]

Message #30 received at 22567-done <at> debbugs.gnu.org (full text, mbox):

From: Linda Walsh <coreutils <at> tlinx.org>
To: Jim Meyering <jim <at> meyering.net>
Cc: SasQ <sasq1 <at> go2.pl>, Eric Blake <eblake <at> redhat.com>,
 22567-done <at> debbugs.gnu.org
Subject: Re: bug#22567: Factoring 38 nines
Date: Sun, 07 Feb 2016 16:24:16 -0800

Jim Meyering wrote:
> On Fri, Feb 5, 2016 at 11:29 AM, Eric Blake <eblake <at> redhat.com> wrote:
>   
>> On 02/05/2016 11:30 AM, SasQ wrote:
>>
>>     
>>> OK, this convinces me this is not a bug. 4m30 on my machine.
>>> But it's definitely a user-interface fail ;)
>>> It should at least output some warning that the computations might
>>> take longer, or display some progress status / estimated time along
>>> the way.
>>>       
---
I thought factoring was something that was able to be made
faster with parallel processing?

I notice on linux and cygwin, only 1 cpu being used.

If someone **really** wanted to speed things up, I think using
video cards that support much larger parallelism, would likely
be a big boost... but that would be even more likely to be
a _little used feature_.

Message #33 received at 22567-done <at> debbugs.gnu.org (full text, mbox):

From: f0rhum <at> free.fr
To: 22567-done <at> debbugs.gnu.org
Subject: Re: bug#22567: Factoring 38 nines
Date: Mon, 8 Feb 2016 10:57:19 +0100 (CET)

Discovering this command, I submit a small mis-translation for french:
"factor --version
factor (GNU coreutils) 8.21
Copyright © 2013 Free Software Foundation, Inc.
License GPLv3+ : GNU GPL version 3 ou ultérieure
<http://gnu.org/licenses/gpl.html>
C'est logiciel libre..."

Should be "C'est ***un*** logiciel libre..." or "Ceci est ***un*** logiciel libre..."

Message #36 received at 22567-done <at> debbugs.gnu.org (full text, mbox):

From: Eric Blake <eblake <at> redhat.com>
To: f0rhum <at> free.fr, 22567-done <at> debbugs.gnu.org, traduc <at> traduc.org
Subject: Re: bug#22567: Factoring 38 nines
Date: Mon, 8 Feb 2016 06:25:54 -0700

[Message part 1 (text/plain, inline)]

On 02/08/2016 02:57 AM, f0rhum <at> free.fr wrote:
> Discovering this command, I submit a small mis-translation for french:

Thanks, but translation errors should be submitted to the appropriate
translation team, as mentioned in the --help output (and added in cc):

$ LC_ALL=fr_FR.UTF-8 factor --help | tail
Afficher les facteurs premiers de chaque NOMBRE entier indiqué.
Sans argument fourni, les nombres sont lus depuis l'entrée standard.

      --help     afficher l'aide et quitter
      --version  afficher des informations de version et quitter

Aide en ligne de GNU coreutils : <http://www.gnu.org/software/coreutils/>
Signalez les problèmes de traduction de « factor » à : <traduc <at> traduc.org>
Full documentation at: <http://www.gnu.org/software/coreutils/factor>
or available locally via: info '(coreutils) factor invocation'

Hmm, it also looks like there's a missing translation bug in the --help
output, at least in my build of coreutils (8.24, from Fedora 23).

> "factor --version
> factor (GNU coreutils) 8.21
> Copyright © 2013 Free Software Foundation, Inc.
> License GPLv3+ : GNU GPL version 3 ou ultérieure
> <http://gnu.org/licenses/gpl.html>
> C'est logiciel libre..."
> 
> Should be "C'est ***un*** logiciel libre..." or "Ceci est ***un*** logiciel libre..."
> 
> 
> 
> 

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

[signature.asc (application/pgp-signature, attachment)]

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.