# Modular reduction in a finite field

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

• 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. – j_random_hacker Nov 8 '18 at 9:42
• 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? – j_random_hacker Nov 8 '18 at 9:50
• @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.. – i52296 Nov 9 '18 at 2:49
• 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?) – j_random_hacker Nov 9 '18 at 11:39
• @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 – i52296 Nov 10 '18 at 22:29