Python. Find factor of huge number.

Question

How to find factor of number like 1636695303948070935006594848413799576108321023021532394741645684048066898202337277441635046162952078575443342063780035504608628272942696526664263794691 in python?

It shouldn't be prime. Any factor except 1 and number - acceptable.

I reviewed solutions like from here with no result.

Naive solution like:

def factor(n):
    i = 2
    limit = n / 2
    while i <= limit:
      if n % i == 0:
        return i
      i += 1
    return 1

Also not work.

Huh. The linked question has an answer with 103, and it "doesn't work"? What code do you *actually run* when you test it, how does the test code behave, and what behaviour did you expect? — , Apr 09 '16 at 20:21
Answer with 103 will fail with error `long int too large to convert to float`. Also it will meet error `OverflowError: range() result has too many items`. My question is more about algorithm for finding one factor of very big number. — Nikolay Fominyh, Apr 09 '16 at 20:24
If you find a reliable way to factor numbers of that size, you will become famous and break a lot of encryption systems. — interjay, Apr 09 '16 at 20:26
I don't think you'll be able to iterate through 1.6e+150 objects in a reasonable amount of time. — TigerhawkT3, Apr 09 '16 at 20:28
I have to assume that you're using Python 2. Regarding the `OverflowError`: you should use `xrange`, not `range`. Regarding, the "long int too large" error: that's because the code uses the float square root to calculate the upper limit, while it should be using the integer square root; you could replace it with `n / 2` for the time being. — , Apr 09 '16 at 20:32
That said, even with more sophisticated factorisation methods, it's not likely you can just punch it in the Python REPL and expect a result in an hour. And even if you implement those methods in the fastest way possible, expect it to [take months](https://en.wikipedia.org/wiki/Integer_factorization_records#Numbers_of_a_special_form) for numbers of that size. — , Apr 09 '16 at 20:37
Even iterating over `n**0.5` objects would be 1.3e+75 iterations. A 10GHz processor doing an iteration every single cycle would still take 4.1e+67 years to complete the loop. — TigerhawkT3, Apr 09 '16 at 20:37
That number isn't too bad to factor: its factors have 10, 13, 25, and 104 decimal digits respectively. The first two are easy to find with [ECM](https://en.wikipedia.org/wiki/Lenstra_elliptic_curve_factorization), but that's a more complicated method than can easily be explained in a comment. — DSM, Apr 09 '16 at 20:43
@DSM: I'm betting you didn't use Python for that, though. :-) (Pari/GP worked for me, apparently finding all three of the smaller factors with ECM.) — Mark Dickinson, Apr 09 '16 at 20:53
Actually I misunderstood conditions of google cup task and replaced input numbers by places. However, very nice discussion. :) — Nikolay Fominyh, Apr 09 '16 at 20:55

score 5 · Accepted Answer · answered Apr 09 '16 at 21:10

Pollard's Rho is a good tool for factoring large numbers that have relatively small prime factors. Here is a naïve implementation:

import random
from fractions import gcd

def pollardRho(n, seed = None):
    def f(x): return (x**2 + 1) % n
    if seed == None: seed = random.randint(0,n-1)
    t = h = seed
    t = f(t)
    h = f(f(h))
    d = gcd(t-h,n)
    while d == 1:
        t = f(t)
        h = f(f(h))
        d = gcd(t-h,n)
    return d,n//d

This finds the 10-digit factor of the n in the question in a few seconds. As an exercise, you can implement some of the speedups described in the Wikipedia article. Using that, the 13 digit factor falls in about a minute. I'm not sure that I have the patience for the 25 digit factor, but it should be borderline feasible.

Python. Find factor of huge number.

1 Answers1