<p>Suppose that $N = p_1^{a_1} p_2^{a_2} ... p_k^{a_k}$ with $p_i$ prime and $a_i \geq 1$.</p>

<p>Given a representation of the factorization of $N$ and an integer $m$ (using alphabet $\Sigma = \{0,1,,\}$):</p>

<p><b>Input:</b> $\quad m,p_1, a_1, ..., p_k, a_k$ </p>

<p>What is the time and space complexity of calculating the $m$-th bit of the binary representation of $N$?</p>

<p>I asked a <a href="https://mathoverflow.net/questions/156093/comparing-two-numbers-given-their-factorization">similar question on mathoverflow</a> a few weeks ago, but didn't get a satisfactory answer.</p>

CC BY-SA 3.0
2014-02-20T15:17:42.400Z
The simpler question about the $i$th bit of $a^b$: [Complexity of exponential function](http://cstheory.stackexchange.com/q/1811/).
Kaveh
CC BY-SA 3.0
2014-02-20T21:51:59.347Z
@Kaveh I think the question you mention is a special case of this one only when $a$ is prime. Not sure if this makes any difference.
Sasho Nikolov
<cc.complexity-theory><reference-request><nt.number-theory>
Unique factorization representation and complexity
Marzio De Biasi
# Unique factorization representation and complexity

(Asked by: username_0 on 2014-02-20)

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](https://mathoverflow.net/questions/156093/comparing-two-numbers-given-their-factorization) a few weeks ago, but didn't get a satisfactory answer.

**Tags:** cc.complexity-theory, reference-request, nt.number-theory

> **Comments:**
> **username_1**: The simpler question about the $i$th bit of $a^b$: [Complexity of exponential function](http://cstheory.stackexchange.com/q/1811/).  
> **username_2**: @username_1 I think the question you mention is a special case of this one only when $a$ is prime. Not sure if this makes any difference.  

---

## 0 answers

