Prime factorization for big numbers

primes prime-factoring
user1391078 picture user1391078 · May 12, 2012 · Viewed 12.2k times · Source

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.

Answer

Koen Peters picture Koen Peters · May 12, 2012

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

Related questions

Finding prime factors

#include <iostream> using namespace std; void whosprime(long long x) { bool imPrime = true; for(int i = 1; i <= x; i++) { for(int z = 2; z <= x; z++) { if((i != z) && (i%z == 0)) { imPrime = false; break; } } if(…

Read More
Segmented Sieve of Eratosthenes?

It's easy enough to make a simple sieve: for (int i=2; i<=N; i++){ if (sieve[i]==0){ cout << i << " is prime" << endl; for (int j = i; j<=N; j+=i){ sieve[j]=1; } } …

Read More
Prime Factors In C#

I want to create a program in C# 2005 which calculates prime factors of a given input. i want to use the basic and simplest things, no need to create a method for it nor array things etc. just simple modulus. …

Read More