# Questions tagged [nt.number-theory]

Questions in number theory

102 questions
Filter by
Sorted by
Tagged with
119 views

### Is modular square roots in NC?

Assume factorization of modulus is known. Is modular square roots then in $NC$? How about the case of prime modulus?
• 12.6k
1 vote
97 views

### On the borderline between natural and artificial problems

While there is no formal definition of what constitutes a natural algorithmic problem, in most cases there is pretty good consensus whether a specific problem is natural or artificial. Natural usually ...
• 10.8k
239 views

### Is the following equitable factoring problem $NP$-hard or in $P$?

Consider the following factoring problem: Given an integer $r$ and another integer $N$ along with all of its $n$ number of prime factors and their corresponding multiplicities $\{p_i,e_i\}_{i=1}^n$, ...
• 12.6k
133 views

### What is a known sequence for which being constant is not provable?

My question concerns the property of being constant for computable functions ${\mathbb N}\to \{0,1\}$, within any common framework $T$ strong enough to include Heyting arithmetic (and of course not ...
• 505
1k views

### Decidability of diophantine equations over {=, +, gcd}

It is well-known that polynomial diophantine equations are undecidable (Hilbert's 10th problem): that is, given a quantifier-free formula over the language $\{=, +, \cdot, 1\}$ (of equality, addition, ...
257 views

Since $e$ is transcendental, the function $f:\mathbb Z_{\geq 0}^{n+1}\to \mathbb R$ is injective, $$f(\underset{\text{Integers}\ \geq\ 0}{\underbrace{a_0,a_1,\ldots, a_n}}) = a_0 + a_1e+a_2e^2+\cdots ... • 1,879 9 votes 1 answer 479 views ### Formalizing the "no formula for primes" intuition I was trying to formalize the intuition is that there is no formula for primes, and this is my best attempt: Conjecture: There is no O(n^2) expected time randomized algorithm to generate \ge n-... • 3,221 0 votes 0 answers 43 views ### Is this a proof that diophantine equation solutions can't be bounded by power towers? From this 2017 paper on upper bounds for solutions to diophantine equations: Conjecture 1. If a system of equations S ⊆ Bn has exactly one solution in positive integers x1, . . . , xn , then x1, .... 1 vote 1 answer 212 views ### Analytic Number theory in TCS [closed] Are there any applications of analytic number theory in TCS? • 31 2 votes 0 answers 81 views ### is factoring harder than deciding if all prime factors lie in a particular residue class? Let n be a large positive integer. Suppose I want to know if all the prime factors of n are congruent to, say, 3 mod 8. Is this any easier than just factoring n? • 241 20 votes 1 answer 492 views ### Is prime-counting function #P-complete? Recall \pi(n) the number of primes \le n is the prime-counting function. By "PRIMES in P", computing \pi(n) is in #P. Is the problem #P-complete? Or, perhaps, there is a complexity reason to ... • 720 1 vote 0 answers 102 views ### Complexity of planted root of a system of quadratic homogeneous polynomials? Given homogeneous degree 2 randomly chosen polynomials f_1,\dots,f_{m} in \mathbb Z[x_1,\dots,x_n,y_1,\dots,y_n] each with only monomials x_iy_j with condition that the system f_1=\dots=f_{m}=... • 12.6k 14 votes 4 answers 614 views ### Base-k representations of the co-domain of a polynomial - is it context-free? In chapter 4 of Jeffrey Shallit's A Second Course in Automata Theory the following problem is listed as open: Let p(n) be a polynomial with rational coefficients such that p(n) \in \mathbb{N} for ... • 411 5 votes 1 answer 180 views ### Complexity of counting integer roots of multivariate polynomials in a polyhedron? Deciding integer roots of multivariate polyomials is undecidable. However what is known about counting integer roots of multivariate polynomials in \mathbb Z[x_1,\dots,x_m] with both m and total ... • 12.6k 14 votes 1 answer 1k views ### Deciding whether an interval contains a prime number What is the complexity of deciding whether an interval of the natural numbers contains a prime? A variant of the Sieve of Eratosthenes gives an \tilde O(L) algorithm, where L is the length of the ... 3 votes 0 answers 252 views ### Primality in NC hierarchy? AKS primality testing solves whether a given integer is prime in P. AKS algorithm is following: Input: integer n > 1. Check if n is a perfect power: if n = a^b for integers a > 1 and b &... • 12.6k 5 votes 0 answers 145 views ### How hard is it to generate a set of relatively prime numbers between two given bounds? Informal Question How hard is it to generate a set of relatively prime numbers between two given bounds? Decision Problem Given a, b, and k \in \mathbb{N}. Does there exist a set S \... • 4,995 2 votes 1 answer 147 views ### Is there any time efficient way of achieving the result of FKS hashing lemma? FKS hashing lemma states. Given a set of n-bit numbers \{x_1,x_2,\dots,x_k\} there exist a prime p of O(\log n + \log k)-bit such that x_i mod p \neq  x_j mod p if x_i \neq x_j... 0 votes 1 answer 87 views ### Does this pairwise independent random process have expected max load \sqrt{n}? This is an extension to the question about balls into bins: Example of pairwise independent random process with expected max load \sqrt{n} . There the following question is asked and answered in ... • 3,940 1 vote 1 answer 293 views ### Relation between transcendental numbers and computational complexity? Regarding the relation, there is the Hartmanis-Stearns conjecture, but beyond Turing Machine of the realtime output, there is no further conjecture or theorem. Obviously irrational algebraic number ... • 1,050 6 votes 0 answers 319 views ### Is there any algorithm outputing e in real time? The Hartmanis-Stearns Conjecture says that a number computed in real time by a Turing Machine is either rational or transcendental. We know that there is some transcendental (Liouville) number that ... • 1,050 10 votes 1 answer 345 views ### Algorithm to compute distance between powers Given coprime a, b, can you quickly compute$$ \min_{x, y > 0} |a^x - b^y|  Here $x, y$ are integers. Obviously taking $x = y = 0$ gives an uninteresting answer; in general how close can these ...
• 261
1k views

The paper "On the computational complexity of algebraic numbers: the Hartmanis--Stearns problem revisited" by Boris Adamczewski, Julien Cassaigne, Marion Le Gonidec https://arxiv.org/abs/1601....
• 1,050
46 views

### Equal degree factoring of homogeneous polynomials over $\Bbb Q[x_1,\dots,x_n]$?

Given $f(x_1,\dots,x_n)\in\Bbb Q[x_1,\dots,x_n]$ of form $\prod_{i=1}^df_i(x_1,\dots,x_n)$ where each of $f,f_i$ are homogeneous and each $f_i$ is irreducible what is the best technique to factor such ...
• 12.6k
297 views

### Algorithms to generate consecutive primes

The prime number theorem, states that the "average length" of the gap between a prime $p$ and the next prime is ln(p). I am looking for (preferably deterministic efficient) an algorithm that generates ...
288 views

• 717
809 views

### Is square removal easier than factoring?

It seems to me that the square removal task can be reduced to the factoring task, but that there is no way to reduce factoring to square removal. Is there a way to make this "feeling" more precise, i....
• 3,013
780 views

• 717
144 views

### Solving a system of sums-of-powers polynomials

What is the complexity of calculating the values of the integers $x_i$, where $0 \leq x_1 < x_2 < \dots < x_k < n$, given only the values $s_m = \sum_{i=1}^k x_i^m$? for $1 \leq m \leq k$? ...
• 11.1k
266 views

### Sieve Methods for Twin Primes - How to extract algorithm from formula

I am reading Cojocaru and Murty's Introduction to Sieve Methods and their Applications. They wait until Chapter 5 to discuss the Sieve of Eratosthenes for finding primes - and their version of it is ...
• 578
278 views

### n irrational number whose digits are pseudo-random: conceptual mismatch?

Are there irrational numbers whose digits are considered pseudo-random? Both concepts seem to be mismatched as a pseudo-random number generator typically is periodic and therefore generates a ...
Suppose that $N = p_1^{a_1} p_2^{a_2} ... p_k^{a_k}$ with $p_i$ prime and $a_i \geq 1$. Given a representation of the factorization of $N$ and an integer $m$ (using alphabet $\Sigma = \{0,1,,\}$): ...
I know about algorithms like Sieve of Eratosthenes and Sieve of Atkin for generating prime numbers. I would like to know what is the most efficient known algorithm to generate the sequence of $k$ ...