this post was submitted on 04 May 2024
15 points (94.1% liked)

Rust

6025 readers
4 users here now

Welcome to the Rust community! This is a place to discuss about the Rust programming language.

Wormhole

[email protected]

Credits

  • The icon is a modified version of the official rust logo (changing the colors to a gradient and black background)

founded 1 year ago
MODERATORS
top 11 comments
sorted by: hot top controversial new old
[–] solrize 6 points 6 months ago (1 children)

This is a pretty lame article. The idea is just use a bignum library, or a language with native bignums. While a few optimizations help, basically just generate random 1024 bit random numbers until you something that passes a pseudoprime test, and call it a day. The rest of the article converts the above into a beginning Rust exercise but I think it's preferable to not mix up the two.

From the prime number theorem, around 1/700th of numbers at that size are prime. By filtering out numbers with small divisors you may end up doing 100 or so pseudoprime tests, let's say Fermat tests (3**n mod n == 3). A reasonable library on today's machines can do one of those tests in around 1ms, so you are good.

RSA is deprecated in favor of elliptic curve cryptography these days anyway.

[–] farcaster 11 points 6 months ago (1 children)

The author pointed out they also could've just called openssl prime -generate -bits 1024 if they weren't trying to learn anything. Rebuilding something from scratch and sharing the experience is valuable.

[–] solrize 6 points 6 months ago (1 children)

There's two things going on in the exercise: 1) some introductory Rust programming; 2) some introductory math and crypto.

Maybe it's just me but I think it's better to separate the two. If you're going to do a prime number generation exercise, it will be easier in (e.g.) Python since the bignum arithmetic is built in, you don't have all the memory management headache, etc. If you're going to do a Rust exercise, imho it is better to focus on Rust stuff.

[–] farcaster 4 points 6 months ago

There isn't even any memory management in their code. And arguably the most interesting part of the article is implementing a bignum type from scratch.

[–] [email protected] 2 points 6 months ago (1 children)

Nice article, I enjoyed it. Why float sqrt has been used? Integer sqrt is way faster and easily supports integers of any lengths

[–] farcaster 1 points 6 months ago* (last edited 6 months ago) (1 children)

The builtin u64.isqrt seems to be available in nightly only, and additionally I guess the author didn't want to use any external crates as part of their self-imposed challenge. Though I think there may be an off-by-one result with f64.sqrt I don't think this functionally breaks their u64 code because they loop to root_n + 1.

https://doc.rust-lang.org/std/primitive.u64.html#method.isqrt

[–] [email protected] 1 points 6 months ago (1 children)

Algorithm is so plain and simple, it doesn’t require nightly or Rust specifically to implement.

[–] farcaster 0 points 6 months ago* (last edited 6 months ago) (1 children)

Well, yeah, but you asked why they didn't use integer sqrt. It's something many programming languages just don't have. Or if they do, it's internally implemented as a sqrt(f64) anyway, like C++ does.

Most CPUs AFAIK don't have integer sqrt instructions so you either do it manually in some kind of loop, or you use floating point...

[–] [email protected] 1 points 6 months ago (1 children)

Integer sqrt is usually not a library function and it’s very easy to implement, just a few lines of code. Algorithm is well defined on Wikipedia you read a lot. And yes, it doesn’t use FPU at all and it’s quite fast even on i8086.

[–] farcaster 1 points 6 months ago (1 children)

I doubt doing it in software like that outperforms sqrtss/sqrtsd. Modern CPUs can do the conversions and the floating point sqrt in approximately 20-30 cycles total. That's comparable to one integer division. But I wouldn't mind being proven wrong.

[–] [email protected] 2 points 6 months ago

Integer sqrt can be used for integers with any length, not only for integers fit into f64