All Questions
31 questions
0
votes
0
answers
78
views
Factoring totient of a prime
Is it any easy to factor $p-1$ when $p$ is a prime compared to general factorization problem?
What about when $2p+1$ is also a prime?
- 13.9k
0
votes
0
answers
462
views
Relation between sieve wheel and Sundaram sieve
I made this sieve for prime numbers, which I briefly describe:
We consider $\quad p=r+modulus \cdot k \quad$ with $\quad modulus=p_1*p_2* \cdots *p_m$
and then we choose an appropriate reduced ...
- 179
2
votes
0
answers
205
views
Sum of all primes below $n$ without listing all primes below $n$
Asymptotically there is around $\frac{n}{\ln n}$ primes below a given integer $n$. Thus $\frac{n}{\ln n}$ is a lower bound for the time complexity of any algorithm that at some point finds each prime ...
- 21
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
7
votes
1
answer
1k
views
Expressing primes $p\equiv 1 \pmod 3$ in the form $p = x^2 + xy + y^2$
Fermat famously showed that the only primes $p$ of the form $x^2 + y^2$ are the primes such that $p \equiv 1 \mod{4}$. Furthermore, we now know “effective” versions of Fermat's theorem, i.e. given a ...
- 1,703
1
vote
0
answers
47
views
What is the most efficient algorithm for calculating $\Phi_q(b) \operatorname{mod} N$?
From Hurwitz's theorem about irreducible factor $F_{n-1}(x)$ of degree $\varphi(n-1)$ of $x^{n-1}-1$ we can deduce the following criterion for the primality of $N=2^m \cdot p_1^{n_1} \cdot p_2^{n_2} \...
- 2,661
35
votes
1
answer
4k
views
Does the algorithm of the Greeks produce all prime numbers?
Let ${\cal P}$ be the set of prime numbers. Define a subset ${\cal P}'=\{p_1,p_2,p_3,\cdots\}$ of ${\cal P}$ by setting $p_1=2$ and defining $p_{n+1}$ to be the smallest element of ${\cal P}$ ...
- 937
4
votes
3
answers
363
views
Example of concrete statement which requires probabilistic algorithm
In my paper I would like to include an example of easy concrete finitary statement which can be easily verified by probabilistic algorithm to any reasonable confidence level, but which looks ...
- 781
3
votes
0
answers
131
views
Improving prime number generation probability?
Deterministic generation of primes in polynomial time is unknown.
Is there a way to probablistically in $O(n^c)$ time bound for some $c>0$ generate polynomially $\Omega(n^c)$ many integers in $[0,...
- 13.9k
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
4
votes
1
answer
828
views
Primality test similar to the AKS test
Let us define polynomials $P_n^{(a)}(x)$ as follows :
$P_n^{(a)}(x)=\left(\frac{1}{2}\right)\cdot\left(\left(x-\sqrt{x^2+a}\right)^n+\left(x+\sqrt{x^2+a}\right)^n\right)$
We can define these ...
- 2,661
29
votes
1
answer
979
views
Is this BBP-type formula for $\ln 257$ and $\ln 65537$ true?
We have the known BBP(Bailey–Borwein–Plouffe)-type formulas,
$$\ln3 = \sum_{n=0}^\infty\frac{1}{2^{2n}}\left(\frac{1}{2n+1}\right)$$
$$\ln5 = \frac{1}{2^2}\sum_{n=0}^\infty\frac{1}{2^{4n}}\left(\...
- 12.6k
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
7
votes
2
answers
679
views
What is wrong with this deterministic algorithm efficiently generating large primes?
According to PolyMath
(Strong) conjecture. There exists deterministic algorithm which, when given an integer k, is guaranteed to find a prime of at least k digits in length of time polynomial in k. ...
- 25.4k
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
0
votes
0
answers
132
views
E- and A-algorithms for finite arithmetic prime progressions and other sets
(EDIT from scratch).
Let $\ \mathbf a := (a_1\ \ldots\ a_n)\ $ be an increasing non-constant arithmetic progression of odd positive numbers. The goal here is to resolve efficiently one of the two ...
- 7,500
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
3
votes
1
answer
906
views
At what point does Miller-Rabin become faster than trial division?
I've read in various places (and know) that Miller-Rabin is a much faster primality test than trial division for large $N$, but is much slower than trial division for small $N$.
My question is: how ...
- 31
9
votes
3
answers
9k
views
Algorithm for detecting prime powers
While reading Peter Shor's paper Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, I came across the following quote:
"This scheme will thus work as ...
- 1,199
3
votes
2
answers
2k
views
The relationship between the Dirichlet Hyperbola Method, the prime counting function, and Mertens function
I have a question concerning the connection between the Dirichlet Hyperbola Method and properties of both the Mertens function and the prime counting function.
Preliminary: Mertens function and the ...
- 627
26
votes
5
answers
11k
views
Fastest algorithm to compute the sum of primes?
Can anyone help me with references to the current fastest algorithms for counting the exact sum of primes less than some number n? I'm specifically curious about the best case running times, of ...
- 627
2
votes
0
answers
310
views
Algorithm for keeping a concrete version of Euclid's argument simple
(A version of this same question was posted to stackexchange.)
Suppose we do what Euclid wrote about: starting with a finite set of primes, multiply them, add or subtract 1, factor the result, append ...
3
votes
1
answer
442
views
Find the least prime $p$ such that $mn$ divides $p-1$
My hope is that this question is "trivial," but it is outside my knowledge base, so I'd appreciate some advice.
Given positive integers $m$ and $n$, find the least prime $p$ such that $p-1 = mnk$ ...
- 881
4
votes
1
answer
493
views
Can we count primes in residue classes quickly?
Using combinatorial methods (due to Legendre, Lehmer, Meissel, Lagarias, Miller, Odlyzko, Deléglise, Rivat, and probably others) it's possible to count the number of primes up to $N$ quickly -- in ...
- 9,114
8
votes
3
answers
2k
views
Prime counting - any fast alternatives to the Lagarias-Miller-Odlyzko combinatorial method or the Lagarias-Odlyzko analytical methods?
I guess the question says it all - I'm trying to track down fast algorithms for prime counting to know what's out there.
I'm already familiar with the two algorithms mentioned in the title (...
- 627
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
12
votes
2
answers
2k
views
Detecting almost-primes quickly
There are many fast algorithms (deterministic and probabilistic) for detecting primality. Are there any fast algorithms (probabilistic ones allowed) known for detecting whether a number is the product ...
- 20.2k
13
votes
4
answers
3k
views
Computing the Mertens function
I wonder if anybody can help me with this problem.
I'm trying to compute the Mertens function for large $n$. The most obvious algorithm is just to compute all primes up to $\sqrt{n}$ and then to ...
- 133
7
votes
8
answers
3k
views
Marey's problem: Generating all prime numbers in $[n_1,n_2]$
Is there are some references to algorithms that generate the set of prime numbers located between two given numbers n1 and n2?
I would like to consider the cases when n1 is large while n2-n1 is small ...
52
votes
4
answers
17k
views
How hard is it to compute the number of prime factors of a given integer?
I asked a related question on this mathoverflow thread. That question was promptly answered. This is a natural followup question to that one, which I decided to repost since that question is answered.
...
- 2,416