[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
## gmp 'factorize.c' example bug, and suggested fix

**From**: |
John Pongsajapan |

**Subject**: |
gmp 'factorize.c' example bug, and suggested fix |

**Date**: |
Sun, 16 Feb 2003 11:19:25 -0800 |

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

**gmp 'factorize.c' example bug, and suggested fix**,
*John Pongsajapan* **<=**