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