integer factorisation can't be polynomial for worst case scenario's

[noobinmath]

Hello I got the following proof, how do I begin to debunk it?

Integer factorisation can't be polynomial for worst case scenario's.

To prove this theorem, we use the fundamental theorem of arithmetic, which states that every integer greater than 1 can be expressed uniquely as a product of primes. We prove this by contradiction.

Assume that there exists an integer n that can be expressed in two different ways as a product of primes, say n = p1 * p2 * ... * pm = q1 * q2 * ... * qn, where the pi and qi are primes and m ≠ n. Without loss of generality, assume that p1 is not equal to any of the qi. Then p1 must divide n, and hence p1 must divide the product q1 * q2 * ... * qn. But since p1 is prime and is not equal to any of the qi, p1 must divide one of the qi, say q1. But now we have p1 divides both n and q1, which contradicts the assumption that the pi and qi are all prime. Therefore, the prime factorization of any integer is unique up to ordering of the factors.

Now, suppose we have an algorithm that can find the prime factors of an integer n in polynomial time. We use this algorithm to find the prime factors of a composite integer N, which we can express as N = p * q for two distinct primes p and q. Let D be the set of divisors of N, excluding 1 and N itself. Then all the elements of D are composite numbers and can be expressed as a product of two distinct primes, namely p and q. We can use our polynomial-time algorithm to find the prime factors of each element of D, and then group the results according to the product of the two primes. There will be exactly one group for each element of D.

Now, consider the product of the two smallest primes in each group. Since there is exactly one group for each divisor of N, we have accounted for all the factors of N. Therefore, the product of the two smallest primesThe fundamental theorem of arithmetic, also known as the unique factorization theorem, states that every positive integer greater than 1 can be represented uniquely as a product of prime numbers. Specifically, if n is a positive integer greater than 1, then there exist distinct prime numbers p1, p2, ..., pk and positive integers e1, e2, ..., ek such that:

n = p1^e1 * p2^e2 * ... * pk^ek

Moreover, this representation is unique up to the order of the factors.

Now suppose that there exists an efficient algorithm for integer factorization. Let n be a positive integer greater than 1, and let p be the smallest prime factor of n. By the fundamental theorem of arithmetic, we can write:

n = p * m

where m is a positive integer that is either prime or has a smallest prime factor greater than p. If we could efficiently compute the prime factors of m using our algorithm, then we could also determine the prime factors of n by combining them with the factor p. Moreover, the size of m is strictly smaller than the size of n, so we can repeat this process until we have found all the prime factors of n.

However, this algorithm would enable us to factor any positive integer n in polynomial time, which contradicts the well-known fact (proved by Carl Friedrich Gauss) that the number of primes less than n is approximately n/ln(n) for large n. In particular, this implies that the number of prime factors of a positive integer with n bits is roughly n/ln(2), which grows much faster than any polynomial function of n. Therefore, no efficient algorithm for integer factorization can exist, unless P = NP, which is considered unlikely by most experts in computational complexity theory.

Edited June 13, 2023 by noobinmath