I'm trying to adapt this crate for no_std (and for use with crypto_bigint), and I'm wondering why in the miller_rabin test do we need to allocate all bases at once, instead of generating them on the fly with iterators?

https://github.com/mikelodder7/glass_pumpkin/blob/412a51b8235187c980a0194b6eae44ff02ac89aa/src/common.rs#L176

Encountered an intermittent panic when calling glass_pumpkin::prime::strong_check():

thread 'main' panicked at 'attempt to subtract with overflow', /home/jnichols/.cargo/registry/src/github.com-1ecc6299db9ec823/glass_pumpkin-0.5.0/src/common.rs:176:25

trials may be zero, so the subtraction in the range definition can underflow.

If I understand the Miller Rabin algorithm properly, then I think a larger issue lies in rewrite():

https://github.com/mikelodder7/glass_pumpkin/blob/412a51b8235187c980a0194b6eae44ff02ac89aa/src/common.rs#L192-L202

I think rewrite() is trying to find r (aka trials) and d from the following line in the algorithm, as given on wikipedia:

write n as 2^{r}·d + 1 with d odd (by factoring out powers of 2 from n − 1)

However the current rewrite() function simply returns trials = 0 and d = candidate - 1 (making d always positive) whenever candidate is odd.

This is because in #17 I was incorrect to assume that the API doesn't change: I didn't notice that some functions were reexported, since I didn't use them myself. Sorry! :(

The decomposition function for MR, rewrite() reads:

fn rewrite(candidate: &BigUint) -> (u64, BigUint) {
    let mut d = candidate - 1_u32;
    let mut trials = 0;

    while d.is_odd() {
        d >>= 1;
        trials += 1;
    }

    (trials, d)
}

It seems that it should be while d.is_even() instead (otherwise it always returns trials = 0, and perhaps that's why miller_rabin() sets trials to at least 5), but if I make that change is_prime_tests() fails. The strange thing is that those tests fail because the MR test fails, but the Lucas test still passes - but that may be an effect of #16? I am not sure how those test numbers were obtained, perhaps you can shed some light on it.

The function to generate a safe prime, gen_safe_prime, performs another primality test on the random prime that was just generated.

Specifically, in gen_safe_prime, gen_prime returns a probable prime, but the next check _is_safe_prime(...) && lucas(...) tests again that candidate is a prime. This is already done in gen_prime, so we now only need to check if (candidate - 1)/2 is also prime.

I am using glass_pumpkin for a teaching demo, and really just want 32-bit primes. Is there some reason for the restriction to 128 bits or more? Sure would be great to remove it for my use case.

When generating safe primes with a specific size via safe_prime::new, the resulting Integer sometimes has a size which is off by one or two bits.

Related: hyperledger-labs/agora-unknown_order#4

Lucas test (and by extension the Baillie-PSW test used in "strong_check") flags some primes as composites. A cursory search found no composites that passed (given the rarity of even 2-SPRPs beyond 2^64 this is fully expected) ,however the aforementioned behavior is sufficient to demonstrate that the test does not perform as predicted and may pass more composites than a correct implementation. Below is one example.

N
18446744073710004191
Claim
true

Witness
8300848561679324618

Factorization of n-1
2, 5, 1844674407371000419

The glass_pumpkin::safe_prime::new docs state that

Note: the bit_length MUST be at least 512-bits.

But the crate supports 128-bits or more.

First, thanks for the nice library! I'm using it to implement a threshold variant of paillier (code is here https://github.com/robinhundt/pht-crypto but still under construction).
I've noticed that my key generation takes a considerable amount of time due to the generation of safe primes being slow (taking minutes for safe primes of size 2048 bits on my machine). I've noticed that openssl is considerably faster in generating safe primes (using https://docs.rs/openssl/0.10.36/openssl/bn/struct.BigNumRef.html#method.generate_prime ).
If there is interest, I could send a PR with benchmarks comparing the openssl implementation and this one :) Maybe there are some easy improvements which could bring the performance closer to the one offered by openssl.

if length<16, check prime will also pass that r % p == 0 if r==p. The biggest prime of first 2048 prime is 16bit long.

This problem exist in almost every prime generation crates