The tag has no wiki summary.

learn more… | top users | synonyms

12
votes
1answer
721 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 ...
9
votes
2answers
208 views

Using the de Bruijn sequence to find the $\lceil\log_2 v \rceil$ of an integer $v$

Sean Anderson published bit twiddling hacks containing the Eric Cole's algorithm to find the $\lceil\log_2 v \rceil$ of an $N$-bit integer $v$ in $O(\lg(N))$ operations with multiply and lookup. The ...
5
votes
1answer
151 views

Is the primality problem with unary input NLOGSPACE-Hard?

Consider the language $L=\{1^n : n \text{ is prime}\}$. Is this language NLOGSPACE-Hard? The motivation for this question is that $L$ is a good candidate for reducing to other languages related to my ...
3
votes
1answer
51 views

Complexity of higher order residues

Let $P$ be a prime. Given a number $a$, what is the computational complexity in establishing if $a$ is a cubic or higher order residue modulo $P$? Are there any good algorithms?
0
votes
1answer
105 views

What algorithms do you know for beltway reconstruction? [closed]

I've faced the beltway reconstruction problem and I've developed a simple backtrack algorithm, what algorithms do you know for this problem? Beltway Reconstruction Problem: Assume there is a set of ...
4
votes
1answer
112 views

Difference Sets

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 ...
17
votes
4answers
574 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 ...
5
votes
0answers
87 views

How short can reversible representations of the n-bit primes be?

For $\: 1 < n \:$ and $\: n^{o(1)} < \sigma \leq n \:$, $\:$ how small can $L$ be for there to be for there to be an efficiently computable (deterministic) function $\;\; f \: : \: ...
11
votes
1answer
416 views

Is there a quantum NC algorithm for computing GCD?

From the comments on one of my questions on MathOverflow I get the feeling that the question regarding GCD being in $\mathsf{NC}$ vs. $\mathsf{P}$ is akin to the question regarding Integer ...
23
votes
2answers
623 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 ...
6
votes
1answer
217 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$, ...
15
votes
1answer
427 views

$(2^n)! = \sum_{k=0}^{m-1} a_k b_k^{c_k} $?

While reading Dick Lipton's blog, I stumbled across the following fact near the end of his Bourne Factor post: If, for every $n$, there exists a relation of the form $$ (2^n)! = \sum_{k=0}^{m-1} ...
15
votes
3answers
938 views

Determinant modulo m

What are the known efficient algorithms for computing a determinant of an integer matrix with coefficients in $\mathbb{Z}_m$, the ring of residues modulo $m$. The number $m$ may not be prime but ...
9
votes
3answers
2k views

Computing the Mobius function

The Mobius function $\mu(n)$ is defined as $\mu(1)=1$, $\mu(n)=0$ if $n$ has a squared prime factor, and $\mu(p_1 \dots p_k)= (-1)^k$ if all the primes $p_1,\dots,p_k$ are different. Is it possible to ...
7
votes
2answers
198 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)? ...
12
votes
0answers
242 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 ...