# Questions tagged [comp-number-theory]

The tag has no usage guidance.

43 questions
Filter by
Sorted by
Tagged with
1 vote
56 views

### Why does splitting $n$ bit integers into chunks of size $\log(n)$ specifically, help in multiplying them

In integer multiplication algorithms such as the Schonhage-Strassen algorithm (and the recently described Harvey and van der Hoeven algorithm), integers of size $n$ are reduced to polynomials with ...
248 views

### Is modular square roots modulo primes in $NC$?

Assume modulus is prime. Is modular square roots then in $NC$? If not then, are there special primes or prime powers or numbers related to these (such as $2^k\pm i$ where $i\in\{-1,0,+1\}$) where it ...
45 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
230 views

### Analytic Number theory in TCS [closed]

Are there any applications of analytic number theory in TCS?
122 views

### Is finding square roots as hard as factoring, when coins are *public* and the square root oracle is adversarial?

Background: There is a well known argument (due to Rabin) that demonstrates that if one has access to an machine that computes square roots of elements in $\mathbb{Z}_n$, with $n = pq$, then $n$ can ...
509 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 ...
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 ...
1 vote
146 views

### Fixed dimension Integer programming minus LLL in fixed parameter $NC$?

If you remove LLL part then is remaining part of a. Lenstra algorithm b. Barvinok algorithm in $O(f(n)(\log(mL))^c)$ time on $O(g(n)(mL)^c)$ processors with fixed $c>0$ in fixed $n$ dimension, $m$ ...
78 views

### How to charactorize computational complexity based on finding solution to algebraic equations? [closed]

The Matiyasevich/MRDP Theorem relates two notions:one from computability theory, the other from number theory, thus Turing Machine and algorithms finding integral solution to algebraic equations can ...
1 vote
324 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 ...
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 ...
195 views

### What is the computational complexity of Hilbert Tenth problem over $\mathbb{Q_p}$

We know that Hilbert Tenth problem over $\mathbb{Q_p}$ is decidable,so what is the computational complexity of Hilbert Tenth problem over $\mathbb{Q_p}$? Is it equivalent to Tarski elimination ...
351 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 ...
288 views

230 views

### Does a polynomial-time algorithm for factoring product of two primes imply a polynomial-time algorithm for factoring in general?

Is it known if the existence of a polynomial-time algorithm for the promise problem of factoring of numbers with two prime factors implies that factoring in general has a polynomial-time algorithm?
173 views

### Simplified lattices

Consider the following question: Let $N$ be some large prime number, and suppose we are given $n$ uniformly independent samples $g_i$ from $0...,N-1$. Think of $N$ as being exponentially large in $n$...
995 views

### Computational complexity of modular power towers (tetration)

The complexity of modular addition is known: $g + p \mod N$ (for $|p| \approx |g| \approx |N|$) can be computed in $O(n = |N|)$. The complexity of modular multiplication is open though some results ...
289 views