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 ...


11

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 $...


9

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 $...


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 (...


6

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 ...


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

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 ...


3

Codes/Lattices are certain combinatorial objects that are commonly used within TCS. A basic question for both of them is finding "short" codewords/lattice points, known as the Minimum Distance problem/Shortest Vector problem (MDP/SVP). Both have been known to be NP-hard under randomized reductions for 20+ years. Roughly 10 years ago, the NP hardness proof ...


2

Some heuristic evidence: to the best of our knowledge $\pi(n)$ looks like a simple function corrected by random fluctuations. Thus I’d expect a poly-time machine with a $\pi(n)$ oracle to be no stronger than such a machine with a random oracle, and w.r.t. a random oracle $X$ adding a separate random oracle $Y$ to $\mathsf{P}$ gives $\#\mathsf{P}^X \not\...


2

Using Fermat theorem, $a^p -a = 0 (\mod p) $ and if a and p are co-prime, then $ a^{p−1} − 1 =1(\mod p) $ So if u choose n to be a prime number(say p), then $a^{b^c} \mod p = a^{ (b^{c} \mod (p-1))} \mod p $ , Then you can use Fast Exponentiation trick in two levels, once for $b^c \mod p-1 $ then for $a^{b^c} \mod p $ I also suggest you to look at cses ...


2

Where does this constant comes from? Quoting: "On December 10, 2009, Mark Dickinson shaved off a couple operations by requiring v be rounded up to one less than the next power of 2 rather than the power of 2". [graphics.stanford.edu/~seander/bithacks.html] This particullar constant is a De Bruijn Sequence with Binary alphabet but with an extra ...


2

Both! You may want to read the answers to this related question, and the 1987 paper of Heather Woll, Reductions among number theoretic problems, Information and Computation 72 (1987) 167-179 cited in Jeffrey Shallit’s answer. This paper looks at the reduction between many problems in number theory, including primality, factorization, order-finding, ...


1

Knowing $F_n(1)$ or $F_n(-1)$ gives good randomized polynomial algorithm for the factorization of $n$. We have $|F_n(1)|=\phi(n)$ and $|F_n(-1)|=\sigma(n)$ by definition. $\phi(n)$ is Euler's totient function and $\sigma(n)$ is the sum of divisors function. The paper you link to proves the case for $\sigma(n)$. The same paper cites that the case for $\...


1

"Beltway Reconstruction Problem” - arxiv.org/pdf/1212.2386.pdf may help. Note that you're asking for the function corresponding to $P$ whose autocorrelation is the given function corresponding to $A$. I've often thought that there's some relation to factoring, at least to for the turnpike version. You can consider $A$ as an integer $Z=a_1x^1+a_2x^2+⋯a_Nx^...


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