Implement more number theory functions

[ejmahler]

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.

[hauleth]

It would be great!

[koverstreet]

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.

[ejmahler]

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

[koverstreet]

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.

[hauleth]

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

[ejmahler]

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?

[vks]

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]

This issue was moved to rust-num/num-integer#3