mufasa's blog

factoring
By mufasa, 13 years ago, In English

Want to factorize 15 digit number.I have implemented the fermat's thm but it is not suitable for numbers having factor not close to square root of that number .Suggest me some methods .Thanx

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

Comments Comments (2)
| Write comment?
13 years ago, # |
  Vote: I like it +8 Vote: I do not like it
Pollard's rho algorithm
→ Reply
13 years ago, # |
  Vote: I like it +8 Vote: I do not like it
AFAIK, most of fast factorization algorithms are randomized and additionally require to implement primality test. But there is at least one algorithm that is fully deterministic, doesn't rely on primality tests and works within O(n1/3) operations for any positive integer n. The algorithm is described in “Factoring Large Integers” paper by R. Sherman Lehman (1974).
→ Reply