Блог пользователя mufasa

factoring
Автор mufasa, 13 лет назад, По-английски

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

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
Pollard's rho algorithm
→ Ответить
13 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
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).
→ Ответить