Implement more number theory functions

[cuviper]

From @ejmahler on June 30, 2016 22:59

In num_integer, I see an implementation of gcd.

I would like to implement some related number theory functions: modular exponentiation, extended euclid's algorithm, modular multiplicative inverse.

I'm also interested in prime factorization, euler's totient function, primitive roots, etc, but these might be too much.

Is there an interest for these functions in this library, to go alongside gcd? I'd be happy to implement the functions, tests, documentation, etc, I just want to make sure there's interest from the maintainers before I begin.

Copied from original issue: rust-num/num#202

[cuviper]

From @hauleth on July 1, 2016 12:0

It would be great!

[cuviper]

From @koverstreet on July 5, 2016 21:49

I'd like to see these implemented as generics over ring/field traits. Especially with specialization coming soon (or has it landed?), this is really the right way to go.

[cuviper]

From @ejmahler on July 6, 2016 5:3

Could you give a really quick example, to illustrate what you're picturing?

[cuviper]

From @koverstreet on July 6, 2016 5:11

Along the lines of a numeric tower (read up on Haskell's if you're curious) - except, I have no intention of trying to do a full numeric tower because no one seems to be able to get that right.

All I'm thinking for now is - define traits for Group, Ring, Field, etc. so we have a place to stick generic algorithms. I tend to think we shouldn't even have the various traits inherit from each other, at least for now - BigUint can always inherit from each of Group/Ring/whatever.

Basically keep it as simple as possible for now - nothing more than a place to stick things that should work on anything that's a group/ring/field.

gcd(), lcm()... perhaps a few others should then become generic functions on whatever the appropriate trait is, with specializations where it matters for performance.

[cuviper]

From @hauleth on July 7, 2016 22:44

I think that having additional structures defined using typenum would feel more "natural".

[cuviper]

From @ejmahler on July 17, 2016 12:50

I understand the high-level picture of what you're looking for, @koverstreet . A set of composable traits that can be included and maybe specialized for each type.

So starting small for now with jsut a "ring" trait that implements all sorts of modular arithmetic functions on this -- what's the correct way to implement this? I wouldn't call myself a rust expert yet so I need some guidance.

The following is what my mind jumps to, but this obviously doesn't compile because you can't implement a trait in terms of another trait -- you need a concrete type. But if we implement this trait for all the primitive types explicitly, that defeats the point of composition of these traits, doesn't it?

pub trait Ring {
    fn pow_mod(&self, exponent: &Self, modulo: &Self) -> Self;
}

impl Ring for Integer {
    fn pow_mod(&self, exponent: &Self, modulo: &Self) -> Self {
             //...
        }
}

We could implement these as standalone template functions:
pub fn pow_mod<T: Integer + Copy>(.......

But again that kind of defeats the point. So how should this be done?

[cuviper]

From @vks on March 17, 2017 17:16

I would like to implement some related number theory functions: modular exponentiation, extended euclid's algorithm, modular multiplicative inverse.

I implemented all of these some time ago here.

[cuviper]

Personally, I think it would be fine to do these without the more ambitious trait categories, but I'm also open to that if someone wants to try it.

[cmpute]

FWIW, I created num-modular and num-prime crates for the same purpose. They accept generic parameters and they're decently optimized.

Note that the implementation for num_bigint::BigUint is very naive, because advanced implementations need num_bigint to expose some of the inner APIs.