# Questions tagged [nt.number-theory]

Questions in number theory

96 questions
Filter by
Sorted by
Tagged with
2k views

### Complexity of exponential function

We know that the exponential function $\exp(x,y) = x^y$ over natural numbers is not computable in polynomial time, because the size of the output is not polynomially bounded in the size of the inputs. ...
1k views

### Efficiently computable function as a counter-example to Sarnak's Mobius conjecture

Recently, Gil Kalai and Dick Lipton both wrote nice articles on an interesting conjecture proposed by Peter Sarnak, an expert in number theory and the Riemann Hypothesis. Conjecture. Let $\mu(k)$ ...
2k views

### complexity of greatest common divisor (gcd)

Consider the following counting problem (or the associated decision problem): Given two positive integers encoded in binary, compute their greatest common divisor (gcd). What is the smallest ...
2k views

### Is there a natural problem on the naturals that is NP-complete?

Any natural number can be regarded as a bit sequence, so inputting a natural number is the same as inputting a 0-1 sequence, so NP-complete problems with natural inputs obviously exist. But are there ...
1k views

### How hard is it to count the number of factors of an integer?

Given an integer $N$ of length $n$ bits, how hard is it to output the number of prime factors (or alternatively number of factors) of $N$? If we knew the prime factorization of $N$, then this would ...
1k views

### Finding a prime greater than a given bound

Is a deterministic polynomial-time algorithm known for the following problem: Input: a natural number $n$ (in binary encoding) Output: a prime number $p > n$. (According to a list of open ...
1k views

### Complexity of factoring in number fields

What is known about the computational complexity of factoring integers in general number fields? More specifically: Over the integers we represent integers via their binary expansions. What is the ...
12k views

### How to check if a number is a perfect power in polynomial time

The first step of the AKS primality testing algorithm is to check if the input number is a perfect power. It seems that this is a well known fact in number theory since the paper did not explain it in ...
2k views

### Implications of proof of abc conjecture for cs theory

What implications would a proof of the abc conjecture have for tcs? http://quomodocumque.wordpress.com/2012/09/03/mochizuki-on-abc/
764 views

### Easy problems with hard counting versions

Wikipedia provides examples of problems where the counting version is hard, whereas the decision version is easy. Some of these are counting perfect matchings, counting the number of solutions to $2$-...
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, ...
463 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 ...
686 views

### How to obtain the unknown values $a_i,b_j$ given an unordered list of $a_i-b_j\mod N$?

Can anyone help me with the following problem? I want to find some values $a_i,b_j$ (mod $N$) where $i=1,2,…,K, j=1,2,…,K$ (for example $K=6$), given a list of $K^2$ values that correspond to the ...
827 views

### Is solving systems of equations modulo $k$ in $\mathsf{coMod}_k\mathsf L$ for $k$ composite?

I'm interested in the complexity of solving linear equations modulo k, for arbitrary k (and with a special interest in prime powers), specifically: Problem. For a given system of $m$ linear ...
964 views

### Why does Odlyzko improvement of Shor's Algorithm reduces the number of trials to $O(1)$

In his 1995 paper Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, Peter W. Shor discusses an improvement on the order-finding part of his ...
329 views

### Does Factoring have a Statistical Zero Knowledge Proof?

The title should be pretty self-explanatory, but to be more precise, consider the decision version of factoring, which is given input $(x,k)$, where $x$ and $k$ are binary encodings of integers, to ...
929 views

### Collatz Conjecture & Grammars / Automata

I was wondering if there is a good bibliography of attempts to investigate the Collatz conjecture as a formal grammar? (or any other attempts in the CS community to deal with this class of generative ...
4k views

### What is the “nearest” problem to the Collatz conjecture that has been successfully resolved?

I am interested in the "nearest" (and "most complex") problem to the Collatz conjecture that has been successfully solved (which Erdos famously said "mathematics is not yet ...
440 views

337 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 ...
439 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$-...
789 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....
The following lemma is not hard to prove. Lemma : Let $c_1 \neq c_2 \neq \dots \neq c_r \in [n]$ and $k \in [n]$. If $m_1, m_2, \dots, m_r$ are integers (some of them might be negative) such that $... 1answer 663 views ### Downward self-reducibility of factorization Is integer factorization downward self-reducible? Is anything known about this? 0answers 273 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 ... 1answer 250 views ### Comparing co-primes Suppose we have two numbers factorized into their primes, represented as lists of (p,d), where all p are prime, and d are the power of p. Is there a way to compare such two numbers without converting ... 2answers 257 views ### Complexity class of phase information in Gauss sum Have number theoretic functions such as Gauss sums been studied from a complexity view point? Where can I get a good introduction into complexity of Gauss sum estimation (beyond the quadratic case)? ... 2answers 314 views ### Complexity of summing up integral powers Let$x$be a rational number, and$S_n(x)= \sum_{1\leq i\leq n} i^x$. What is the complexity of computing$S_n(x)$correct to$d$decimal places? Is this a Hard problem? It is clear from Faulhaber's ... 4answers 1k views ### Approaching Number Theory conjectures through Graph Theory i try to find if there was an attempt to prove any famous Number Theory conjectures like Goldbach conjecture or Twin Prime conjectures through Graph Theory. I have in my mind something like the ... 1answer 519 views ### Discrete log in GL(2,p) Let$p$be a large prime. Let$A$be a$2\times 2$matrix with coefficients in$GF(p)$(i.e., coefficients taken modulo$p$). Let$B=A^k$, where$k$is an integer not given to us. Given$p$,$A$, ... 1answer 449 views ### Generating a Diffie Hellman tuple without “being able to know” one of the discrete logs involved Is it (believed to be) possible, in the various standard examples of groups in which discrete log/Diffie Hellman are hard (including multiplicative groups in modular arithmetic and elliptic curves, ... 0answers 151 views ### Recognition of a primitive root Adleman and McCurley published a paper in 1994 called "Open problems in number theoretic complexity, II" (http://ww.cstheory.com/papers/open.ps.gz) Problem 18 of this list of open problems is about ... 0answers 164 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$... 2answers 278 views ### Is there a fast algorithm to quickly evaluate$a^{b^c}$mod$n$? I need to quickly evaluate$a^{b^c} \mod n$where$c$is pretty big. Using the usual repeated squaring trick, this can be performed in$O(\log(b^c)) = O(c)$time. In my problem,$c$is huge, (say,$&...
Suppose we have a set $$P=\{p_1,p_2,...,p_K\}$$ where $$1\leq p_k\leq N , k=1,...,K \qquad \& \quad p_k \in \mathbb{N}$$ and $p_k$'s are distinct. We calculate the differences as: d=p_i-p_j\mod ...