# Tag Info

Accepted

• 17.9k

### Is there a fast algorithm to quickly evaluate $a^{b^c}$ mod $n$?

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 ...
• 12.2k

### Algorithm to check whether a given set is Sidon

Probably OP's problem has no sub-quadratic algorithm, as it is 3-SUM-hard, per [1]: Corollary 1.2 [1]. Under the 3-SUM hypothesis, for all $\delta > 0$, determining whether a given set of $n$ ...
• 10.8k

### The factoring problem reduces to order finding or is it the other way around?

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

### Algorithm to check whether a given set is Sidon

In what range are the values in your set $S$? Note that if the range is not too large you can represent $S$ by a polynomial $P_S$ ($P_S = \sum_{s \in S} x^s$) and compute $P_S^{2}$ with the FFT ...

### Analytic Number theory in TCS

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

### Relation between transcendental numbers and computational complexity?

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 ...
• 37.4k
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))} \... • 129 2 votes ### Using the de Bruijn sequence to find the$\lceil\log_2 v \rceil$of an integer$v$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 ... • 21 2 votes ### Is prime-counting function #P-complete? 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 ... • 3,263 1 vote Accepted ### Is modular square roots modulo primes in$NC$? Square roots modulo$2^n$can be computed in (uniform)$\mathrm{TC}^0$. More generally, just like in On parallel complexity of modular inverse, given$X$and$M$in binary and$b$in unary such that$...
"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$. ...