Suppose that $N = p_1^{a_1} p_2^{a_2} ... p_k^{a_k}$ with $p_i$ prime and $a_i \geq 1$.Given a representation of the factorization of $N$ and an integer $m$ (using alphabet $\Sigma = \{0,1,,\}$):Input: $\quad m,p_1, a_1, ..., p_k, a_k$ What is the time and space complexity of calculating the $m$-th bit of the binary representation of $N$?I asked a similar question on mathoverflow a few weeks ago, but didn't get a satisfactory answer.
Unique factorization representation and complexity
cc.complexity theory;reference request;nt.number theory