2
$\begingroup$

Given $k\in\Bbb N$ with $k<(\log_2N)^{\frac1\alpha}$ where $\alpha>2$ is fixed and $N$ being some integer such that $$N<\prod_{i=1}^k\pi_i^{a_i}$$ where $\pi_1,\pi_2,\dots,\pi_{k-1},\pi_k$ are unequal primes less than $\log_2N$ with some natural numbers $a_i$ and suppose we know the smallest non-negative member in each of the residue classes $$N\bmod\pi_i^{a_i}$$ at every $i\in\{1,\dots,k\}$, then given an integer $M<\log_2N$, is it possible to compute smallest non-negative member in the residue class $$N\bmod M$$ without first reconstructing $N$ by $\mathsf{CRT}$ or any other means?

If so is there an efficient algorithm (efficient here is running in $O( (\log_2N)^{\frac1\alpha}\log^cM)$ arithmetic operations where $c\geq0$ is fixed)? By arithmetic operations, I mean $\{+,-,\times,\bmod\}$ operations without regard to size of integer

Improve this question
$\endgroup$
1
  • $\begingroup$ Why do you want to do this? Are the $a_i$ small enough that none of the residues is actually equal to $N$? Have you looked at Knuth's work on representing integers modulo prime powers in this way and what are the benefits/drawbacks? If $M$ is that small, you might consider indeterminants of the form ax+b, where a is pi^a_i mod M, b is the residue of (N mod pi^a_i) mod M, and then see if you can find x big enough to answer your question. x might be bigger than can be efficiently read though. Gerhard "Not Understanding Why's Going On" Paseman, 2015.10.11 $\endgroup$
    – Gerhard Paseman
    Commented Oct 11, 2015 at 23:39

0

Reset to default

You must log in to answer this question.