search

gazman-sdk / quadratic-sieve

Quadratic sieve implementation in Java
17 stars 3 forks source link

Adaptations for use. #1

Open wmacevoy opened 7 years ago

wmacevoy commented 7 years ago

I have an application with a set of numbers (all large potential composites, some obviously not). Can QS be adapted to commit a certain amount of work to factor, and then give up? I see your basic use just asks for a factoring, but there will be hard factor problems in the set; I just want to eliminate the simple composite cases.

An example of how do do this would be great, say with a range of b-bit numbers.

int n = 10000;
int b = 256;
SecureRandom rng = new SecureRandom();
BigInteger x0 = new BigInteger("2").pow(b-1);
BigInteger [] a = new BigInteger[n];
for (int i=0; i<n; ++i) {
  a[i]=x0.add(new BigInteger(b-1,rng));
}
// .... sieve(a, work/time limit)?
wmacevoy commented 7 years ago

This is also a theory question -- does QS do well at discovering composites that are not products of two large primes --- I really just want to eliminate unlikely choices. Thanks again...