problem with factorize demo program
relson at osagesoftware.com
Sat Feb 2 14:20:15 CET 2008
I've encountered a problem with the factorize demo program. When used
with certain fairly large numbers it goes into an infinite loop.
Fortunately the fix is not hard.
Environment: 64-bit gentoo with a 64 bit build of gmp-4.2.2.
Consider 744073579624848590845803823140730546249, a 39 digit
number. It is the product of 31357373417090093431 and
23728823512345609279, which can be verified by using "bc" to multiply
the two numbers. However attempting to factor it with factorize results
in an infinite loop.
The difficulty is the "for" loop at line 199. All the variables are of
type "int" which limits the max useful value to 2**31. Factoring this
39 digit number needs a max loop value of 2**33.
The attached zip file contains files to demonstrate the problem and a
patch to correct it. The included files are:
patch1.txt - instruments factorize with a printf to display variables
k and l (along with the current power of 2 corresponding to k) and
to test for k wrapping from positive to negative. Wrapping
triggers an error message and the program exits.
patch2.txt - changes variables i, k, and l from type "int" to type
"mpz_t". It also includes the printf and negative test from patch1.
Makefile.am - adds rules for creating 2 'c' files, their associated
executables and testing them with 744...249
factorize1.c - created from factorize.c and patch1.txt
factorize2.c - created from factorize.c and patch2.txt
test_factorize1.out - the output of testing factorize1
test_factorize2.out - the output of testing factorize2
Makefile - the autoconf'd version of Makefile.am
To reproduce my results on your machine, unzip the files into the
"demos" directory and run the following:
This will regenerate Makefile from Makefile.am, create factorze1.c and
factorize2.c, and run both programs.
I'm looking forward to seeing this fix included in gmp.
Let me know if the problem (or this message) needs further
clarification or if you run into any issue reproducing my results.
David Relson Osage Software Systems, Inc.
relson at osagesoftware.com Ann Arbor, MI 48103
-------------- next part --------------
A non-text attachment was scrubbed...
Size: 10501 bytes
Desc: not available
Url : http://gmplib.org/list-archives/gmp-bugs/attachments/20080202/0a85b171/attachment.zip
More information about the gmp-bugs