Jim Meyering <[email protected]> writes: Looking at factor.c, I saw this bit of code, and confirm that the current tests do not exercise it. { /* The found factor is two words. This is highly unlikely, thus hard to trigger. Please be careful before you change this code! */ uintmax_t ginv; binv (ginv, g0); /* Compute n = n / g. Since the result will */ n0 = ginv * n0; /* fit one word, we can compute the quotient */ n1 = 0; /* modulo B, ignoring the high divisor word. */ if (!prime2_p (g1, g0)) factor_using_pollard_rho2 (g1, g0, a + 1, factors); else factor_insert_large (factors, g1, g0); } Can you provide a test case that exercises that code? I tested this when this code was committed, using a special script. The problem is making Pollard rho find a factor of 65 bits or more, and since this Pollard rho code accepts 128-bit numbers, that means finding the 2nd largest factor. I could find only these two examples:
170141183460469225450570946617781744489 170141183460469229545748130981302223887 These will take a few minutes to run through our code, even on the fastest hardware, since they are absolutely worst-case numbers for Pollard rho. -- Torbjörn
