numlib::mpqs
-- Multi-polynomial
Quadratic Sievenumlib::mpqs
(n)
returns a proper factor of
n
, using some version of the quadratic sieve.
n
is returned if it is prime.
numlib::mpqs(n <, options>)
n |
- | integer |
options |
- | one of the options below |
InteractiveInput |
- | prompt the user for all parameters given below |
SieveArrayLimit=M |
- | For any polynomial f , f(x) is
tested for -M <= x <= M. M must be a
positive integer. |
Tolerance=t |
- | Sets an exponent t that is used to define
``smoothness'' of values investigated by the sieve: if the maximum of
the factorbase is b, let a value pass the first part of the
sieve step if it has presumably no prime divisor greater than
b^t. t must be a positive real number. |
Factorbase=l |
- | Define l to be the factor base.
l must be a list of primes; they are investigated whether
they divide a certain set of values of each polynomial. |
MaxInFactorbase=b |
- | the factorbase consists of all suitable primes that
are smaller than b . b must be a positive
integer. This option cannot be used together with
Factorbase . |
NumberOfPolynomials=N |
- | The number of polynomials the values of which are
tested for smoothness. N must be a positive integer. |
LargeFactorBound=K |
- | Define K to be the bound below which
every factor of a given value must be to make that value pass the
trial-division part of the sieve step and become a sieve report. All
prime numbers outside the factor base, but below that bound, are added
to the factor base if they divide at least two sieve reports.
K must be a positive integer. |
CollectInformation |
- | Do not return a prime factor of n , but
some information on the course of the algorithm. |
numlib::mpqs
returns a positive integer dividing
n
, or FAIL
if n
is not prime,
but a proper factor could not be found.
If the option CollectInformationhas been given, a list of equations is returned; each of the equations contains some piece of information on an intermediate result in some step of the algorithm.
numlib::mpqs
may
give you some insight how the algorithm works if you set the
information level yo a high value (see setuserinfo
).If n
is prime, it is returned.
>> numlib::mpqs(10000000019)
10000000019
Using the default parameters, no factor is found:
>> n:=300000000580000000019: numlib::mpqs(n)
FAIL
However, using more polynomials and a larger factor base, the input can be factored:
>> numlib::mpqs(n,MaxInFactorbase=200,NumberOfPolynomials=30)
30000000001
ExtendedInformation
has been renamed to
CollectInformation
.