Add support for custom Sieves.

[lleoha]

The title should actually be: "Support for custom Sieves or other means to generate primes of specific forms".

Rationale: In many cases one wants to have a prime with some additional constraints, e.g. with k most significant bits set or k least significant bits sets or both (e.g. take a look at safe primes defined in RFC3526. In my specific use case I want to have an RSA modulus with MSB set hence I need two primes which have two MSB bits set. I also want them for the reasons being out of scope of this description to be congruent to 3 mod 4, i.e. two LSB set (but not necessarily safe primes).

Currently I am using my own custom primality tests, but having a way to specify custom sieve (or whatever that would sieve out the prime candidate based on specified predicate) would allow me to use this crate.

Let me know what you think. I can work on implementation if there's an interest in that.

[fjarri]

The way to do it with the current API is to use the stuff from hazmat to roll your own BPSW test with required conditions.

I wonder if the best approach here is to separate the BPSW preset from sieving and allow the user use both as building blocks. This technically will not be a hazmat API, since BPSW without pre-sieving still works, it's just slower.

[lleoha]

@fjarri Definitely The way I imagined it is to make a Sieve a trait (which would basically just be blessed Iterator) and some kind of hazmat API that can take any Sieve implementation for generating primes.

[fjarri]

The trait is just Iterator<Item=T> where T: Integer (although perhaps it should be Item=Odd<T> instead). For your case you don't even need to write a sieve implementation, just filter() on the existing Sieve.

I'll make a draft of the new API this week so that we can iterate from there.

[lleoha]

@fjarri

For your case you don't even need to write a sieve implementation, just filter() on the existing Sieve

Yes, But in more general case probably many of the potential Sieve implementation will be somewhat a wrapper over existing Sieve (aka NoSmallPrimeFactorsSieve).

[dvdplm]

I'm not wholly convinced we need much here to implement what you need @lleoha .

Consider:

pub fn prime_from_iter<T>(sieve: &mut impl Iterator<Item = T>) -> T
where
    T: Integer + RandomMod,
{
    loop {
        if let Some(prime) = sieve.find(|num| is_prime_with_rng(&mut OsRng, num)) {
            return prime;
        }
    }
}

#[test]
fn test_prime_from_iter() {
    use crypto_bigint::U64;
    // Replace this with anything that yields `T`s of the form you like
    let mut sieve = (1..1000u64).map(|n| U64::from_limb_like(n.into(), &U64::ZERO));
    for _ in 1..50 {
        let p = prime_from_iter(&mut sieve);
        println!("Prime: {:?}", p);
    }
}

Isn't the natural interface for a Sieve to yield candidates one by one for the primality test (i.e. an iterator)?

Sieves can be built in a variety of ways and it might be tricky to come up with a trait that models them all (or even most of them).

[lleoha]

I'm not wholly convinced we need much here to implement what you need @lleoha .

Indeed there isn't much. The reason I suggested having custom Sieves is to generalize sieving. In vast majority cases the default "no small prime factors" is enough, but in the setting I work with I do need occasionally to have a prime of specific form.

[dvdplm]

I think it's difficult to generalize in a sane way, but I would love to be proven wrong! ;)

[fjarri]

Took a stab at it with #64. Not sure how sane it is, and whether we need all this stuff.