Accelerating the pace of engineering and science

# Documentation Center

• Trial Software

# numlib::mpqs

 Note:   numlib::mpqs has been removed. Use ifactor instead.

### Use only in the MuPAD Notebook Interface.

This functionality does not run in MATLAB.

## Syntax

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

## Description

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

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 by ifactor, using this algorithm does not pay off.

## Parameters

 n Integer

## Options

 InteractiveInput Prompt the user for all parameters given below SieveArrayLimit Option, specified as SieveArrayLimit = M For any polynomial f, f(x) is tested for - M ≤ x ≤ M. M must be a positive integer. Tolerance Option, specified as 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 bt. t must be a positive real number. Factorbase Option, specified as 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 Option, specified as 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 Option, specified as NumberOfPolynomials = N The number of polynomials the values of which are tested for smoothness. N must be a positive integer. LargeFactorBound Option, specified as 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 divisor of n, but some information on the course of the algorithm.

## Return Values

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 CollectInformation has 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.

## References

[1] Silverman, R. "The multi-polynomial quadratic sieve", Math.Comp. 48 (1987), pp.329–339.