Diffusion of arithmetic and bit operations

Question

I want to estimate when and wether different types of functions provide full or partial diffusion.

I'm trying to understand diffusion of basic operations, like:

• addtion,
• multiplication,
• xoring.

If we change one bit in $a$ how many bits will be changed in average in result $c$ if we do:

$a+b \mod n = c$

If we change one bit in $a$ how many bits will be changed in average in result $c$ if we do:

$a \oplus b \mod n = c$

If we change one bit in $a$ how many bits will be changed in average in result $c$ if we do:

$a \cdot b \mod n = c$

And what if we change one bit in $a$ how many bits will be changed in average in result $c$ if we do:

$(a >> 1) \cdot b \mod n = c$

Is it fairly easy to deduce or do I have to write a program to check it?

In xor case only one bit would be changed if we compute it for $a$ differing by one bit. But what with other cases? I think in case of $a >> 1$ nearly half of the bits will be changed, because if we switch two bits that way, we have about 50% probability that they would be the same or not. So simple $a >> 1$ could provide good diffusion (if we combine it with other mixing operations, just repeating this operation over and over, of course, makes no sense).

EDIT:

Let's consider $n$ equal to power of $2$.

Answer 1

You can visually inspect the diffusion of different operations using an avalanche diagram.

I've generated the avalanche diagrams of these operations, the sizes I used for $a$ and $b$ are 64 bits. The result is also a 64-bit variable.

The tool I use generates the diagrams for all bit changes instead of just $a$, but it should still be informative.

Diffusion of $a \oplus b$

As you guessed; with plain XOR, the output bit $c_n$ is only affected by input bits $a_n$ and $b_n$. Here's what that looks like.

Diffusion of $a + b$

A slight improvement is addition. You can see that instead of each bit only affecting itself, there is now a very slight diffusion around the bits.

Diffusion of $a \cdot b$

Multiplication provides a massive improvement. But multiplication only diffuses changes in one direction. And depending on the processor you are targeting, multiplications might be expensive or not constant time.

Diffusion by repeating simple mixers

If you take a bunch of invertible operations that somewhat diffuse the changes, and repetitively perform them, you can get much better results.

Below is an example with just XOR-shifts and add-shifts.

Here's the operations that are being performed. As you can see, individually none of those diffuse that much, but if you repeat them enough, the mixing is much better.

for (size_t i = 0; i < 4; i++) {
    // Mix a
    a ^= a >> 7;
    a += a << 13;
    a ^= a >> 9;

    // Mix b
    b ^= b >> 7;
    b += b << 13;
    b ^= b >> 9;

    // Shift a and b into each other
    u64 a_old = a;
    u64 b_old = b;
    a = (a_old << 8) | ((b_old >> 56) & 0xFF);
    b = (b_old << 8) | ((a_old >> 56) & 0xFF);

}

u64 c = a ^ b;