34

One non-answer to your question is that SQUARE-FREE (is a number square free) is itself not known to be in P, and computing the Möbius function would solve this problem (since a square free number has $\mu(n) \neq 0$).


27

Disclaimer: I'm not an expert in number theory. Short answer: If you're willing to assume "reasonable number-theoretic conjectures", then we can tell whether there is a prime in the interval $[n, n+\Delta]$ in time $\mathrm{polylog}(n)$. If you're not willing to make such an assumption, then there is a beautiful algorithm due to Odlyzko that achieves $n^{1/...


19

Here is the construction of such a number. You can argue whether this means such a number is "known". Take any function $f$ from $\mathbb{N}$ to $\{ 1, 2, \ldots, 8 \}$ where the $n$'th digit is not computable in $O(n)$ time. Such a function exists, for example, by the usual diagonalization technique. Interpret $f(n)$ as the $n$'th decimal digit of some ...


17

There is a combinatorial algorithm by Mahajan and Vinay that works over commutative rings: http://cjtcs.cs.uchicago.edu/articles/1997/5/contents.html


15

If you know the factorization of $m = p_1^{e_1} \cdots p_n^{e_n}$ you can compute modulo each $p_i^{e_i}$ separately and then combine the results using Chinese remaindering. If $e_i = 1$, then computing modulo $p_i^{e_i}$ is easy, since this is a field. For larger $e_i$, you can use Hensel lifting.


15

For another non-answer, you might be interested in Sarnak’s conjecture (see e.g. http://gilkalai.wordpress.com/2011/02/21/the-ac0-prime-number-conjecture/, http://rjlipton.wordpress.com/2011/02/23/the-depth-of-the-mobius-function/, https://mathoverflow.net/questions/57543/walsh-fourier-transform-of-the-mobius-function), which basically states that Möbius ...


14

First of all, there is a formal definition of "quantum-NC", see QNC on the zoo. GCD is indeed a good candidate for a problem that could be shown to be in QNC, but it's not known to be in NC. However, finding a QNC algorithm for GCD is still an open problem. The feeling for which this is believed to be true comes from the fact that the Quantum Fourier ...


14

The following answer was originally posted as a comment on Gil's blog (1) Let $K=\mathbb{Q}(\alpha)$ be a number field, where we assume $\alpha$ has a monic minimal polynomial $f\in\mathbb{Z}[x]$. One can then represent elements of the ring of integers $\mathcal{O}_K$ as polynomials in $\alpha$ or in terms of an integral basis -- the two are equivalent. ...


12

More generally, for any constant $k\ge1$, there are transcendental numbers computable in polynomial time, but not in time $O(n^k)$. First, by the time hierarchy theorem, there exists a language $L_0\in\mathrm E$ not computable in time $O(2^{kn})$. We may assume $L\subseteq\{0,1\}^*$, and we may also assume that all strings $w\in L$ have length divisible by $...


11

To solve this problem there is a fast deterministic algorithm based on Smith normal forms whose worst-case complexity is upper-bounded by the cost of matrix-multiplication over the integers modulo $m$. For any matrix $A$, the algorithm outputs its Smith normal form, from where $\text{det}(A)$ can be easily computed. More concretely, define $\omega$ so that ...


9

First note that this algorithm only computes $\lceil \log_2 v \rceil$, and as the code is written, it works only for $v$ that fit in a $32$-bit word. The sequence of shifts and or-s that appears first has the function of propagating the leading 1-bit of $v$ all the way down to the least significant bit. Numerically, this gives you $2^{\lceil \log_2 v \rceil}...


8

This language is in $\mathsf{LOGSPACE}$ via trial division. It is also known logarithmic space is neccessary ([1]). For a generalization to sparse sets, see bounded language complete for NSPACE(log n)?. For hardness in binary case, see Are the problems PRIMES, FACTORING known to be P-hard?. [1] J. Hartmanis, L. Berman, On tape bounds for single letter ...


8

I’ll comment on why a relation as in the question $$ (2^n)! = \sum_{k=0}^{m-1} a_k b_k^{c_k} $$ (for every $n$) helps factoring. I can’t quite finish the argument, but maybe someone can. The first observation is that a relation as above (and more generally, the existence of poly-size arithmetic circuits for $(2^n)!$) gives a poly-size circuit for computing $...


8

TL;DR The decimal expansion of a fixed rational number is not pseudorandom in the cryptographic sense, but irrational numbers (are conjectured to) exhibit some weaker but interesting forms of pseudorandom behavior. Roughly speaking, a sequence $s \in \{0, \ldots, B\}^n$ is pseudorandom with respect to distinguishers $\cal A$, if it cannot be distinguished (...


7

Your problem seems a special case of the turnpike reconstruction problem (for which no polynomial time algorithm is known). See for example: Shiteng Chen, Zhiyi Huang, and Sampath Kannan, "Reconstructing Numbers from Pairwise Function Values". Abstract: The turnpike problem is one of the few natural problems that are neither known to be NP-complete nor ...


5

Sorry if this answer doesn't tell anything nontrivial, but you don't seem to imply these results in the questionm. Consider first the problem of computing a modular exponentiation $ a^r \mod m $. You say above that you can compute this by repeated squaring modulo $ m $, and that this needs $ O(\log r) $ multiplications. This is true, and it's certainly ...


5

The question of how to find computable substructures of algebraic structures was studied by Jens Blanck and myself in the paper "Canonical Effective Subalgebras of Classical Algebras as Constructive Metric Completions". There we give general conditions on what it means for a substructure of an algebraic structure to be computable. Let me give a summary, but ...


5

Some comments (not really an answer). Let's classify 32-bit integers $c$ as follows: Type X: $c$ (as a binary string) is De Bruijn sequence (for all rotations, bits [27,31] are distinct). An example: 11111011100110101100010100100000 Type Y: bits [27,31] of $2^i \cdot c$ are distinct for $i = 0, 1, ..., 31$. This is what Leiserson et al. uses. Examples: ...


5

As mentioned by Daniel, you can find some informations in the book A Course in Computational Algebraic Number Theory (link). In particular, there are several ways of representing elements of number fields. Let $K=Q[\xi]/\langle\varphi\rangle$ be a number field with $\varphi$ a degree-$n$ monic irreducible polynomial of $\mathbb Z[\xi]$. Let $\theta$ be any ...


5

Start by putting $A$ into Jordan normal form, i.e., write $A=PJP^{-1}$ where $J$ is the Jordan normal form and $P$ is a suitably chosen invertible matrix. Then $A^k = PJ^k P^{-1}$, so without loss of generality I only need to consider possibilities for $A$ that are already in Jordan normal form. For $2\times 2$ matrices, there are only three interesting ...


5

Update: The description below is for a different problem (in which you have all pairwise distances in a set rather than pairwise distances between two distinct sets). I'll leave it up anyway since it is closely related. This problem is called the beltway problem, and is a special case of the general $d$-torus embedding problem. It is also closely related to ...


5

There are essentially only two algorithms that I'm aware of: Use repeated-squaring, along the lines you mentioned. Factor $n$ using a state-of-the-art algorithm, then use the Chinese remainder thoerem. If $p$ is prime, you can compute $a^{b^c} \bmod p$ efficiently by computing $b^c \bmod p-1$ using fast exponentiation, call the result $d$, then computing $...


4

Here is a suggestion, for $K = 6$ and $N = 251$. We are given a list $a_i - b_j \pmod{N}$. Start by taking one of them, without loss of generality $a_1-b_1$. Without loss of generality $b_1=0$, and we obtain the value of $a_1$. Now take another one, and hope that it is of the form $a_2-b_1$ (this happens with probability $5/35 = 1/7$), and deduce $a_2$. At ...


4

The state of the art here is: We can decide primality in polynomial time, but the fastest, general-purpose algorithm to $\underline{\rm find}$ the factors of an n-bit composite integer takes time $\approx 2^{n^{1/3}\log^{2/3}n}$. More to your question, a primality test is the same thing as a compositeness test. Therefore, we can easily implement the '...


3

I think your question is closely related to the set reconciliation problem, which is solved in this paper: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.20.5338 The problem of set reconciliation is to given two sets $A, B \subseteq [n]$ find $A \backslash B$ and $B \backslash A$ with as less communication as possible. If $B = [n]$, then you just ...


3

Here's a different approach, based upon iteratively finding numbers that cannot appear among $\{a_1,\dots,a_6\}$. Call a set $A$ an over-approximation of the $a$'s if we know that $\{a_1,\dots,a_6\} \subseteq A$. Similarly, $B$ is an overapproximation of the $b$'s if we know that $\{b_1,\dots,b_6\} \subseteq B$. Obviously, the smaller $A$ is, the more ...


3

Here's an observation that I think gives you a foothold, possibly enough of one to solve the problem. Suppose we have four differences $a_1-b_1$, $a_1-b_2$, $a_2-b_1$, $a_2-b_2$ that arise as the pairwise differences between two $a$'s and two $b$'s. Call this a quartet of differences. Notice that we have a non-trivial relationship: $$(a_1-b_1)-(a_1-b_2) =...


3

Yes, there are good (efficient) algorithms. This is completely solved, and the algorithms are widely used in the cryptographic community. If $\gcd(n,p-1)=1$, then everything is a $n$th residue. If $n$ divides $p-1$, then $a$ is a $n$th residue if and only if $a^{(p-1)/n} \equiv 1 \pmod p$. If $1<\gcd(n,p-1)<n$, $a$ is a $n$th residue if and only if ...


3

One other way to look at this, which brings in potentially all complexity classes above $\mathsf{E} = \mathsf{DTIME}(2^{O(n)})$, is to consider real numbers in their binary expansion. Any real number whose binary expansion doesn't end with $0^\infty$ or $1^\infty$ - i.e., which is not a dyadic rational - has a unique binary expansion. We can treat this ...


2

Paul Lemke Steven S. Skiena Warren D. Smith, Reconstructing Sets From Interpoint Distances, gave backtracking algorithm that runs in time $O(n^n \log n)$ for the beltway reconstruction problem. As far as I know, this is the best known. The exact complexity of the problem is not known. It is not known to be in $P$ and neither known to be $NP$-complete.


Only top voted, non community-wiki answers of a minimum length are eligible