Multiplicative Inverse mod-256 with No Division Operations

Background

Finding the multiplicative inverse in modular arithmetics can be accomplished with Extended Euclid's Algorithm, but that requires division operations and looping/recursion for an average of 6 iterations/depth (over all input values from 1..255).

This is a piece of ugly code that CLANG (or also GCC a bit less optimized) boils down to something finishing in less than 100~200 cycles on the tinyest 8-bit CPUs, in constant time, with no lookup tables, no multiplication/division/modulo instructions.

The Code

typedef unsigned char byte;

struct bit8
{    int a:1,b:1,c:1,d:1,e:1,f:1,g:1,h:1;
};

__attribute__((noinline))
byte inv8(byte _i)
{
    byte is {_i}, ix; bit8 i_1,i_2,i_3,i_4,i_5;

    is>>=1; ix=_i^is; i_1=*(bit8*)&ix;
    is>>=1; ix=_i^is; i_2=*(bit8*)&ix;
    is>>=1; ix=_i^is; i_3=*(bit8*)&ix;
    is>>=1; ix=_i^is; i_4=*(bit8*)&ix;
    is>>=1; ix=_i^is; i_5=*(bit8*)&ix;

    bit8 k {0,0,0, i_1.b, i_1.c&i_2.b,
        i_3.b^(i_1.d&!i_2.c&!i_3.b),
        (!i_4.b&!i_1.e&(i_3.c|!i_2.d)) ^ (!i_1.c&!i_2.b),
        (i_5.b^(i_1.e&i_2.c&!i_3.b))
        | (((i_2.e|i_1.f)^i_4.c) & (i_4.c|!i_3.d&!i_5.b))
    };

    return _i^*(byte*)&k;
};

Points of Interest

Note that the input parameter should be an ODD number, so the result can make sense, if you think about it.

The scheme does not seem to me to be extendable to wider integers... ideas, comments and questions welcome!

History

• 8^th July, 2022: Initial version