# Questions tagged [comp-number-theory]

The tag has no usage guidance.

13 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
265 views

### Conditional density of primes

We have some theorems about the density of prime numbers, the most famous one is probably the prime number theorem. My question is about the density of primes when we choose random numbers from a ...
826 views

### Complexity class of this problem?

I am trying to understand to which complexity class the following problem belongs: Exponentiating Polynomial Root Problem (EPRP) Let $p(x)$ be a polynomial with $\deg(p) \geq 0$ with coefficients ...
218 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?
309 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 ...
160 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$...
286 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 ...
93 views

104 views

### What is the complexity of computation of zero point by Rieman zeta function?

What is the complexity of computation of zero point by Rieman zeta function? That is, given s, whether ζ(s)=0? Is it in P? Any reference is appreciated.
242 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 ...
### 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$...
Having an infinite source of messages of $2^k$ possible values of equal probability of occurrence, what is the least necessary buffer needed for a reversible conversion of it to a source of messages ...