adds the primes contained in the vector x (or the single integer x) to the table computed upon GP initialization (by pari_init in library mode), and returns a row vector whose first entries contain all primes added by the user and whose last entries have been filled up with 1's. In total the returned row vector has 100 components. Whenever factor or smallfact is subsequently called, first the primes in the table computed by pari_init will be checked, and then the additional primes in this table. If x is empty or omitted, just returns the current list of extra primes.

The entries in x are not checked for primality. They need only be positive integers not divisible by any of the pre-computed primes. It's in fact a nice trick to add composite numbers, which for example the function factor(x,0) was not able to factor. In case the message "impossible inverse modulo <some integermod >" shows up afterwards, you have just stumbled over a non-trivial factor. Note that the arithmetic functions in the narrow sense, like eulerphi, do not use this extra table.

The present PARI version 2.1.1 allows up to 100 user-specified primes to be appended to the table. This limit may be changed by altering NUMPRTBELT in file init.c. To remove primes from the list use removeprimes.

The library syntax is addprimes(x).

if x belongs to R, finds the best rational approximation to x with denominator at most equal to k using continued fractions.

The library syntax is bestappr(x,k).

finds u and v minimal in a natural sense such that x*u+y*v = gcd(x,y). The arguments must be both integers or both polynomials, and the result is a row vector with three components u, v, and gcd(x,y).

The library syntax is vecbezout(x,y) to get the vector, or gbezout(x,y, &u, &v) which gives as result the address of the created gcd, and puts the addresses of the corresponding created objects into u and v.

as bezout, with the resultant of x and y replacing the gcd.

The library syntax is vecbezoutres(x,y) to get the vector, or subresext(x,y, &u, &v) which gives as result the address of the created gcd, and puts the addresses of the corresponding created objects into u and v.

number of prime divisors of |x| counted with multiplicity. x must be an integer.

The library syntax is bigomega(x), the result is a long.

binomial coefficient \binom x y. Here y must be an integer, but x can be any PARI object.

The library syntax is binome(x,y), where y must be a long.

if x and y are both integermods or both polmods, creates (with the same type) a z in the same residue class as x and in the same residue class as y, if it is possible.

This function also allows vector and matrix arguments, in which case the operation is recursively applied to each component of the vector or matrix. For polynomial arguments, it is applied to each coefficient. Finally chinese(x,x) = x regardless of the type of x; this allows vector arguments to contain other data, so long as they are identical in both vectors.

The library syntax is chinois(x,y).

computes the gcd of all the coefficients of x, when this gcd makes sense. If x is a scalar, this simply returns x. If x is a polynomial (and by extension a power series), it gives the usual content of x. If x is a rational function, it gives the ratio of the contents of the numerator and the denominator. Finally, if x is a vector or a matrix, it gives the gcd of all the entries.

The library syntax is content(x).

creates the row vector whose components are the partial quotients of the continued fraction expansion of x, the number of partial quotients being limited to lmax. If x is a real number, the expansion stops at the last significant partial quotient if lmax is omitted. x can also be a rational function or a power series.

If a vector b is supplied, the numerators will be equal to the coefficients of b. The length of the result is then equal to the length of b, unless a partial remainder is encountered which is equal to zero. In which case the expansion stops. In the case of real numbers, the stopping criterion is thus different from the one mentioned above since, if b is too long, some partial quotients may not be significant.

If b is an integer, the command is understood as contfrac(x,lmax).

The library syntax is contfrac0(x,b,lmax). Also available are gboundcf(x,lmax), gcf(x), or gcf2(b,x), where lmax is a C integer.

when x is a vector or a one-row matrix, x is considered as the list of partial quotients [a_0,a_1,...,a_n] of a rational number, and the result is the 2 by 2 matrix [p_n,p_{n-1};q_n,q_{n-1}] in the standard notation of continued fractions, so p_n/q_n = a_0+1/(a_1+...+1/a_n)...). If x is a matrix with two rows [b_0,b_1,...,b_n] and [a_0,a_1,...,a_n], this is then considered as a generalized continued fraction and we have similarly p_n/q_n = 1/b_0(a_0+b_1/(a_1+...+b_n/a_n)...). Note that in this case one usually has b_0 = 1.

The library syntax is pnqn(x).

if n is a non-zero integer written as n = df^2 with d squarefree, returns d. If flag is non-zero, returns the two-element row vector [d,f].

The library syntax is core0(n,flag). Also available are core(n) ( = core(n,0)) and core2(n) ( = core(n,1)).

if n is a non-zero integer written as n = df^2 with d fundamental discriminant (including 1), returns d. If flag is non-zero, returns the two-element row vector [d,f]. Note that if n is not congruent to 0 or 1 modulo 4, f will be a half integer and not an integer.

The library syntax is coredisc0(n,flag). Also available are coredisc(n) ( = coredisc(n,0)) and coredisc2(n) ( = coredisc(n,1)).

x and y being vectors of perhaps different lengths but with y[1] ! = 0 considered as Dirichlet series, computes the quotient of x by y, again as a vector.

The library syntax is dirdiv(x,y).

computes the Dirichlet series to b terms of the Euler product of expression expr as p ranges through the primes from a to b. expr must be a polynomial or rational function in another variable than p (say X) and expr(X) is understood as the Dirichlet series (or more precisely the local factor) expr(p^{-s}). If c is present, output only the first c coefficients in the series.

The library syntax is direuler(entree *ep, GEN a, GEN b, char *expr)

x and y being vectors of perhaps different lengths considered as Dirichlet series, computes the product of x by y, again as a vector.

The library syntax is dirmul(x,y).

creates a row vector whose components are the positive divisors of the integer x in increasing order. The factorization of x (as output by factor) can be used instead.

The library syntax is divisors(x).

Euler's phi (totient) function of |x|, in other words |(Z/xZ)^*|. x must be of type integer.

The library syntax is phi(x).

general factorization function. If x is of type integer, rational, polynomial or rational function, the result is a two-column matrix, the first column being the irreducibles dividing x (prime numbers or polynomials), and the second the exponents. If x is a vector or a matrix, the factoring is done componentwise (hence the result is a vector or matrix of two-column matrices). By definition, 0 is factored as 0^1.

If x is of type integer or rational, an argument lim can be added, meaning that we look only for factors up to lim, or to primelimit, whichever is lowest (except when lim = 0 where the effect is identical to setting lim = primelimit). Hence in this case, the remaining part is not necessarily prime. See factorint for more information about the algorithms used.

The polynomials or rational functions to be factored must have scalar coefficients. In particular PARI does not know how to factor multivariate polynomials.

Note that PARI tries to guess in a sensible way over which ring you want to factor. Note also that factorization of polynomials is done up to multiplication by a constant. In particular, the factors of rational polynomials will have integer coefficients, and the content of a polynomial or rational function is discarded and not included in the factorization. If you need it, you can always ask for the content explicitly:

? factor(t^2 + 5/2*t + 1)
 %1 =
 [2*t + 1 1]
 
 [t + 2 1]
 
 ? content(t^2 + 5/2*t + 1)
 %2 = 1/2

See also factornf.

The library syntax is factor0(x,lim), where lim is a C integer. Also available are factor(x) ( = factor0(x,-1)), smallfact(x) ( = factor0(x,0)).

f being any factorization, gives back the factored object. If a second argument nf is supplied, f is assumed to be a prime ideal factorization in the number field nf. The resulting ideal is given in HNF form.

The library syntax is factorback(f,nf), where an omitted nf is entered as NULL.

factors the polynomial x modulo the prime p, using distinct degree plus Cantor-Zassenhaus. The coefficients of x must be operation-compatible with Z/pZ. The result is a two-column matrix, the first column being the irreducible polynomials dividing x, and the second the exponents. If you want only the degrees of the irreducible polynomials (for example for computing an L-function), use factormod(x,p,1). Note that the factormod algorithm is usually faster than factorcantor.

The library syntax is factcantor(x,p).

factors the polynomial x in the field F_q defined by the irreducible polynomial a over F_p. The coefficients of x must be operation-compatible with Z/pZ. The result is a two-column matrix, the first column being the irreducible polynomials dividing x, and the second the exponents. It is recommended to use for the variable of a (which will be used as variable of a polmod) a name distinct from the other variables used, so that a lift() of the result will be legible. If all the coefficients of x are in F_p, a much faster algorithm is applied, using the computation of isomorphisms between finite fields.

The library syntax is factmod9(x,p,a).

or x!: factorial of x. The expression x! gives a result which is an integer, while factorial(x) gives a real number.

The library syntax is mpfact(x) for x! and mpfactr(x,prec) for factorial(x). x must be a long integer and not a PARI integer.

factors the integer n using a combination of the Shanks SQUFOF and Pollard Rho method (with modifications due to Brent), Lenstra's ECM (with modifications by Montgomery), and MPQS (the latter adapted from the LiDIA code with the kind permission of the LiDIA maintainers), as well as a search for pure powers with exponents <= 10. The output is a two-column matrix as for factor.

This gives direct access to the integer factoring engine called by most arithmetical functions. flag is optional; its binary digits mean 1: avoid MPQS, 2: skip first stage ECM (we may still fall back to it later), 4: avoid Rho and SQUFOF, 8: don't run final ECM (as a result, a huge composite may be declared to be prime). Note that a (strong) probabilistic primality test is used; thus composites might (very rarely) not be detected.

The machinery underlying this function is still in a somewhat experimental state, but should be much faster on average than pure ECM as used by all PARI versions up to 2.0.8, at the expense of heavier memory use. You are invited to play with the flag settings and watch the internals at work by using GP's debuglevel default parameter (level 3 shows just the outline, 4 turns on time keeping, 5 and above show an increasing amount of internal details). If you see anything funny happening, please let us know.

The library syntax is factorint(n,flag).

factors the polynomial x modulo the prime integer p, using Berlekamp. The coefficients of x must be operation-compatible with Z/pZ. The result is a two-column matrix, the first column being the irreducible polynomials dividing x, and the second the exponents. If flag is non-zero, outputs only the degrees of the irreducible polynomials (for example, for computing an L-function). A different algorithm for computing the mod p factorization is factorcantor which is sometimes faster.

The library syntax is factormod(x,p,flag). Also available are factmod(x,p) (which is equivalent to factormod(x,p,0)) and simplefactmod(x,p) ( = factormod(x,p,1)).

x^{th} Fibonacci number.

The library syntax is fibo(x). x must be a long.

computes a monic polynomial of degree n which is irreducible over F_p. For instance if P = ffinit(3,2,y), you can represent elements in F_{3^2} as polmods modulo P.

The library syntax is ffinit(p,n,v), where v is a variable number.

creates the greatest common divisor of x and y. x and y can be of quite general types, for instance both rational numbers. Vector/matrix types are also accepted, in which case the GCD is taken recursively on each component. Note that for these types, gcd is not commutative.

If flag = 0, use Euclid's algorithm.

If flag = 1, use the modular gcd algorithm (x and y have to be polynomials, with integer coefficients).

If flag = 2, use the subresultant algorithm.

The library syntax is gcd0(x,y,flag). Also available are ggcd(x,y), modulargcd(x,y), and srgcd(x,y) corresponding to flag = 0, 1 and 2 respectively.

Hilbert symbol of x and y modulo p. If x and y are of type integer or fraction, an explicit third parameter p must be supplied, p = 0 meaning the place at infinity. Otherwise, p needs not be given, and x and y can be of compatible types integer, fraction, real, integermod or p-adic.

The library syntax is hil(x,y,p).

true (1) if x is equal to 1 or to the discriminant of a quadratic field, false (0) otherwise.

The library syntax is gisfundamental(x), but the simpler function isfundamental(x) which returns a long should be used if x is known to be of type integer.

if flag = 0 (default), true (1) if x is a strong pseudo-prime for 10 randomly chosen bases, false (0) otherwise.

If flag = 1, use Pocklington-Lehmer "P-1" test. true (1) if x is prime, false (0) otherwise.

If flag = 2, use Pocklington-Lehmer "P-1" test and output a primality certificate as follows: return 0 if x is composite, 1 if x is a small prime (currently strictly less than 341 550 071 728 321), and a matrix if x is a large prime. The matrix has three columns. The first contains the prime factors p, the second the corresponding elements a_p as in Proposition8.3.1 in GTM138, and the third the output of isprime(p,2).

In the two last cases, the algorithm fails if one of the (strong pseudo-)prime factors is not prime, but it should be exceedingly rare.

The library syntax is gisprime(x,flag), but the simpler function isprime(x) which returns a long should be used if x is known to be of type integer. Also available is plisprime(N,flag), corresponding to gisprime(x,flag+1) if x is known to be of type integer.

true (1) if x is a strong pseudo-prime for a randomly chosen base, false (0) otherwise.

The library syntax is gispsp(x), but the simpler function ispsp(x) which returns a long should be used if x is known to be of type integer.

true (1) if x is square, false (0) if not. x can be of any type. If n is given and an exact square root had to be computed in the checking process, puts that square root in n. This is in particular the case when x is an integer or a polynomial. This is not the case for intmods (use quadratic reciprocity) or series (only check the leading coefficient).

The library syntax is gcarrecomplet(x,&n). Also available is gcarreparfait(x).

true (1) if x is squarefree, false (0) if not. Here x can be an integer or a polynomial.

The library syntax is gissquarefree(x), but the simpler function issquarefree(x) which returns a long should be used if x is known to be of type integer. This issquarefree is just the square of the Moebius function, and is computed as a multiplicative arithmetic function much like the latter.

Kronecker (i.e.generalized Legendre) symbol ((x)/(y)). x and y must be of type integer.

The library syntax is kronecker(x,y), the result (0 or ± 1) is a long.

least common multiple of x and y, i.e.such that lcm(x,y)*gcd(x,y) = abs(x*y).

The library syntax is glcm(x,y).

Moebius mu-function of |x|. x must be of type integer.

The library syntax is mu(x), the result (0 or ± 1) is a long.

finds the smallest prime greater than or equal to x. x can be of any real type. Note that if x is a prime, this function returns x and not the smallest prime strictly larger than x.

The library syntax is nextprime(x).

number of divisors of |x|. x must be of type integer, and the result is a long.

The library syntax is numbdiv(x).

number of distinct prime divisors of |x|. x must be of type integer.

The library syntax is omega(x), the result is a long.

finds the largest prime less than or equal to x. x can be of any real type. Returns 0 if x <= 1. Note that if x is a prime, this function returns x and not the largest prime strictly smaller than x.

The library syntax is precprime(x).

the x^{th} prime number, which must be among the precalculated primes.

The library syntax is prime(x). x must be a long.

creates a row vector whose components are the first x prime numbers, which must be among the precalculated primes.

The library syntax is primes(x). x must be a long.

class number of the quadratic field of discriminant x. In the present version 2.1.1, a simple algorithm is used for x > 0, so x should not be too large (say x < 10^7) for the time to be reasonable. On the other hand, for x < 0 one can reasonably compute classno(x) for |x| < 10^{25}, since the method used is Shanks' method which is in O(|x|^{1/4}). For larger values of |D|, see quadclassunit.

If flag = 1, compute the class number using Euler products and the functional equation. However, it is in O(|x|^{1/2}).

Important warning. For D < 0, this function often gives incorrect results when the class group is non-cyclic, because the authors were too lazy to implement Shanks' method completely. It is therefore strongly recommended to use either the version with flag = 1, the function qfhclassno(-x) if x is known to be a fundamental discriminant, or the function quadclassunit.

The library syntax is qfbclassno0(x,flag). Also available are classno(x) ( = qfbclassno(x)), classno2(x) ( = qfbclassno(x,1)), and finally there exists the function hclassno(x) which computes the class number of an imaginary quadratic field by counting reduced forms, an O(|x|) algorithm. See also qfbhclassno.

composition of the binary quadratic forms x and y, without reduction of the result. This is useful e.g.to compute a generating element of an ideal.

The library syntax is compraw(x,y).

Hurwitz class number of x, where x is non-negative and congruent to 0 or 3 modulo 4. See also qfbclassno.

The library syntax is hclassno(x).

composition of the primitive positive definite binary quadratic forms x and y using the NUCOMP and NUDUPL algorithms of Shanks (à la Atkin). l is any positive constant, but for optimal speed, one should take l = |D|^{1/4}, where D is the common discriminant of x and y.

The library syntax is nucomp(x,y,l). The auxiliary function nudupl(x,l) should be used instead for speed when x = y.

n-th power of the primitive positive definite binary quadratic form x using the NUCOMP and NUDUPL algorithms (see qfbnucomp).

The library syntax is nupow(x,n).

n-th power of the binary quadratic form x, computed without doing any reduction (i.e.using qfbcompraw). Here n must be non-negative and n < 2^{31}.

The library syntax is powraw(x,n) where n must be a long integer.

prime binary quadratic form of discriminant x whose first coefficient is the prime number p. By abuse of notation, p = 1 is a valid special case which returns the unit form. Returns an error if x is not a quadratic residue mod p. In the case where x > 0, the "distance" component of the form is set equal to zero according to the current precision.

The library syntax is primeform(x,p,prec), where the third variable prec is a long, but is only taken into account when x > 0.

reduces the binary quadratic form x (updating Shanks's distance function if x is indefinite). The binary digits of flag are toggles meaning

1: perform a single reduction step

2: don't update Shanks's distance

D, isqrtD, sqrtD, if present, supply the values of the discriminant, \lfloor sqrt{D}\rfloor, and sqrt{D} respectively (no checking is done of these facts). If D < 0 these values are useless, and all references to Shanks's distance are irrelevant.

The library syntax is qfbred0(x,flag,D,isqrtD,sqrtD). Use NULL to omit any of D, isqrtD, sqrtD.

Also available are

redimag(x) ( = qfbred(x) where x is definite),

and for indefinite forms:

redreal(x) ( = qfbred(x)),

rhoreal(x) ( = qfbred(x,1)),

redrealnod(x,sq) ( = qfbred(x,2,,isqrtD)),

rhorealnod(x,sq) ( = qfbred(x,3,,isqrtD)).

Buchmann-McCurley's sub-exponential algorithm for computing the class group of a quadratic field of discriminant D. If D is not fundamental, the function may or may not be defined, but usually is, and often gives the right answer (a warning is issued). The more general function bnrinit should be used to compute the class group of an order.

This function should be used instead of qfbclassno or quadregula when D < -10^{25}, D > 10^{10}, or when the structure is wanted.

If flag is non-zero and D > 0, computes the narrow class group and regulator, instead of the ordinary (or wide) ones. In the current version 2.1.1, this doesn't work at all: use the general function bnfnarrow.

Optional parameter tech is a row vector of the form [c_1,c_2], where c_1 and c_2 are positive real numbers which control the execution time and the stack size. To get maximum speed, set c_2 = c. To get a rigorous result (under GRH) you must take c_2 = 6. Reasonable values for c are between 0.1 and 2.

The result of this function is a vector v with 4 components if D < 0, and 5 otherwise. The correspond respectively to

* v[1]: the class number

* v[2]: a vector giving the structure of the class group as a product of cyclic groups;

* v[3]: a vector giving generators of those cyclic groups (as binary quadratic forms).

* v[4]: (omitted if D < 0) the regulator, computed to an accuracy which is the maximum of an internal accuracy determined by the program and the current default (note that once the regulator is known to a small accuracy it is trivial to compute it to very high accuracy, see the tutorial).

* v[5]: a measure of the correctness of the result. If it is close to 1, the result is correct (under GRH). If it is close to a larger integer, this shows that the class number is off by a factor equal to this integer, and you must start again with a larger value for c_1 or a different random seed. In this case, a warning message is printed.

The library syntax is quadclassunit0(D,flag,tech). Also available are buchimag(D,c_1,c_2) and buchreal(D,flag,c_1,c_2).

discriminant of the quadratic field Q(sqrt{x}), where x belongs to Q.

The library syntax is quaddisc(x).

relative equation defining the Hilbert class field of the quadratic field of discriminant D. If flag is non-zero and D < 0, outputs [form,root(form)] (to be used for constructing subfields). If flag is non-zero and D > 0, try hard to get the best modulus. Uses complex multiplication in the imaginary case and Stark units in the real case.

The library syntax is quadhilbert(D,flag,prec).

creates the quadratic number omega = (a+sqrt{x})/2 where a = 0 if x = 0 mod 4, a = 1 if x = 1 mod 4, so that (1,omega) is an integral basis for the quadratic order of discriminant x. x must be an integer congruent to 0 or 1 modulo 4.

The library syntax is quadgen(x).

creates the "canonical" quadratic polynomial (in the variable v) corresponding to the discriminant D, i.e.the minimal polynomial of quadgen(x). D must be an integer congruent to 0 or 1 modulo 4.

The library syntax is quadpoly0(x,v).

relative equation for the ray class field of conductor f for the quadratic field of discriminant D (which can also be a bnf), using analytic methods.

For D < 0, uses the sigma function. flag has the following meaning: if it's an odd integer, outputs instead the vector of [ideal, corresponding root]. It can also be a two-component vector [lambda,flag], where flag is as above and lambda is the technical element of bnf necessary for Schertz's method. In that case, returns 0 if lambda is not suitable.

For D > 0, uses Stark's conjecture. If flag is non-zero, try hard to get the best modulus. The function may fail with the following message

"Cannot find a suitable modulus in FindModulus"

See bnrstark for more details about the real case.

The library syntax is quadray(D,f,flag).

regulator of the quadratic field of positive discriminant x. Returns an error if x is not a discriminant (fundamental or not) or if x is a square. See also quadclassunit if x is large.

The library syntax is regula(x,prec).

fundamental unit of the real quadratic field Q(sqrt x) where x is the positive discriminant of the field. If x is not a fundamental discriminant, this probably gives the fundamental unit of the corresponding order. x must be of type integer, and the result is a quadratic number.

The library syntax is fundunit(x).

removes the primes listed in x from the prime number table. In particular removeprimes(addprimes) empties the extra prime table. x can also be a single integer. List the current extra primes if x is omitted.

The library syntax is removeprimes(x).

sum of the k^{th} powers of the positive divisors of |x|. x must be of type integer.

The library syntax is sumdiv(x) ( = sigma(x)) or gsumdivk(x,k) ( = sigma(x,k)), where k is a C long integer.

integer square root of x, which must be of PARI type integer. The result is non-negative and rounded towards zero. A negative x is allowed, and the result in that case is I*sqrtint(-x).

The library syntax is racine(x).

g must be a primitive root mod a prime p, and the result is the discrete log of x in the multiplicative group (Z/pZ)^*. This function using a simple-minded baby-step/giant-step approach and requires O(sqrt{p}) storage, hence it cannot be used for p greater than about 10^{13}.

The library syntax is znlog(x,g).

x must be an integer mod n, and the result is the order of x in the multiplicative group (Z/nZ)^*. Returns an error if x is not invertible.

The library syntax is order(x).

returns a primitive root of x, where x is a prime power.

The library syntax is gener(x).

gives the structure of the multiplicative group (Z/nZ)^* as a 3-component row vector v, where v[1] = phi(n) is the order of that group, v[2] is a k-component row-vector d of integers d[i] such that d[i] > 1 and d[i] | d[i-1] for i >= 2 and (Z/nZ)^* ~ prod_{i = 1}^k(Z/d[i]Z), and v[3] is a k-component row vector giving generators of the image of the cyclic groups Z/d[i]Z.

The library syntax is znstar(n).