# Finding multiplicative inverse modulo n

**URL:** <https://discourse.julialang.org/t/finding-multiplicative-inverse-modulo-n/19603>\
**Category:** General Usage\
**Created:** [January 14, 2019, 1:01am UTC](https://discourse.julialang.org/t/finding-multiplicative-inverse-modulo-n/19603 "2019-01-14T01:01:44Z")\
**Posts on this page:** 8\
**Page:** 1

<div class="post-metadata">

**Author:** ![xiaodai](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/xiaodai/32/15937_2.png) [@xiaodai](https://discourse.julialang.org/u/xiaodai)\
**Post date:** [January 14, 2019, 1:01am UTC](https://discourse.julialang.org/t/finding-multiplicative-inverse-modulo-n/19603/1 "2019-01-14T01:01:44Z")

</div>

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?

---

<div class="post-metadata">

**Author:** ![xiaodai](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/xiaodai/32/15937_2.png) [@xiaodai](https://discourse.julialang.org/u/xiaodai)\
**Post date:** [January 14, 2019, 2:29am UTC](https://discourse.julialang.org/t/finding-multiplicative-inverse-modulo-n/19603/2 "2019-01-14T02:29:25Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![tkluck](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tkluck/32/15769_2.png) [@tkluck](https://discourse.julialang.org/u/tkluck)\
**Post date:** [January 14, 2019, 8:16am UTC](https://discourse.julialang.org/t/finding-multiplicative-inverse-modulo-n/19603/3 "2019-01-14T08:16:25Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![xiaodai](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/xiaodai/32/15937_2.png) [@xiaodai](https://discourse.julialang.org/u/xiaodai)\
**Post date:** [January 14, 2019, 8:31am UTC](https://discourse.julialang.org/t/finding-multiplicative-inverse-modulo-n/19603/4 "2019-01-14T08:31:21Z")

</div>

Doesn’t show how to use it though.

---

<div class="post-metadata">

**Author:** ![tkluck](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tkluck/32/15769_2.png) [@tkluck](https://discourse.julialang.org/u/tkluck)\
**Post date:** [January 14, 2019, 8:35am UTC](https://discourse.julialang.org/t/finding-multiplicative-inverse-modulo-n/19603/5 "2019-01-14T08:35:18Z")

</div>

Oops. For your use case:

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

```

---

<div class="post-metadata">

**Author:** ![chakravala](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/chakravala/32/6832_2.png) [@chakravala](https://discourse.julialang.org/u/chakravala)\
**Post date:** [January 14, 2019, 4:23pm UTC](https://discourse.julialang.org/t/finding-multiplicative-inverse-modulo-n/19603/6 "2019-01-14T16:23:04Z")

</div>

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

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

---

<div class="post-metadata">

**Author:** ![tkluck](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tkluck/32/15769_2.png) [@tkluck](https://discourse.julialang.org/u/tkluck)\
**Post date:** [January 14, 2019, 7:42pm UTC](https://discourse.julialang.org/t/finding-multiplicative-inverse-modulo-n/19603/7 "2019-01-14T19:42:07Z")

</div>

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
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
julia> using GaloisFields
julia> F = @GaloisField! 4 α
𝔽₄
julia> α*(α+1)
1

```

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

> <https://github.com/tkluck/GaloisFields.jl/blob/master/src/PrimeFields.jl#L42>

---

<div class="post-metadata">

**Author:** ![chakravala](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/chakravala/32/6832_2.png) [@chakravala](https://discourse.julialang.org/u/chakravala)\
**Post date:** [January 14, 2019, 10:58pm UTC](https://discourse.julialang.org/t/finding-multiplicative-inverse-modulo-n/19603/8 "2019-01-14T22:58:33Z")

</div>

By the way, I have created a package called [Grassmann.jl](https://github.com/chakravala/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

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