gmp 'factorize.c' example bug, and suggested fix

[John Pongsajapan]

this is a bug in the pollard-rho factorization example code, not in
gmp.

using gmp 4.1.2, cygwin 1.3.20, pentium4, the following problem
occurs:

attempting to factorize 6244123617391642667062950 results in an
infinite loop [well, nearly].  [this is just one example].  i was
unable to test on other platforms.

factorize hangs on:

$ ./fact
6244123617391642667062950
6244123617391642667062950 = [trial division (6889)] 2 3 5 5 11 13 29 137 421 [is
 number prime?] [pollard-rho (1)] 27409

[does not finish]

...

immediately after 'goto target' S3, k value is sometimes negative and
keeps counting down [presumably until it overflows and hits a positive number].

replacing 'if (k != 0)' on line 184 with 'if (k > 0)' appears to fix
the problem:

$ diff factorize.c e:/mygmp/gmp-4.1.2/demos/factorize.c
183c183
<       if (k > 0)
---
>       if (k != 0)

$ ./fact
6244123617391642667062950
6244123617391642667062950 = [trial division (6889)] 2 3 5 5 11 13 29 137 421 [is
 number prime?] [pollard-rho (1)] 27409 28163 225461

, which is the correct result.

as the code is largely undocumented, i'm not -perfectly- sure that
this is the correct bugfix, and i did not trace through the logic path
that leads to k negative.

applying factorizations to large numbers of semi-large numbers tends
to trip this bug quite regularly.

---
John Pongsajapan                          mailto:address@hidden