2
$\begingroup$

Let $\mathbb{F}_p$ be a finite field of prime order $p$. Define $r_q : \mathbb{F}_p \to \mathbb{F}_p$ as $r_q (x) = x \bmod q$ with $q<p$. A tad more formally, treat $x$ as an integer in $[0, p)$ and then perform the modular reduction mod $q$.

For example, with $p = 5$ and $q=3$, we have:

$$0 \mapsto 0$$ $$1 \mapsto 1$$ $$2 \mapsto 2$$ $$3 \mapsto 0$$ $$4 \mapsto 1$$

NB. that this is not modular inversion or division.

Is there an efficient algorithm to compute $r_q (x)$ for $p, q$ fixed? Here $p, q$ are very big, like $\log_2 p\approx 128$ and $\log_2 q \approx 48$. I am particularly interested in the arithmetic circuit model, where we have the usual gates $+ : \mathbb{F}_p \times \mathbb{F}_p \to \mathbb{F}_p$ and $\times : \mathbb{F}_p \times \mathbb{F}_p \to \mathbb{F}_p$. But answers in other models are interesting.

$\endgroup$
  • $\begingroup$ You could use a binary search to find the largest $k$ such that $kq \le x$, and then just return $x - kq$. Since the largest $k$ could ever get is $p/q$, this should take $\log(p/q)$ subdivision steps. If multiplication is cheap then each step is $O(1)$ and you're done; otherwise, if you use the "galloping" approach (starting at $k=1$ and doubling it until $kq \le x$ is violated) and store all values of $kq$ generated this way (with $k$ being a power of 2), then each subdivision step's $kq$ value can be computed efficiently from the previous step's with a single addition or subtraction. $\endgroup$ – j_random_hacker Nov 8 '18 at 9:42
  • $\begingroup$ Thinking about it, I just described an algorithm for computing integer division. I realise you only care about the "remainder", but it's probably worth searching for other algorithms to do this. Maybe good old Euclidean division is better? $\endgroup$ – j_random_hacker Nov 8 '18 at 9:50
  • $\begingroup$ @j_random_hacker this seems like a good start, but there are two hidden costs (1) you need division by 2 in order to find the midpoint for binary search and (2) comparisons are probably expensive (especially in the arithmetic circuit model). but it's a good idea, I'll have to think about it.. $\endgroup$ – i52296 Nov 9 '18 at 2:49
  • $\begingroup$ Division by 2 is just shifting right by 1 bit, so I think it should be very cheap (possibly even free). I'm not familiar with the arithmetic circuit, but if comparing 2 integers is an expensive operation in this model, then I think it will be very hard to design any efficient algorithm, not only for this problem but for almost any problem. (Isn't it just a subtraction, followed by testing a carry/borrow flag bit?) $\endgroup$ – j_random_hacker Nov 9 '18 at 11:39
  • $\begingroup$ @j_random_hacker unfortunately there's no notion of bits in arithmetic circuits. Basically it is like a boolean circuit, except you have $+$ and $\times$ gates instead. You can get things like equality comparisons using $a^{p-1} \equiv 1 \pmod{p}$ for $a\neq 0$. I agree that it's a rather unfortunate restriction for this problem. But it seems that you've reduced the problem to division by 2, which is useful $\endgroup$ – i52296 Nov 10 '18 at 22:29

Your Answer

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

Browse other questions tagged or ask your own question.