xiaodai
January 14, 2019, 1:01am
#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?

xiaodai
January 14, 2019, 2:29am
#2
`invmod`

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

1 Like

tkluck
January 14, 2019, 8:16am
#3
Depending on what you are using this for, you may be interested in https://github.com/tkluck/GaloisFields.jl .

xiaodai
January 14, 2019, 8:31am
#4
Doesn’t show how to use it though.

tkluck
January 14, 2019, 8:35am
#5
Oops. For your use case:

```
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.

tkluck
January 14, 2019, 7:42pm
#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.

one( F::Type{<:PrimeField}) = F(Reduced(), one(inttype(F)))
+(a::F, b::F) where F<:PrimeField = F(a.n + b.n)
-(a::F, b::F) where F<:PrimeField = F(a.n - b.n)
+(a::PrimeField) = a
-(a::PrimeField) = typeof(a)(Reduced(), char(typeof(a)) - a.n)
*(a::F, b::F) where F<:PrimeField = F(Base.widemul(a.n, b.n))
inv(a::F) where F<:PrimeField = F(Reduced(), invmod(a.n, char(F)))
/(a::F,b::F) where F<:PrimeField = a * inv(b)
//(a::F,b::F) where F<:PrimeField = a * inv(b)
iszero(a::PrimeField) = iszero(a.n)
# -----------------------------------------------------------------------------
#
# Constructors and promotion
#
# -----------------------------------------------------------------------------

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