# 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

1 Like

Depending on what you are using this for, you may be interested in https://github.com/tkluck/GaloisFields.jl .

Doesn’t show how to use it though.

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

1 Like

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)
3

julia> @btime inv($(F(5))) 31.002 ns (0 allocations: 0 bytes) 3 julia> @btime inv(F(5)) 652.671 ns (2 allocations: 32 bytes) 3  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) 3  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) 1  If this topic interests, you, let me know of any features you are missing. 1 Like 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) 3e₁ julia> @btime inv($ans)
26.636 ns (0 allocations: 0 bytes)
5e₁


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.

1 Like