Finding multiplicative inverse modulo n

#1

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?

#2

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

#3

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

#4

Doesn’t show how to use it though.

#5

Oops. For your use case:

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

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.

#7

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.

#8

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.