Jump to content

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


rafael01
 Share

Recommended Posts

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
Link to comment
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.

Link to comment
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..

Link to comment
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.

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share

×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.