Primes generation and checking with num-bigint

[vimmerru]

Hi,

Is there any solution for generation of primes, safe primes and prime checking with num-bigint?

[cuviper]

Nothing in the crate, and I'm not aware of anything published elsewhere. I do have a generic Miller-Rabin implementation that I use for Project Euler problems, but I'm not sure it's good enough to share. :)

[vimmerru]

Does it look fast enough for RSA-like crypto needs? For now i use OpenSSL, but consider switching to some rust-native solution to simplify cross-platforms builds and deployment.

[cuviper]

I'm not confident enough to answer that... Tell you what, I'll see if I can clean that up as an example program, at least, and we can go from there.

[vimmerru]

If you interested in we can benchmark it over OpenSSL together. My BN wrapper over OpenSSL is placed here https://github.com/hyperledger/indy-crypto/blob/master/libindy-crypto/src/bn/openssl.rs

I am interesting in performance of calls:

 pub fn generate_prime(size: usize) -> Result<BigNumber, IndyCryptoError> {
        let mut bn = BigNumber::new()?;
        BigNumRef::generate_prime(&mut bn.openssl_bn, size as i32, false, None, None)?;
        Ok(bn)
    }

    pub fn generate_safe_prime(size: usize) -> Result<BigNumber, IndyCryptoError> {
        let mut bn = BigNumber::new()?;
        BigNumRef::generate_prime(&mut bn.openssl_bn, (size + 1) as i32, true, None, None)?;
        Ok(bn)
}

[cuviper]

See #33 -- but I'll save you some suspense, it's definitely not as fast as OpenSSL. Make sure you at least run it with optimization though, e.g. cargo run --release --features rand --example primes.

[vimmerru]

Thanks for this work. I will check on my side this week.

[vks]

If you are ok with using non-Rust code, you could try rug or rust-gmp.

[dignifiedquire]

I have done some work on this, you can find more details about it here: https://github.com/rust-num/num-bigint/pull/33#issuecomment-406076473

[cmpute]

Although it's an old question, but I'm building a crate (num-prime) to support various algorithms for prime generation, primality checks and integer factorization with big integer implementation (right now num-bigint, in future maybe also support rug). Just list it here in case anyone is interested.