Previous Page Next Page Contents

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

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

Changes




Do you have questions or comments?


Copyright © SciFace Software GmbH & Co. KG 2000