On Fri, Aug 07, 2020 at 11:36:59PM +0200, Marc Glisse wrote:
> > > https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm is the most
> > > common way to compute the modular multiplicative inverse of a number. For
> > > 3
> > > and 2^32, it could tell us that 2863311531*3-2*2^32=1, so modulo 2^32
> > > 2863311531*3==1, and 3*X==5 is the same as 2863311531*3*X==2863311531*5,
> > > i.e. X==1431655767.
> >
> > wi::gcd ?
>
> That's the first place I looked, but this is only the regular Euclid
> algorithm, not the extended one. It tells you what the gcd is, but does not
> give you the coefficients of the Bézout identity. For 3 and 2^32, it would
> tell me the gcd is 1, while I want the number 2863311531 (inverse of 3).
>
> Ah, found it, there is mod_inv hidden in expr.c!
It can be certainly moved to wide-int.{h,cc} if you need it elsewhere.
Jakub
