|
|
D.12.3.21 quadraticSieve
Procedure from library crypto.lib (see crypto_lib).
- Usage:
- quadraticSieve(n,c,B,k); n to be factorized, [-c,c] the
sieve-intervall, B a list of primes,
k for using the first k elements in B
- Return:
- a list of factors of n or the message: no divisor found
- Note:
- The idea being used is to find x,y such that x^2=y^2 mod n then
gcd(x-y,n) can be a proper divisor of n
Example:
| | LIB "crypto.lib";
list L=primList(5000);
quadraticSieve(7429,3,L,4);
==> 17
quadraticSieve(1241143,100,L,50);
==> 547
|
|
