Add a Prime class to the standard library or as a "blessed" shard

[watzon]

Ruby has Prime class which until recently was built in to the standard library and is very helpful for a number of cases, but especially when dealing with Cryptography. It would be nice to have such a class built in to Crystal's standard library as well, or at least living under the crystal github repo as a "blessed" shard. Has this been considered?

Cryptography is one of those things you don't want to get wrong, and as Crystal maintainers are most familiar with how to keep things fast, it would make sense to have it be an official project.

[jzakiya]

I created a Rubygem primes-utils - https://github.com/jzakiya/primes-utils. It provides a slew of methods to easily deal with all things prime. I also wrote the PRIME-UTILS HANDBOOK that explains the math, and the code for it. https://www.academia.edu/19786419/PRIMES-UTILS_HANDBOOK

It's currently at version 2.7. I've added more methods, but am waiting for Ruby 3.0, which is supposed to have multi-threading, before I do a gem version 3.0, and update the HANDBOOK for it.

I already have a working Crystal version of the gem, tested and ready to go too, but I'm also waiting for multi-threading in it to become stable and mature too, so I can do one update to both code bases.

I would be willing to provide my code for the Crystal stdlib if that is what you're proposing. The Crystal version is very robust and fast, because it inherently uses the BigInt library to deal with arbitrary sized integers. I have a whole test suite for all the methods, tested over BigInts. We're talking usable for integers into the thousands of digits.

For example, it has a very fast Miller-Rabin primality test method, which works on arbitrary sized integers. Below are times to test (correctly) for various primes, I recently ran on my laptop, using a single core (each base witness could be done in parallel).

https://primes.utm.edu/primes/lists/all.txt

n = ("70965694293".to_big_i << 200006) - 1       # 60,219 digits 5:29:16.2
n = ("4111286921397".to_big_i << 66420) + 5      # 20,008 digits    7:18.4
n = ("4122429552750669".to_big_i << 16567) + 7   #  5,003 digits      13.37
n = ("12379".to_big_i << 12379) - 1              #  3,731 digits      13.4

Here's the Miller-Rabin code on Rosetta Code.

https://rosettacode.org/wiki/Miller%E2%80%93Rabin_primality_test#Crystal

Let me know if this is of interest, and I can provide the code.

[watzon]

@jzakiya please make the shard public. I'm in need of a good prime implementation right now. It would be nice to get it integrated into the standard library as well, or at least have it be a "blessed" shard as mentioned, but as long as there's a good implementation out there I'll be good for now.

[jzakiya]

OK. Play with primes-utils in Ruby to get a feel for it, and read the HANDBOOK.

I'll look at cleaning up the Crystal code and making a shard out of it.

Let me know if there's some method (functionality) that's currently missing that you want and I will see if I can add it.

[oprypin]

I don't see any rationale or even description of what it would do.

"Ruby has" and "would be nice" don't count.

[jzakiya]

I don't see any rationale or even description of what it would do.

"Ruby has" and "would be nice" don't count.

Dealing with primes is necessary in various fields of applied and theoretical math, number theory, and cryptography.

My primes-utils create methods that operate directly on integers. See cited references.

[asterite]

I think this is something useful.

I don't think this belongs in the standard library.

[watzon]

Didn't feel like a description was necessary since Ruby's Prime class is fairly self explanatory, but ok. A Prime implementation like Ruby's should be capable of prime number generation in a fast way, as well as giving you the ability to do things like generate random primes in a range, loop over a range of primes using the built in Range literal, do prime division, etc.

Prime number generation is the backbone of many cryptography algorithms, as well as being useful in other applications such as number theory and theoretical math as mentioned above. I agree that this might not belong in the standard library, but at least having it as an officially maintained project should make sure it doesn't get lost in the ecosystem.

[RX14]

I don't think this will be added to the stdlib, I think the forum would be a great place to discuss this.

[jkthorne]

@watzon here might be a good place to start https://github.com/Souravgoswami/simple-sieve

[watzon]

@wontruefree I actually already wrote a full port of the Ruby version from ruby/prime. Includes the Eratosthenes Sieve.

[jkthorne]

I was looking into that but if you already did that. Awesome !

[jkthorne]

@watzon here is an initial pass at a shard. https://github.com/wontruefree/prime