Home Online Manual
Top
Back: pFactor
Forward: isOnCurve
FastBack: atkins_lib
FastForward: hyperel_lib
Up: crypto_lib
Top: Singular Manual
Contents: Table of Contents
Index: Index
About: About this document

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