search

EbTech / rust-algorithms

Common data structures and algorithms in Rust
MIT License
3.77k stars 220 forks source link

Miller rabin #13

Closed JaroPaska closed 4 years ago

JaroPaska commented 4 years ago

Added modular exponentiation along with the miller rabin primality test. Tests included. Also added vscode workspace stuff to the .gitignore.

JaroPaska commented 4 years ago

Also, I made the mod_inv and mod_exp functions private as you suggested, however, I think they are useful and I think people could benefit from them being public. If you do choose to keep them private, you can remove mod_inv as it currently has no uses in the code other than the test function.

EbTech commented 4 years ago

Also, I made the mod_inv and mod_exp functions private as you suggested, however, I think they are useful and I think people could benefit from them being public. If you do choose to keep them private, you can remove mod_inv as it currently has no uses in the code other than the test function.

Thanks! I agree that they're useful. Right now, this code is essentially duplicated by Field in num.rs. Your factoring algorithms highlight a shortcoming of Field: namely, that it can't dynamically specify the modulus. I guess const generics don't quite solve this either, so a new solution might be needed after all... we'll figure something out.

JaroPaska commented 4 years ago

Also, I made the mod_inv and mod_exp functions private as you suggested, however, I think they are useful and I think people could benefit from them being public. If you do choose to keep them private, you can remove mod_inv as it currently has no uses in the code other than the test function.

Thanks! I agree that they're useful. Right now, this code is essentially duplicated by Field in num.rs. Your factoring algorithms highlight a shortcoming of Field: namely, that it can't dynamically specify the modulus. I guess const generics don't quite solve this either, so a new solution might be needed after all... we'll figure something out.

I finally see what you mean. I avoided reading through Field because the description scared me off, but I see now it's essentially just modular arithmetic. Unfortunately, I don't think it is possible to integrate Field into these algorithms unless the modulus can be specified. Would it be too ugly to just code the MOD in as a variable and make it so that operations can only succeed under some conditions (eg. when adding two fields the MODs of both fields are the same) (I am currently pondering what other situations are legal).

EbTech commented 4 years ago

Also, I made the mod_inv and mod_exp functions private as you suggested, however, I think they are useful and I think people could benefit from them being public. If you do choose to keep them private, you can remove mod_inv as it currently has no uses in the code other than the test function.

Thanks! I agree that they're useful. Right now, this code is essentially duplicated by Field in num.rs. Your factoring algorithms highlight a shortcoming of Field: namely, that it can't dynamically specify the modulus. I guess const generics don't quite solve this either, so a new solution might be needed after all... we'll figure something out.

I finally see what you mean. I avoided reading through Field because the description scared me off, but I see now it's essentially just modular arithmetic. Unfortunately, I don't think it is possible to integrate Field into these algorithms unless the modulus can be specified. Would it be too ugly to just code the MOD in as a variable and make it so that operations can only succeed under some conditions (eg. when adding two fields the MODs of both fields are the same) (I am currently pondering what other situations are legal).

I might rename Field to something like ModularInt32. Its safe modular arithmetic has been helpful in contest problems with fixed modulus.

Storing a separate MOD with each integer would double the memory footprint and add dynamic checks that the MODs match; I'd like to avoid that. One solution might be to implement Field in terms of standalone functions like what you have, and expose both APIs. It's not ideal to have two APIs though...

JaroPaska commented 4 years ago

Alright, I think I've addressed everything that was brought up.