The comp-number-theory tag has no wiki summary.
16
votes
4answers
504 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
79 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 \: : \: ...
9
votes
1answer
364 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
564 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
168 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
411 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} ...
9
votes
3answers
636 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 ...
8
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
190 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)?
...
11
votes
0answers
227 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 ...
