Is there an Efficient Way to Divide by a Mersenne Prime?

Question

Mersenne primes are used in Computer Science and Cryptography because they support fast modulo computation. If $p$ is a Mersenne prime, $n \bmod p$ can be computed with just a few add and shift operations.

Is there a well known, similarly fast, way to compute $\lfloor n/p \rfloor$? That is a way that uses only basic operations, such as shifts, adds and perhaps multiplications, but no divisions?

It doesn't appear to follow directly from the modulus computation. I have searched for all the terms I could think of, but nothing has appeared so far.

Answer 1

I think something like Algorithm 6 in https://ece.uwaterloo.ca/~ahasan/web_papers/technical_reports/web_lwpfi.pdf is what I was looking for:

def crandall(x, n, c):
    """ Returns divmod(x, 2**n-c) """
    q, r = x >> n, x & ((1<<n)-1)
    q_sum, r_sum = q, r
    while q > 0:
        q, r = q*c >> n, (q * c) & ((1<<n)-1)
        q_sum, r_sum = q_sum + q, r_sum + r
    t = 2**n - c
    while r_sum >= t:
        q_sum, r_sum = q_sum + 1, r_sum - t
    return q_sum, r_sum

Setting c = 1 gives a division free way to divide by Mersenne primes, and for general c it does Pseudo-Mersenne numbers.

Edit: I found a more efficient algorithm for this and other operations using Mersenne primes: https://arxiv.org/abs/2008.08654

Edit 2: Bug corrections for Python implementation - Firstrock