## `numlib::mpqs` -- Multi-polynomial Quadratic Sieve

#### Introduction

`numlib::mpqs``(n)` returns a proper factor of `n`, using some version of the quadratic sieve. `n` is returned if it is prime.

#### Call(s)

`numlib::mpqs(n <, options>)`

#### Parameters

`n` | - | integer
`options` | - | one of the options below

#### Options

`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.

#### Returns

`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.

#### Related Functions

`ifactor`

#### Details

- The multi-polynomial quadratic sieve is an algorithm to factor large integers without small prime factors. For small integers that can be factored within a reasonable amount of time in MuPAD, using this algorithm does not pay off. However, `numlib::mpqs` may give you some insight how the algorithm works if you set the information level yo a high value (see `setuserinfo`).

#### Example 1

If `n` is prime, it is returned.

    >> numlib::mpqs(10000000019)

                                    10000000019

#### Example 2

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

#### Background

- For more information about the algorithm, see Silverman, The multi-polynomial quadratic sieve, Math.Comp. 48 (1987), pp.329-339.

#### Changes

- The option `ExtendedInformation` has been renamed to `CollectInformation`.

Do you have questions or comments?
Copyright © SciFace Software GmbH & Co. KG 2000