forgotter's blog

Fast prime factorization (numbers greater than 10^19)
By forgotter, history, 6 years ago, In English

I have been trying to solve this question for a very long time: https://www.spoj.com/problems/FACT2/ (29 digits), I have already solved the task with smaller constraints (19 digits).

My implementation

Prime_factorization (num):
    prime_factor = pollard_rho (num)
    while (miller_rabin( prime_factor) != true):
        prime_factor = miller_rabin( prime_factor )
    while num%prime_factor == 0:
        num /= prime_factor

Here pollard-rho guesses a suitable prime factor and miller-rabin checks if returned factor is a prime.

My implementation (Code, C++) : https://github.com/forgotter/Snippets/blob/master/prime_factorization.cpp

Bugs in current implementation:

  1. The prime-numbers used in miller-rabin needs to be more, to check for higher constraints.

  2. Overflow (maybe)

I would like to know

  1. How to make my code more faster

  2. How to handle inputs larger than 10^18 (should I write one library for myself which can perform basic operations (+,-,*,/) on string.

Also, if someone can provide with a good tutorial on quadratic sieve. And with implementation would be too good to have.

Thanks for reading.

P.S: This is my first blog post. Please ignore minor mistakes.

  • Vote: I like it
  • +22
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it -9 Vote: I do not like it

Thanks forgotter.

→ Reply
»
6 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Nice post. I can see in the submission status of the problem that TLE has already solved this problem. Would you like to share your idea please ? Thanks in advance.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    'handle inputs larger than 10^18': just use __int128.

    There's nothing special: I myself wrote a pretty bad quadratic sieve while it seems a good pollard rho can already pass. I learnt all concepts just in wikipedia so I'm not sure I understood the concept clearly since my implementation is very very slow. (sad fact: a good pollard rho is 3 times faster than my quadratic sieve)

    You can see some codes of factorization here (I uploaded this problem: factorize n = pq ≤ 1030, p and q are different primes)

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      Thanks a lot. :)

      I am trying to solve both the questions now. :D

      Most of solutions implemented a 256 bit struct (Now I know the bug in my code). Those links seems to be very useful. A lot of nifty tricks to learn.

      → Reply