search

nishanth17 / factor

Fast prime factorization in Python
25 stars 7 forks source link

[Bug] Wrong result found #2

Closed teofr closed 2 years ago

teofr commented 3 years ago

The function factorize has a bug, in particular, if asked to factorize 18846316186591 it returns 1097 as its sole factor. However, if run with the verbose flag set, it works as expected. I'll try to find the reason if I have some time, it seems to be related to the Pollard Rho algorithm.

factorize(18846316186591)
[(1097, 1)]
>>> factorize(18846316186591, verbose=True)
Factoring 18846316186591...
Number of digits: 14
Finding small prime factors...
Prime factors found: 1097
Factoring 17179868903 with Pollard Rho...
Found factor 17179868903
Factoring 17179868903...
Number of digits: 11
17179868903 is prime!
[(1097, 1), (17179868903, 1)]
nishanth17 commented 3 years ago

Hello Teodoro,

Thank you for brining this to my attention! Indeed, the bug is in factor.py- I got the indentation of everything following the print statement wrong so a number would only be further factorized with Pollard Rho and ECM if verbose = True.

The code block in lines 104-109 should instead read:

if verbose:
    print "Found factor", str(g)
f1 = merge_factorizations(factorize(g, verbose = verbose, level = 2), \
                        factorize(n/g, verbose = verbose, level = 2))
if f1 != -1:
    f.extend(f1)

while, similarly, the code block in lines 118-125 should be:

if verbose:
    print "Found factor", str(g)
f1 = merge_factorizations(factorize(g, verbose = verbose, level = 2), \
                        factorize(n/g, verbose = verbose, level = 2))
if f1 != -1:
    f.extend(f1)
else:
       f = -1

I don't have access rights to my repository anymore to commit the fix for some odd reason, so while I figure that issue out, you could patch your local copy with these fixes.

Cheers!

nishanth17 commented 2 years ago

Sorry this took so long - fixed!