1
$\begingroup$

I'm researching method of biprime number factoring. I have a biprime number 1012322327 * 1115382761 (19 decimal digits= 1129126872111204847). I'd like to know how many iterations (or trials) the best method has to perform to obtain a solution factors of this number. I'd like to have an estimation to compare to my own probabilistic method. My method requires between 100 million to couple billion randomized trials, this works quite fast in practice, but still seems too much.

If you are interested, here is the link to method: https://github.com/avaneev/biteopt/blob/master/primefactor.cpp (based on derivative-free optimization method)

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

Well there are about $5\times 10^7$ primes which are less than the square root of your input, since $$\pi(x)\sim x/\log(x),$$ so even a brute force search for prime divisors would be faster. Also your number is too small to try state of the art algorithms on.

The magma online calculator here computes the factorisation almost instantly.

Improve this answer
$\endgroup$
2
  • $\begingroup$ There is a handbook linked (look under basic rings/integer ring) but the command is Factorisation(n). $\endgroup$
    – kodlu
    Commented Sep 30, 2018 at 9:38
  • $\begingroup$ Yes, found it, thanks. It probably uses SQUFOF() algorithm for this number. $\endgroup$
    – aleksv
    Commented Sep 30, 2018 at 9:42

Not the answer you're looking for? Browse other questions tagged .