CODEWITHSUNDEEP
algorithmprime-factoring
Morgan Gethin Barrett
Morgan Gethin Barrett

Reputation: 91

How efficient is an integer factorizing algorithm with time complexity O(2^(n/2))?

How efficient is an integer factorizing algorithm for an n-bit number with time complexity O(2^(n/2)) compared to other factorizing algorithms?

Upvotes: 0

Views: 429

Answers (1)

knst
knst

Reputation: 533

Yes, trivial algorithm with checking all divisor from interval [1..sqrt(X)] has same complexity O(2^(n/2)).

Pollard's rho algorithm has complexity O(2^(n/4)). This one is old algorithm, easy implemented and good for not very long integer.

But modern number theory has more efficient algorithms, for example General number field sieve or Pollard-Strassen Algorithm.

You can read more about known popular factorization algorithm at wiki list

Upvotes: 1

Related Questions