1
$\begingroup$

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.

| cite | improve this question | |
$\endgroup$
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – TheoryQuest1 Dec 16 '17 at 13:14
  • 1
    $\begingroup$ Your question is itself unclear. But you can probably solve it using my answer. $\endgroup$ – Yuval Filmus Dec 16 '17 at 13:15
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.