Prime Factorization Time Complexity

In summary, the conversation discusses the time complexity for prime factorization algorithms, particularly for a simple algorithm using division. The algorithm's complexity is found to be exponential and it is noted that prime factorization is known to be subexponential. The conversation ends with an understanding of the algorithm's complexity.
  • #1
gchadwick
2
0
While I know the time complexity for all known prime factorization algorithms is exponential, I can't seem to get this results for a very simple algorithm.

First assume we're doing this with numbers that are simply the product of two primes (the kind you get when working with RSA and others) a very simple way to do it is to simple divide the number you're trying to factorize, n by every number between 2 and sqrt(n) and seeing which two leave no remainder. If we then say that the division has a time complexity of o(a) where a is the number of digits we can work out the time complexity of factorization by a simple sum, log(n) + log(n) + log(n) + ... + log(n) (where log(n) will be the number of digits in n) the sum will have sqrt(n) terms in giving sqrt(n) log(n) however that is clearly the wrong result, so can anyone tell me where I'm going wrong? I'm sure it's something obvious I just can't see it.
 
Physics news on Phys.org
  • #2
gchadwick said:
While I know the time complexity for all known prime factorization algorithms is exponential

Are you sure about that? If you're correct then I have the same stumbling block as you, because even an algorithm that tests all numbers 1 to N would only have a run time of NlogN
 
  • #3
If you're correct then I have the same stumbling block as you, because even an algorithm that tests all numbers 1 to N would only have a run time of NlogN]
That is an exponential algorithm: the complexity of number theoretic algorithms is usually described in terms of the size of the representation of the numbers involved, rather than the size of the numbers themselves.

It takes n = lg N bits to store the number N, and so this algorithm runs in time:

[tex]O(2^{\mathop{\text{lg}} N} \mathop{\text{lg}} N)
= O(2^n n)[/tex]

and is thus exponential.


That said, prime factorization is known to be subexponential: The number field sieve is an L(1/3) algorithm. See Wikipedia's or Mathworld's page for reference.
 
Last edited:
  • Like
Likes WWGD
  • #4
Ahh that makes sense, I knew it was something obvious, thanks :)
 

1. What is Prime Factorization Time Complexity?

Prime Factorization Time Complexity refers to the amount of time it takes to determine the prime factors of a given number. This is an important concept in computer science and mathematics, as it helps us understand the efficiency of algorithms for finding prime factors.

2. How is Prime Factorization Time Complexity measured?

Prime Factorization Time Complexity is typically measured in terms of the number of operations required to find the prime factors of a given number. This can vary depending on the algorithm used, but is often expressed in terms of the input size (i.e. the number of digits in the given number).

3. What is the most efficient algorithm for Prime Factorization Time Complexity?

The most efficient algorithm for Prime Factorization Time Complexity is currently the General Number Field Sieve (GNFS), which has a time complexity of O(e^(c(log n)^(1/3)(log log n)^(2/3))) where n is the given number and c is a constant. However, for smaller numbers, simpler algorithms such as Trial Division or Pollard's Rho can be more efficient.

4. How does Prime Factorization Time Complexity impact cryptography?

Prime Factorization Time Complexity is a crucial factor in cryptography, as many cryptographic algorithms rely on the difficulty of factoring large numbers. If a more efficient algorithm for Prime Factorization is discovered, it could potentially weaken the security of these algorithms and make them vulnerable to attacks.

5. Are there any real-world applications for Prime Factorization Time Complexity?

Yes, Prime Factorization Time Complexity has many real-world applications such as in cryptography, computer security, and number theory. It is also used in various fields of science and engineering, such as in signal processing and error-correction coding.

Similar threads

  • Engineering and Comp Sci Homework Help
Replies
7
Views
1K
  • Programming and Computer Science
Replies
4
Views
1K
  • Precalculus Mathematics Homework Help
Replies
9
Views
1K
Replies
13
Views
1K
  • Quantum Physics
Replies
13
Views
837
Replies
4
Views
696
  • Engineering and Comp Sci Homework Help
Replies
10
Views
1K
  • General Math
Replies
12
Views
921
  • General Math
Replies
16
Views
3K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
1K
Back
Top