# is it possible to factor a large number in polynomial time using this method?

## Recommended Posts

is it possible to factor a large number in polynomial time using this method?

##### Share on other sites

1 hour ago, rafael01 said:

is it possible to factor a large number in polynomial time using this method?

I do not see an explanation of the method that allows for an analysis. As far as I know there is no known method for integer factorization that runs in polynomial time on classical* computers. "Large" is also rather vague.

For quantum computers refer to Shor's algorithm: https://en.wikipedia.org/wiki/Shor's_algorithm

Edited by Ghideon
##### Share on other sites

Quote

As far as I know there is no known method for integer factorization that runs in polynomial time on classical* computers.

It is possible, if we restrict ourselves to prime factorization we know that the distribution of primes is strictly increasing (if looking at the largest and second largest primes we know of the gap is fairly large). We can assume that after some point x the number of primes to test should be small enough to run in polynomial time using known algorithms. We just use a hashmap for the ones before that and we have an algorithm that has a polynomial runtime.

##### Share on other sites

4 minutes ago, fiveworlds said:

It is possible, if we restrict ourselves to prime factorization we know that the distribution of primes is strictly increasing (if looking at the largest and second largest primes we know of the gap is fairly large). We can assume that after some point x the number of primes to test should be small enough to run in polynomial time using known algorithms. We just use a hashmap for the ones before that and we have an algorithm that has a polynomial runtime.

The largest known primes are Mersenne primes. You have no idea where are non-Mersenne primes prior it..

##### Share on other sites

Unless rafael returns and explains his wallpaper designs, the answer is no.

##### Share on other sites

19 hours ago, fiveworlds said:

It is possible, if we restrict ourselves to prime factorization we know that the distribution of primes is strictly increasing (if looking at the largest and second largest primes we know of the gap is fairly large). We can assume that after some point x the number of primes to test should be small enough to run in polynomial time using known algorithms. We just use a hashmap for the ones before that and we have an algorithm that has a polynomial runtime.

Can you provide a reference? As far as I know the best algorithm at this time is general number field sieve and it does not run in polynomial time.

## Create an account

Register a new account