15,666,183 members
Articles / Programming Languages / C++
Tip/Trick
Posted 8 Jul 2022

7.5K views
2 bookmarked

# Multiplicative Inverse mod-256 with No Division Operations

Rate me:
14 Jul 2022LGPL3
Find the multiplicative inverse mod-256 with no division operations
Targetting 8-bit CPUs with no division instruction (in hardware), this snippet finds the number X that, given N (both 8-bit unsigned) so that N*X=1 (mod 256).

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

C++
```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

• 8th July, 2022: Initial version

Written By
Chief Technology Officer Software Union
Austria
has been working a total of 14 years as programmer and system developer, plus some years of working as network technician and application supporter. Also experienced modeling, optimizing and administering FireBird and SqlServer databases. Loathes MySql.
Works with C++, C++/CLI, C#, JavaScript, PHP, PSQL and TextPad.

## Comments and Discussions

 First Prev Next
 Explanations on the algorithm would have been interesting Stephane Capo19-Jul-22 23:52 Stephane Capo 19-Jul-22 23:52
 Re: Explanations on the algorithm would have been interesting captnmac20-Jul-22 4:03 captnmac 20-Jul-22 4:03
 A table is much better Member 1492932115-Jul-22 4:24 Member 14929321 15-Jul-22 4:24
 Re: A table is much better darrellp15-Jul-22 8:33 darrellp 15-Jul-22 8:33
 Re: A table is much better captnmac17-Jul-22 6:28 captnmac 17-Jul-22 6:28
 Purpose? Member 1299508710-Jul-22 22:06 Member 12995087 10-Jul-22 22:06
 Re: Purpose? Andrea Simonassi11-Jul-22 22:28 Andrea Simonassi 11-Jul-22 22:28
 Re: Purpose? Member 129950879-Dec-22 8:18 Member 12995087 9-Dec-22 8:18
 Last Visit: 31-Dec-99 18:00     Last Update: 1-Jun-23 15:50 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.