Bug in factorize.c (in the demos folder)

[Philip McLaughlin]

GMP version: 4.1.2

This is not a GMP bug, but a coding bug in "factorize.c" which is included in the demos folder. You can see the bug in action by making factorize and executing the following line:

./factorize 245723963580715350733457214075196517831719728

which results in the following output:

2 2 2 2 3 3 3 7 7 7 113 197 271 421 49633 1117913

at which point the program appears to hang. It isn't really hung, though. What's happening is that for one particular (rare) path in the code a certain variable (k) in the routine "factor_using_pollard_rho" is decremented from zero to -1, which then acts as 2^32-1 in a loop (resulting in a very long loop!) Specifically, here's the offending code:

k = 1;
while (mpz_cmp_ui (n, 1) != 0)
{
S2:
... (k is not affected here)
S3:
k--;
if (k != 0)
goto S2;

mpz_gcd (g, P, n);
if (mpz_cmp_ui (g, 1) != 0)
goto S4;

... (k is changed in this section, always > 0 )

S4:
... (k is not affected here)

} (end of while loop, jumps back to S2)

For bad behavior, k is equal to 1 at the S3 point, is decremented to zero, and falls through to the gcd call. If the 
gcd is greater than 1, then the code jumps to S4 and then back to S2 without altering k. When it gets decremented again (to -1), we enter the long loop. To fix this, I changed the "if (k != 0)" statement to "if(k > 0)", which seems to work. The correct output for the input above is

2 2 2 2 3 3 3 7 7 7 113 197 271 421 49633 1117913 16700713 704628237289 

My solution should be reviewed by someone who knows the theory to make sure it always works (and if not to find the right one!) 

Regards,
Phil McLaughlin