Finding multiplicative inverse modulo n


Does anyone know of a package that has implemented fast algorithms for finding multiplication inverses modulo n? E.g.

3*5 = 15 == 1 (mod 7) and hence 3 and 5 are inverses modulo 7.

I looked at AbstractAlgebra and it doesn’t look like it has inverse algorithms?


invmod is the function e.g. invmod(5,7) == 3


Depending on what you are using this for, you may be interested in .


Doesn’t show how to use it though.


Oops. For your use case:

julia> using GaloisFields
julia> F = @GaloisField 7
julia> inv(F(5))
julia> 1/F(5)


It looks like they have the same performance, aside from the additional cost of constructing the GaloisFields element

julia> @btime invmod(5,7)
  31.165 ns (0 allocations: 0 bytes)

julia> @btime inv($(F(5)))
  31.002 ns (0 allocations: 0 bytes)

julia> @btime inv(F(5))
  652.671 ns (2 allocations: 32 bytes)

In the last example, the time for constructing F(5) is also accounted for, which takes some extra time.


Indeed! That’s the beauty of Julia’s zero-cost abstractions. The implementation uses invmod (see snippet below).

Construction only seems expensive because F is not a constant. That’s fixable:

julia> using GaloisFields; using BenchmarkTools
julia> const F = GaloisField(7)
julia> @btime inv(F(5))
  30.270 ns (0 allocations: 0 bytes)

I didn’t know that before your post triggered me to investigate. I’ll update the documentation accordingly.

FWIW, the benefit you get from using this package is that every operation happens mod p automatically. Moreover, you can use extension fields, like the field of 4 elements \{0,1,\alpha, \alpha + 1\} defined by \alpha(\alpha+1) = 1.

julia> using GaloisFields
julia> F = @GaloisField! 4 α
julia> α*(α+1)

If this topic interests, you, let me know of any features you are missing.


By the way, I have created a package called Grassmann.jl which can be used to define the Grassman product algebra on number fields.

Because your type is already <:Number, it is already compatible

julia> using GaloisFields,Grassmann

julia> const F = GaloisField(7)

julia> basis"2"
(++, e, e₁, e₂, e₁₂)

julia> @btime F(3)*e1
  21.076 ns (2 allocations: 32 bytes)

julia> @btime inv($ans)
  26.636 ns (0 allocations: 0 bytes)

So it is possible to use GaloisFields as a field for the VectorSpace, without any extra setup required.

I am interested in making my package compatible with any number fields out there.