Add code for computing n-th roots of unity

[Keno]

In many application of finite fields of practical interest, a common need to compute the an n-th root of unity in this finite field. This provides (randomized) algorithms for computing either an arbitrary n-th root or the unique minimum n-th root. Computing the latter is expensive and of little mathematical significance, but due to the randomized nature of the algorithm, users may want predictability in which root gets chosen.

This package seemed like a good place for it.

[codecov[bot]]

Codecov Report

Merging #3 into master will increase coverage by 0.55%. The diff coverage is 100%.

@@            Coverage Diff             @@
##           master       #3      +/-   ##
==========================================
+ Coverage   82.11%   82.66%   +0.55%     
==========================================
  Files          12       13       +1     
  Lines         559      571      +12     
==========================================
+ Hits          459      472      +13     
+ Misses        100       99       -1

Impacted Files	Coverage Δ
src/GaloisFields.jl	92.85% <ø> (ø)	:arrow_up:
src/PrimitiveRoots.jl	100% <100%> (ø)
src/Reinterpret.jl	77.77% <0%> (+11.11%)	:arrow_up:

---

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update 75858e8...f842081. Read the comment docs.

[codecov[bot]]

Codecov Report

Merging #3 into master will increase coverage by 0.55%. The diff coverage is 100%.

@@            Coverage Diff             @@
##           master       #3      +/-   ##
==========================================
+ Coverage   82.11%   82.66%   +0.55%     
==========================================
  Files          12       13       +1     
  Lines         559      571      +12     
==========================================
+ Hits          459      472      +13     
+ Misses        100       99       -1

Impacted Files	Coverage Δ
src/GaloisFields.jl	92.85% <ø> (ø)	:arrow_up:
src/PrimitiveRoots.jl	100% <100%> (ø)
src/Reinterpret.jl	77.77% <0%> (+11.11%)	:arrow_up:

---

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update 75858e8...07fcb67. Read the comment docs.

[tkluck]

Love it, thank you!

Am I right in thinking that this algorithm would work for any finite field, not just of prime characteristic? If so, maybe we should generalize to AbstractGaloisField and not just PrimeField (and use length(F) instead of char(F)).

[Keno]

It's quite possible that this variant will work, but the literature on primitive root search in non-prime fields is quite extensive and I haven't read through it sufficiently to know that there aren't some corner cases. I also don't have a use case for it that would give me confidence that the code is correct for that case. My preference would be to merge as is and then if and when somebody has a use case for the generalization, we can look into it.

[tkluck]

Oh, there's one more important comment. The thing we are computing here is a "primitive root of unity" no? Not a primitive root. These latter ones are actually in use in the ZechLog module so it's important to clearly distinguish these. What's a good way to name these functions to make that clear?

[Keno]

Yes, these's some overlapping confusing terminology. These are n-th primitive roots of unity in 𝔽p. A primitive element of 𝔽p (also known as the primitive root of 𝔽p, or the generator of 𝔽p*) is an p-1-th primitive root of unity in 𝔽p, so they are related concepts, but the order of the primitive root is implied when only the field is specified. Perhaps the way to resolve this is to just make the n argument optional and default to char(𝔽) - 1, in which case it matches the primitive element.

[Keno]

I think I've addressed all the review comments, except the extensions to AbstractGaloisField and the MultiplicativeGroup abstractions, which are probably better for separate PRs.

[tkluck]

Thanks @Keno ! I'll make a release soon.