Parity of modular operations

Remco Bloemen

2009-11-29, last updated 2014-03-03

For a problem I am trying to solve I want to find out if I can quickly calculate the odd/even parity of an inverse modulo a large prime. That is, I want to know:

(am2modm)mod2 \left( a^{m-2} \mod m \right) \mod 2

Where aa is typically less than a hundred thousand and mm is a 64 bit prime.

Parity of modular multiplication

Let’s first investigate the related question of the parity of the modular product:

(abmodm)mod2 \left( a \cdot b \mod m \right) \mod 2

Now, if aa or bb is zero then the parity will also be zero. The other case is however more interesting. Lets plot the parity for a few small primes mm.

ab-mod-3, ab-mod-5, ab-mod-7, ab-mod-11, ab-mod-13, ab-mod-17

Now a few things can be noticed, first that the whole thing is symmetric over the diagonal, a consequence of the commutativity of multiplication. Second, there are two anti-symmetries: the left half is the exact opposite of the right and the top half is the exact opposite of the bottom half. This leads to the relation:

(abmodm)((ma)b+1modm)mod2(ab+1modm)mod2 \begin{aligned} &\left(a \cdot b \mod m \right) \\ &\equiv \left( (m - a) \cdot b + 1\mod m \right)\mod 2 \\ &\equiv \left(- a \cdot b + 1 \mod m \right)\mod 2 \end{aligned}

The explanation is that a negative number gets subtracted from m, which is odd, such that the result has its parity flipped.

Another peculiarity in the pattern is that there seems to be some kind of grid xor-ed with the image. This grid corresponds to a bmod2\cdot b \mod 2 and can be xored out:

ab-mod-17-a \bigoplus ab-mod-17-b == ab-mod-17-c

The pattern that remains consists of hyperbolas corresponding to the number of mm’s that need to be subtracted to compute the modm\mod m. Since mm is odd each additional subtraction results in a parity flip.

The top left half of the hyperbola pattern appears reasonably well behaved, the rest appears distorted due to aliasing, but that is not a problem, since these can be calculated using the anti-symmetries. I verified that the top-left quarter stays well behaved for a few large primes mm.

Unfortunately, I can’t see a faster way to calculate hyperbolas than to perform an division, so speeding up the multiplication seems to be a dead end.

Parity of modular exponentiation

Next attempt, maybe some structure emerges in the exponentiation process. So let’s investigate

(abmodm)mod2 \left( a ^ b \mod m \right) \mod 2

Again, first the small primes:

a-pow-b-mod-3, a-pow-b-mod-5, a-pow-b-mod-7, a-pow-b-mod-11, a-pow-b-mod-13, a-pow-b-mod-17

It’s seems almost, but not entirely, random, like a cellular automaton or a broken pseudo random generator. Especially the next-to-last one, abmod13a^b \mod 13 seems to have a repeating pattern in it. Investigating some larger primes for mm I stumbled upon 281, which has the following pattern:

a-pow-b-mod-281
a-pow-b-mod-281

There is clearly a grid of white lines going on in this pattern. To investigate this further I took the discrete cosine transform:

a-pow-b-mod-281-F
a-pow-b-mod-281-F

A pattern of vertical lines emerges, which means that there should be a lot of correlation between the columns of the pattern.

Now lets take a prime number that does not have a white line grid, such as the next number, 283. It’s pattern is:

a-pow-b-mod-283
a-pow-b-mod-283

This pattern does seem completely random, however, when we apply the cosine transform the vertical lines re-appear, although less pronounced:

a-pow-b-mod-283-F
a-pow-b-mod-283-F

This seems to happen for every prime I try, and I can’t currently explain where it comes from. It seems that the length of the pattern is a divisor of φ(m)\varphi(m) and thus related to Fermat’s little theorem and Euler’s theorem, I should study this further sometime, but for now it doesn’t seem likely that this will result in faster computation of modular exponentiation parities.

Conclusion

A mathematician, like a painter or poet, is a maker of patterns. If his patterns are more permanent than theirs, it is because they are made with ideas.

—G. H. Hardy, A Mathematician’s Apology

For now there does not seem to be a simple pattern in the parity of modular operations that can be exploited.