Click here to Skip to main content
15,666,183 members
Articles / Programming Languages / C++
Posted 8 Jul 2022

Tagged as


2 bookmarked

Multiplicative Inverse mod-256 with No Division Operations

Rate me:
Please Sign up or sign in to vote.
3.67/5 (3 votes)
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).


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;

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_4.b&!i_1.e&(i_3.c|!i_2.d)) ^ (!i_1.c&!i_2.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!


  • 8th July, 2022: Initial version


This article, along with any associated source code and files, is licensed under The GNU Lesser General Public License (LGPLv3)

Written By
Chief Technology Officer Software Union
Austria 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

QuestionExplanations on the algorithm would have been interesting Pin
Stephane Capo19-Jul-22 23:52
professionalStephane Capo19-Jul-22 23:52 
AnswerRe: Explanations on the algorithm would have been interesting Pin
captnmac20-Jul-22 4:03
captnmac20-Jul-22 4:03 
QuestionA table is much better Pin
Member 1492932115-Jul-22 4:24
Member 1492932115-Jul-22 4:24 
AnswerRe: A table is much better Pin
darrellp15-Jul-22 8:33
darrellp15-Jul-22 8:33 
GeneralRe: A table is much better Pin
captnmac17-Jul-22 6:28
captnmac17-Jul-22 6:28 
QuestionPurpose? Pin
Member 1299508710-Jul-22 22:06
Member 1299508710-Jul-22 22:06 
AnswerRe: Purpose? Pin
Andrea Simonassi11-Jul-22 22:28
Andrea Simonassi11-Jul-22 22:28 
GeneralRe: Purpose? Pin
Member 129950879-Dec-22 8:18
Member 129950879-Dec-22 8:18 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

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