Skip to main content
MathOverflow

Return to Answer

deleted 4 characters in body
Source Link
Dan Brumleve
Dan Brumleve
  • 2.3k
  • 17
  • 28

If we could find a number $x$ co-prime to $2^n!$ in $n^{O(1)}$ time, or even just a number divisible by at least one prime greater than $2^n$, we could factor it to find such a prime greater than $2^n$. This would constitute a solution to the strong conjecture with factoring, so it is an open problem.

As far as I know, it is open whether or not it is possible to find a prime larger than $2^n$ in time $2^{\frac{n}{2}+o(1)}$ with or without a factoring oracle. The finding primes page doesn't say this explicitly but I don't see any obvious method to beat this using a factoring oracle from the information presented. Perhaps someone can confirm that this weaker problem is open.

If we could find a number $x$ co-prime to $2^n!$ in $n^{O(1)}$ time, we could factor it to find a prime greater than $2^n$. This would constitute a solution to the strong conjecture with factoring, so it is an open problem.

As far as I know, it is open whether or not it is possible to find a prime larger than $2^n$ in time $2^{\frac{n}{2}+o(1)}$ with or without a factoring oracle. The finding primes page doesn't say this explicitly but I don't see any obvious method to beat this using a factoring oracle from the information presented. Perhaps someone can confirm that this weaker problem is open.

If we could find a number co-prime to $2^n!$ in $n^{O(1)}$ time, or even just a number divisible by at least one prime greater than $2^n$, we could factor it to find such a prime. This would constitute a solution to the strong conjecture with factoring, so it is an open problem.

As far as I know, it is open whether or not it is possible to find a prime larger than $2^n$ in time $2^{\frac{n}{2}+o(1)}$ with or without a factoring oracle. The finding primes page doesn't say this explicitly but I don't see any obvious method to beat this using a factoring oracle from the information presented. Perhaps someone can confirm that this weaker problem is open.

added 223 characters in body
Source Link
Dan Brumleve
Dan Brumleve
  • 2.3k
  • 17
  • 28

If we could find a number $x$ co-prime to $2^n!$ in $n^{O(1)}$ time, we could factor it to find a prime greater than $2^n$. This would constitute a solution to the strong conjecture with factoring, so it is an open problem. As

As far as I know, it is open whether or not it is possible to find a prime larger than $2^n$ in time $2^{\frac{n}{2}+o(1)}$ with or without a factoring oracle. The finding primes page doesn't say this explicitly but I don't see any obvious method to beat this using a factoring oracle from the information presented. Perhaps someone can confirm that this weaker problem is open.

If we could find a number $x$ co-prime to $2^n!$ in $n^{O(1)}$ time, we could factor it to find a prime greater than $2^n$. This would constitute a solution to the strong conjecture with factoring, so it is an open problem. As far as I know, it is open whether or not it is possible to find a prime larger than $2^n$ in time $2^{\frac{n}{2}+o(1)}$ with or without a factoring oracle.

If we could find a number $x$ co-prime to $2^n!$ in $n^{O(1)}$ time, we could factor it to find a prime greater than $2^n$. This would constitute a solution to the strong conjecture with factoring, so it is an open problem.

As far as I know, it is open whether or not it is possible to find a prime larger than $2^n$ in time $2^{\frac{n}{2}+o(1)}$ with or without a factoring oracle. The finding primes page doesn't say this explicitly but I don't see any obvious method to beat this using a factoring oracle from the information presented. Perhaps someone can confirm that this weaker problem is open.

Source Link
Dan Brumleve
Dan Brumleve
  • 2.3k
  • 17
  • 28

If we could find a number $x$ co-prime to $2^n!$ in $n^{O(1)}$ time, we could factor it to find a prime greater than $2^n$. This would constitute a solution to the strong conjecture with factoring, so it is an open problem. As far as I know, it is open whether or not it is possible to find a prime larger than $2^n$ in time $2^{\frac{n}{2}+o(1)}$ with or without a factoring oracle.