CODEWITHSUNDEEP
primesprime-factoring
user1391078
user1391078

Reputation: 53

Prime factorization for big numbers

I am trying to find the complexity of a factorization for big numbers. Which is the best algorithm and which is the complexity of finding a number's prime factors? Assume that the length of the number is n.

Upvotes: 3

Views: 12420

Answers (2)

Abhishek kumar yadav
Abhishek kumar yadav

Reputation: 39

the complexity will be sqrt(n)log(n).But for n<=19^7 if you use sieve then after sieve it can be done in log(n). You can see here -> http://codeforces.com/blog/entry/7262

Upvotes: 0

Koen Peters
Koen Peters

Reputation: 12916

The best know algoritm for factoring integer larger than 100 digits is General number field sieve. It's complexity is explained on the page that the link links to.

Wikipedia has a nice article about other algoritms: http://en.wikipedia.org/wiki/Integer_factorization

Upvotes: 1

Related Questions