# Query regarding Integer factorization

Let us consider a product $P$ (whose factors we do not know). Given a base $b$, such that all the Modulus Residues are calculated using powers of $b$ w.r.t. $P$.

For some (unknown) power $x$ we know the corresponding residue ($R_x$), i.e.:

$b^x\bmod P = R_x$.

Query 1: Without knowing (or calculating) the factorization of $P$ and value $x$, for a given $k$, (using $R_x$) is it possible to calculate $b^{(x-k)}\bmod P = R_{(x-k)}$ efficiently?

Query 2: Can the above procedure (if known/exists) help in factorization of $P$?

I am uncertain about how to achieve 1 and its relation to factorization if any.

You can calculate $b^k \bmod P$ efficiently for $k \geq 0$ using repeated squaring. There is no need to know the factorization of $P$. Furthermore, you can calculate $b^{-1} \bmod P$ (if it exists) efficiently using the Euclidean algorithm. This also doesn't require the factorization of $P$.
• Thank you but I am a little unclear. The objective is not to calculate $b^k$ but $b^{(x-k)}$ i.e. $k$ is an offset from $x$ ($x$ being unknown). Are you suggesting we can (unclear how?) calculate $b^{x-k}$ using $b^k$? – TheoryQuest1 Dec 16 '17 at 13:14
Yes, given $b^k$ you can compute $b^{x-k}$ by $b^x = b^x \times b^{-k}$. Yuval Filmus explains how to compute $b^{-k}$.
No, this doesn't appear to lead to a better algorithm for factoring $P$.