Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Implement more number theory functions #3

Open
cuviper opened this issue Dec 19, 2017 · 9 comments · May be fixed by #10
Open

Implement more number theory functions #3

cuviper opened this issue Dec 19, 2017 · 9 comments · May be fixed by #10

Comments

@cuviper
Copy link
Member

cuviper commented Dec 19, 2017

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
Copy link
Member Author

cuviper commented Dec 19, 2017

From @hauleth on July 1, 2016 12:0

It would be great!

@cuviper
Copy link
Member Author

cuviper commented Dec 19, 2017

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
Copy link
Member Author

cuviper commented Dec 19, 2017

From @ejmahler on July 6, 2016 5:3

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

@cuviper
Copy link
Member Author

cuviper commented Dec 19, 2017

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
Copy link
Member Author

cuviper commented Dec 19, 2017

From @hauleth on July 7, 2016 22:44

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

@cuviper
Copy link
Member Author

cuviper commented Dec 19, 2017

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
Copy link
Member Author

cuviper commented Dec 19, 2017

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
Copy link
Member Author

cuviper commented Dec 19, 2017

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
Copy link

cmpute commented Apr 22, 2022

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants