All Questions
21 questions
2
votes
0
answers
66
views
How to check that a number probably/likely has a divisor having a specific bit length/in range?
Given a randomly generated $\alpha\in\Bbb N$ where $\alpha$ is large thus hard to factor (no small prime composites). How to check that a divisor $F\in\Bbb N$ with a specific bitlengh $n\in\Bbb N∧n<...
- 87
2
votes
0
answers
121
views
How to know if a random natural number is a probable semiprime?
Let that $n\in\Bbb N$ generated from a hash function where $n$ is long enough to be hard to factor in the gnfs algorithm. How to check if $n$ is probably a semi‑prime in a faster way than factoring it ...
- 87
3
votes
1
answer
1k
views
Root of polynomials in a finite field
I am looking for a way to find out if a polynomial $P\in \mathbb Z/p\mathbb Z=\mathbb F_p$, of great degree, has roots in $\mathbb F_p$, with $p$ a big prime number.
For example : $p=2^{2020}-69$ ...
- 4,074
0
votes
0
answers
135
views
On a deterministic primes search problem
I feel the following problem might be resolved already. But I could not find any related answers.
If $p_1,p_2,\dots,p_t$ are primes where $2\leq t=o(\log n)$ is there a prime within $$\prod_{i=1}^...
- 13.9k
0
votes
0
answers
62
views
On complexity of a particular prime problem
Is the following problem in $PH$ and is it complete for any class?
Problem: Is the $i$th bit of the $m$th prime $1$?
It appears to require a counting quantifier which has to demonstrate witness is the ...
- 13.9k
1
vote
1
answer
92
views
What are the complexity classes of these problems about divisibility and coprimality?
The problems
'Given $0<a<b$ and a prime $p<a$ is there an integer $\ell\in[a,b]$ such that $p|\ell$?'
'Given $0<a<b$ and an integer $q\not\in[a,b]$ is there an integer $\ell\in[a,b]$ ...
- 13.9k
4
votes
0
answers
213
views
What is the complexity class of this problem without Cramer's conjecture?
The problem 'Given $0<a<b$ is there a prime in the interval $[a,b]$?' is in $\mathsf{NP}$. If we assume Cramer's conjecture the problem is in $\mathsf{P}$ since if $b-a>(\log a)^{2+\epsilon}$ ...
- 13.9k
2
votes
0
answers
99
views
A problem in modular roots
We have three mutually coprime integers $r,t,M$ where $M\asymp K^{\frac12-2\epsilon}$ and $r,t\asymp K^{\frac14+\epsilon}$ holds with some fixed $\epsilon>0$ and $K>0$ is a large parameter. ...
- 13.9k
4
votes
1
answer
324
views
Higher roots modulo prime complexity best algorithm
Given integers $a,\ell$ and prime $p$ we need to find the roots of the algebraic equation $x^\ell\equiv a\bmod p$. We know there are at most $\ell$ such $x$.
What is the best method to find all such ...
12
votes
1
answer
547
views
Seeking references for finding primes infinitely often
I've been pondering this weakened version of the finding primes problem for a while:
Is there an algorithm which given $k$ outputs a prime $p > 2^k$ in time $F(\log_2(p))$?
This differs from ...
- 2,302
3
votes
2
answers
332
views
On generating squarefree integers and primes?
Given an $\alpha\in(0,1)$ and $n\in\Bbb N$ what are some known deterministic algorithms to sample $O(n^\alpha)$ (not just get one) square free integers of $n$ bits? Is it $O(n^{\alpha})$ complexity?
...
- 13.9k
7
votes
1
answer
382
views
Counting twin primes efficiently
This question, as well as its answers and comments, highlights a lot of unsettling numerical coincidences where certain sums over twin primes ostensibly converge to all kinds of weird values, however ...
- 5,590
1
vote
1
answer
153
views
Specializing non-trivial primality tests
Primes $p$ are integers with no factors (composite allowed) in $[1,p]$. There is a polynomial time test for them.
Given an interval $[a,b]$ what is the best way to test given integer $q$ has no ...
- 13.9k
7
votes
0
answers
267
views
Can primes be (almost) random sequence in von Mises sense?
Random models for primes (such as Cramer's model) have been extensively used for informal justification of various conjectures involving primes. It is crucial to understand in what sense sequence of ...
- 7,182
2
votes
0
answers
306
views
Avoiding Chinese Remainder Theorem
Given $k\in\Bbb N$ with $k<(\log_2N)^{\frac1\alpha}$ where $\alpha>2$ is fixed and $N$ being some integer such that $$N<\prod_{i=1}^k\pi_i^{a_i}$$ where $\pi_1,\pi_2,\dots,\pi_{k-1},\pi_k$ ...
user76479
3
votes
1
answer
369
views
What is the Complexity Class of the "Function Variant" of the Integer Factorization Problem?
I've been reading up a lot Prime Factorization and it's complexity, including a fair number of questions on this very site. However, I still feel there is a question still left unanswered.
So, ...
- 31
15
votes
1
answer
1k
views
Is there a known primitive recursive upper bound on the nth "Zhang prime"
(This question is pure curiosity. Feel free to close it if you feel it is not appropriate for mathoverflow.)
In 2013 Zhang showed that there are infinitely many pairs of primes which are less that ...
- 6,287
6
votes
2
answers
1k
views
Approximate number of primes below a given integer?
The problem of the complexity of the exact counting problem for primes is interesting. The best result we have about primes is that it is hard for TC0. But counting the number of witnesses to a TC0 ...
- 61
4
votes
0
answers
369
views
Reducing factoring prime products to factoring integer products (in average-case)
My question is about the equivalence of the security of various candidate one-way functions that can be constructed based on the hardness of factoring. (This question has been asked also in the CS ...
- 41
10
votes
2
answers
3k
views
Can a number be factored quickly, given the sum of its prime factors?
This is perhaps most naturally phrased as a promise problem. Given numbers $n$ and $s$, where $s$ is the sum of the prime factors of $n$ (distinct or with multiplicity; I imagine both variants will ...
- 9,114
8
votes
3
answers
947
views
Boolean Cube of Primes
For a large enough $n$, and a parameter $ m $ I'm looking for a subset of the prime numbers in the range $[n,2n]$ with a unique structure. I am looking for a prime $p$ and a set of $m$ positive (not ...
- 273