problem with factorize demo program

[David Relson]

Hello,

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:

    rm Makefile.in
    make test

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.

Regards,

David

-- 
David Relson                   Osage Software Systems, Inc.
relson at osagesoftware.com       Ann Arbor, MI 48103
www.osagesoftware.com
-------------- next part --------------
A non-text attachment was scrubbed...
Name: factorize.zip
Type: application/zip
Size: 10501 bytes
Desc: not available
Url : http://gmplib.org/list-archives/gmp-bugs/attachments/20080202/0a85b171/attachment.zip