Main Download Packages GP in your browser Timeline Funding Search Help FAQ Documentation Tutorials Mailing Lists Contributed GP scripts Development Ateliers PARI/GP Bugs Latest Changes Version Control Coding Guidelines PariDroid Tests & benchmarks Buildlogs Coverage Report Doc Coverage Benchmarks Miscellaneous WWW Stats Logo Fun! Links 
PARI/GP Frequently Asked QuestionsThis document is maintained by
Karim Belabas, the current PARI/GP maintainer (feedback welcome). It
strives to be useful for all versions of PARI/GP but, for the time being, it
documents the behaviour of the latest versions in the Questions
General InformationWhat is PARI/GP?PARI/GP is a widely used computer algebra system designed for fast computations in number theory (factorizations, algebraic number theory, elliptic curves...), but also contains a large number of other useful functions to compute with mathematical entities such as matrices, polynomials, power series, algebraic numbers, etc., and a lot of transcendental functions. PARI is a C library (C++  compatible). Writing C (or C++)
programs, and linking them to gp is an interactive shell giving access to PARI functions, easier to use. Lowlevel scripts are typically 4 times slower than directly written C code. Highlevel scripts, whose running time is dominated by a few calls to PARI functions, incur no penalty. GP is the name of gp's scripting language. What is gp2c?It is the GPtoC compiler. It compiles GP scripts to the C language, easing the task of writing PARI programs. It can automagically compile them to object code and load the resulting functions in gp. Lowlevel gp2ccompiled scripts typically run 3 or 4 times faster. gp2c currently only understands a subset of the GP language, and some functionalities are restricted to Unix operating systems. What is GNU readline? It is a library, which provide lineediting facilities (cursor movement,
command history, completion, etc). All applications built using this library,
for instance the
It is strongly advised to make sure that readline is present on your system
before building gp yourself (readline is included in the Windows binary we
distribute). In fact, before running What is GNU MP?GNU MP, or GMP for short, is a multiprecision library, which in particular provides asymptotically fast routines for arithmetic operations between integers. PARI multiprecision kernel can use native implementations or make good use of GMP if it is available. We advise you to download and install GMP before Configuring PARI. Make sure you download version 4.2 or more recent, because of this problem. See also How do I enable the GMP kernel. How can I report bugs or request new features?Please use PARI/GP's Bug Tracking System. Others may see and comment on your request, and you will be individually notified whenever a solution is committed to the GIT server. Need I formally cite PARI/GP in my paper?If you have used PARI/GP in the preparation of a paper, then yes, we would appreciate that. When an author formally cites the use of a computer algebra system or package in the bibliography of a paper, then system developers receive credit in citation indices. This practice encourages development of systems and packages and helps provide recognition for this work that is similar to that enjoyed by those who publish research articles. It also makes your experimental results reproducible. See also SIGSAM's statement of policy and bibliography of computer algebra systems. You may cite PARI in the following form (BibTeX format) @preamble("\usepackage{url}") @manual{PARI2, organization = "{The PARI~Group}", title = "{PARI/GP version {\tt 2.9.0}}", year = 2016, address = "Bordeaux", note = "available from \url{http://pari.math.ubordeaux.fr/}" } (please change the version number to match the version you actually used), which would translate to something like \bibitem{PARI2} The PARI~Group, PARI/GP version {\tt 2.9.0}, Bordeaux, 2016, \url{http://pari.math.ubordeaux.fr/}. What are the licensing terms?PARI/GP is free software. It is released under GNU's General Public License (GPL for short) as published by the Free Software Fundation, either version 2 of the License, or (at your option) any later version. Why use such a "restrictive" license as the GPL? Will you change it?The short answer to the second question is no. We are quite happy with the GPL. The original license (for all the 1.xx versions) was proprietary, too casually worded, and led to various conflicts. Starting from version 2.0, we wanted a well known license for the whole PARI/GP package, that would leave contributors secure with the future use of their code and, as far as possible, not prevent anyone from helping out. It was soon agreed that PARI/GP should become free software. The GPL was a natural choice. It is certainly wellknown, and it satisfied every developer involved in the project, as well as their respective employers. For the latter, the alternatives would have been more restrictive, certainly not closer to the LGPL, BSD, or the Artistic license. Most free Computer Algebra Systems also use the GPL, presumably for related reasons. Is this the PARI Web site?
Yes. There used to be a separation between
Is there a documentation?
The For more information about the algorithms used, check out Henri Cohen's two books (Graduate Texts in Mathematics 138 and 193, Springer). Has the documentation been translated to ...?No, English only. PARI is written by a small group of volunteers, and maintaining an adequate documentation in a single language has already proven to be a daunting task. Please do not harass us with translation requests or lectures on linguistic imperialism. Some developers happen to be native French speakers, and are indeed aware of a number of disturbing linguistic issues. But this does not imply we have unlimited time to translate existing documents, not to mention creating and maintaining new ones. PARI is free software, and you are welcome to undertake or sponsor a translation effort to the language of your choice. Please notify us if you do. What is the current version?
Current What is this stable/testing thing?We simultaneously maintain two versions (or branches) of PARI:
What version should I use?
It depends on your needs; we describe a few plausible scenarios below. First,
always use the most recent version in a given branch,
If
If you just want to give PARI/GP a try or have already run into problems with
If you run into problems with Release 2.1.4? What does this mean?The version number has three components M.m.p, e.g 2.1.4:
The idea is that patchlevel is bumped whenever a series of modifications
has been completed, and minor version number is increased when a
This has a number of implications in terms of interface stability. When will the next version be available?When it is ready. We have no definite schedule: if you are bothered by a particular problem or want to check out new improvements, please use the development version available via GIT. Here is the history of past releases. Can you unsubscribe me from (subscribe me to) the mailing list?Please do it yourself: depending on the list(s) you are interested in, please send an email to one of pariusersrequest@pari.math.ubordeaux.fr paridevrequest@pari.math.ubordeaux.fr pariannouncerequest@pari.math.ubordeaux.fr paricommitrequest@pari.math.ubordeaux.fr paribugsrequest@pari.math.ubordeaux.fr
Include either
I have a problem with one list. Who should I contact?Please email listman@pari.math.ubordeaux.fr Installation/Build ProblemsMath::Pari problemPlease report it directly to Math::Pari author and maintainer Ilya Zakharevich. PariEmacs problem
Please report to directly to the maintainer of the I fetched xxx.gz from the Download page, and the files are corruptedSome web browsers silently expand anything the web server tells them is gzip'd. And will nevertheless offer you to save it with the .gz ending, now inappropriate. You are probably looking at xxx under the name of xxx.gz.
Under Unix, Where is your CVS / Subversion server?They are gone. We now use GIT. What is GIT?GIT is an opensource revision control system. For the developers of PARI/GP, it provides networktransparent source control. For ordinary users it provides a very convenient way to obtain patched versions (source code only) in between releases, or follow development branches. GIT clients are available for
all major platforms: Unix, MacOS, Windows. In particular, the
When your GIT client connects to our GIT repository server for the first time, it copies the source code on your hard drive, exactly as if you had fetched and extracted a source release. PARI can then be compiled and installed in the usual way. Later connections upgrade your local copy using latest available sources, fetching only modified files. It is easy to restrict to a specific version branch, to released snapshots, or to revert your local repository to an older copy. More details on GIT setup for PARI. I upgraded from GIT and build fails
First, there is no guarantee that bleeding edge sources from the development
server will indeed compile. You may be unlucky, and fetch a broken version.
More probably, new code modules have been added, which were not compiled
in. Just try to run
Configure not found
If you get an error message of the form ./Configure in the toplevel directory. I built gp and line editing does not work!
You need to install GNU readline first,
then run withreadline withreadlineinclude withreadlinelib flags if you installed your library in an exotic place, or you
installed many and I am using withxxx but Configure still picks the wrong libraryFor instanceConfigure withgmp=path , but the default
libgmp is found instead of the intended one. The command
is an alias for
Configure withgmplib=path/lib
withgmpinclude=path/include and a common problem
is that lib64 was intended instead of lib .
The solution is to spell out a specific override as in
Configure withgmp=/usr/local withgmplib=/usr/local/lib64 [Linux:] readline/ncurses not found
Linux distributions have separate
Configure may also complain about a missing [Linux:] X11 graphic libraries not found
variant of this FAQ. It has been reported that in
SuSE distributions, one needs to install both Build fails with undefined symbolsBefore submitting a bug report, try the followingmake clean ./Configure (with proper options) make gpSometimes, a previous build (e.g. interrupted or after an update from GIT) interferes with subsequent compilation; make clean deletes all
cached information from the build directory.
My sources are in "directory name containing spaces". Build breaks mysteriously.This was specifically reported on Mac OS X, while trying to compile GNU readline. The exact message was: make: *** No rule to make target `/Volumes/Macintosh', needed by `readline.o'. Stop.
This was caused by a directory named " If renaming the offending directories is not an option, a simple solution was to do the following ln s "$HOME/readline5.0" /tmp/tmpreadlinethen cd to /tmp/tmpreadline and restart the
standard procedure. The above creates a derivation (symbolic link)
from /tmp/tmpreadline (doesn't contain spaces) to the directory we intended to work in. Adapt to your specific needs.
Using GIT sources, compilation fails in parse.yThis I can't build a 64bit sparcv9 executable!
On the env CC="gcc m64" ./Configure kernel=nonenone
or (Forte env CC="cc xarch=v9" CFLAGS="xarch=v9" ./Configure kernel=nonenone
You may want to specify You may run into further trouble if the linker picks up some 32bit
libraries instead of their 64bit equivalent. This might happen for
userinstalled libraries like I'm using SELinux and paridyn fails with 'Permission denied'This came up under Fedora Core 6 as Bug #621. Andrew van Herick reported the problem and worked around it by adjusting SELinux security policy. Using Fedora's graphical interfaces, this is done as follows:
I get an internal compiler error in ...
We do not try to support broken compilers. You may try to compile the
faulty code module using a lower optimization level (e.g. I'm using gcc2.96 and compilation fails in ...
I'm using MacOS X and ... produces a segmentation fault.As in Bug #565. First, try to upgrade your version of XCode. In particular, check the build number for gcc (e.g. in gp headers, Apple Computer Inc. build xxx). Builds < 5300 are very buggy, build 5363 works fine. I'm using MacOS X and make bench fails horribly.For instance
This is a painful bug in OS X Lion default
compiler (LLVM build 2335.15.00), reported as
Bug #1252. We suggest you try and install GCC4.5, the simplest option
being to use MacPorts; in this case
port install gcc45 export CC=/opt/local/bin/gccmp4.5 ./Configure
should see you home. Another possibility, as a temporary workaround, which
produces a slower rm f Odarwin*/mpker.o Odarwin*/mp.o make CFLAGS=O0 gp A [BUG] message appears in the 'program' test suiteIn version 2.9 and above, something is wrong. Please notify us.
In pre2.9 versions, the 'program' bench tried the My own program compiled OK, but when I try to run it, I get an "error while loading shared libraries: libpari.so"
On most platforms,
Since the link command in your $(CC) ... L$(LIBDIR) lpari lm
with
GP SpecificHow can I customize key bindings?This is possible only if the In this file, you can associate actions to sequences of keypresses, e.g. "\e[1;5C": forwardword "\e[1;5D": backwardword "\e[A": historysearchbackward "\e[B": historysearchforward
associates To determine what sequence is associated to a given combination of key
presses, you can hit I configured PARI to use readline and TAB completion only works if the completion is unique instead of showing all the possible completions?This is the default readline behaviour. When there is more than one match, hitting TAB once only completes the longest common prefix. Hitting TAB a second time then displays the list of possible completions. You can get the second behaviour directly after a single TAB by adding set showallifambiguous
in How to search readline's history of commands under gp?Readline provides a wealth of functions to search through the command history for lines containing a specified string. There are two search modes: incremental (search as you type) and nonincremental (type a prefix, then start searching). Some of these commands are bound by default (all of them incremental): reversesearchhistory (Cr) Search backward starting at the current line and moving `up' through the history as necessary. forwardsearchhistory (Cs) Search forward starting at the current line and moving `down' through the the history as necessary. Some are unbound (all of them nonincremental): nonincrementalreversesearchhistory Search backward starting at the current line and moving `up' through the history as necessary. nonincrementalforwardsearchhistory Search forward starting at the current line and moving `down' through the the history as necessary. historysearchforward Search forward through the history for the string of characters between the start of the current line and the point. historysearchbackward Search backward through the history for the string of characters between the start of the current line and the point.The last two provide GAP/Magmastyle history completion; to bind then to the UpArrow and DownArrow , add
"\e[A": historysearchbackward "\e[B": historysearchforward
in Result 'x' is history entry %n but they don't behave the same!
The function ? a = x+yx %1 = y ? variable(a) %2 = x ? variable(%1) %3 = y
How can I sort by increasing absolute value ?Replace the default comparison function by an anonymous closure: vecsort(v, (x,y) > sign( abs(x)  abs(y) ));or by a special purpose auxilliary function cmp(x,y) = sign( abs(x)  abs(y) ); vecsort(v, cmp);The latter solution unfortunately creates a globally visible cmp
function. You may use the following intermediate construction to restrict ad
hoc subroutines to a function scope:
Complicated_HighLevel_Function() = { my(cmp = (x,y)>sign( abs(x)  abs(y) )); ... vecsort(v, cmp); vecsort(w, cmp); ... } How can I write a `procedure' (void return value)?
Use I want to define functions within a user functionFor instance, the following happens to work init() = f(x) = x but this one does not init() = f(x) = x; g(x) = 2 * x
In fact, calling the latter defines the function x; g(x) = 2 * x which is not what was intended. In fact, the GP grammar states that the end of a function definition is the end of the longest expression sequence following the prototype. And the above is unfortunately a valid expression sequence. The solution is simple: init(a) = ( f(x) = x ); ( g(x) = 2 * x )
When a call to Uninitialized arguments are set to 0; I want an error insteadFor the sake of backward compatibility with previous GP versions (which
used the function arguments to declare local variables, before the
introduction of ? fun(x, y) = print(y); ? fun(2, 3) 3 ? fun(2) 0 In current GP, there is no reason to add unnecessary variables in the argument list, AND we have the possibility to explicitly set a default value as in ? fun(x, y = 0) = print(y); So a missing argument is probably a mistake and it would be more useful to get a warning than to silently go on with incorrect data, as for builtin functions: ? sin() *** too few arguments: sin() *** ^ To enable this (backward incompatible) behaviour, set
? default(strictargs, 1); ? fun(x, y = 0) = print(y); ? fun(1) 0 ? fun() *** at toplevel: fun() *** ^ *** in function fun: x,y=0 *** ^ *** missing mandatory argument 'x' in user function. Can I install() a C function returning a GEN which may be NULL?
The correct solution, as when trying to install functions whose prototype is not supported by GP, is to write a small wrapper function GEN wrapper_fun() { GEN z = fun(); if (!z) pari_err(...); // or any desired special handling return z; }and install that one instead. The following dirty trick also works in pure GP, without needing to mess
with C code (not recommended). wrapNULL(a = "result_was_NULL") = a; install(Fp_sqrt,GG); \\ returns NULL when arg1 not a square mod arg2 mysqrt(a, p) = wrapNULL(Fp_sqrt(a, p)); ? mysqrt(1, 3) %1 = 1 ? mysqrt(1, 3) %2 = "result_was_NULL" input() does not work from a scriptIt does. Read the following from a file (or copypaste it) fun() = { print("enter an integer a: "); a = input(); print("a^2 is "a^2) }
Then typing print("enter an integer a: "); a = input(); print("a^2 is "a^2)
does not work, is that print("a^2 is "a^2)
which is 0, then returns immediately. In the meantime, the expanded
How can I read from a file one item at a time?
Indeed, Another solution is to use the 1+1 2+2 3+3Then ? readvec(file) %1 = [2, 4, 6] A few amusing hacks: if you read in a file using for (i = first, last, x = eval( Str("%", i) ); \\ the ith history entry ... ) On a Unix system, you can use the following trick (courtesy of Markus Endres) to input the nth line of a given file: getline(n, file) = extern("sed n " n "p" file); On a Unix system, you can use the following beautiful hack (courtesy of
Bill Allombert) using named sh1$ mkfifo fifo sh1$ gp ? for(i=1, 10, print(i, read("fifo")) sh2$ perl ne 'system("echo '\''$_'\'' > fifo")' < data The possibility of handling file objects in GP without resorting to such extremities is in the TODO list. How can I read spaceseparated data from a file, one line at a time?Best answer: go and learn one of awk / sed / perl / python and preprocess your file! Second best answer: you asked for it readsplit(file) = { my(cmd); cmd = "perl ne \"chomp; print '[' . join(',', split(/ +/)) . ']\n';\""; eval( externstr(Str(cmd, " ", file)) ); } ? system("cat foo") 1 2 3 4 5 6 7 ? readsplit("foo") %2 = [[1, 2, 3], [4, 5, 6, 7]] How can I read numbers from a file and store them into a vector?
Use How can I input integers in hexadecimal ?
You may use the following function, courtesy of Martin Larsen on
hextodec(s) = { my(v=Vec(s), a=10,b=11,c=12,d=13,e=14,f=15, A=10,B=11,C=12,D=13,E=14,F=15, h); for(i=1,#v,h = (h<<4) + eval(v[i])); h; } ? hextodec("ff01") %1 = 65281The above does not work with gp2c, because of eval. Here is a more robust (and more efficient) version hextodec(s) = { my(v = Vecsmall(s), h = 0); for(i = 1, #v, h = (h<<4) + if(v[i]<=57, v[i]48, if(v[i]<=70, v[i]55, v[i]87)) );h; }In pari2.6.* and above, the above can be streamlined as hextodec(s) = { my(v = Vecsmall(s), h = 0); for(i = 1, #v, h = (h<<4) + if(v[i]<=57, v[i]48, v[i]<=70, v[i]55, v[i]87)); h; } Is there a tutorial for 'extern'?Here is a worked out example for Cremona's mwrank. How can I loop over permutations?n = 4; for (i = 1, n!, print( numtoperm(n, i) )) How can I loop over all subsets of S?for (i = 0, 2^#S  1, print( vecextract(S, i) )) How can I loop over subsets of S with k elements?forvec( v=vector(k, i,[1,#S]), print(vecextract(S,v)), 2) How can I loop over partitions?
In 2.6.1 and higher, use
For older versions, adapt the following code:
forpart() .
aux(n, m, v) = { v = concat(v,m); if(n, for(i=1, min(m,n), aux(ni, i, v)) , print(v) ); } partitions(n) = for(i=1, n, aux(ni, i, [])) How can I loop over divisors of polynomials?
Use I want bigger lists, 65533 is not enoughUse pari2.2.6 or newer: the limit is gone. Lists can be about as large as vectors (roughly 2^{24} entries). If you are using an older version, this is not straightforward, since the limit is hardcoded into the object representation.
I want more variables, 16383 is not enoughNot straightforward, this is hardcoded into the object representation.
How can I increase maximal recursion depth?The maximal recursion depth is governed by the maximal stack space allocated to the gp process (not to be confused with gp's stack). Use the following commands from the shell, before starting gp, to increase the process stack size to 20000 kbytes, say: If your shell is shbased (bash, ksh, sh, zsh): ulimit s 20000 If your shell is cshbased (csh, tcsh): limit stacksize 20000 Timing functions do not take system time into accountIndeed ? system("sleep 5") time = 0 ms ? for(i=1,10^4, write("testtimer.txt","12345678901")) time = 164 ms where the second command actually requires about 10 seconds on my machine.
This is intentional. PARI supports four timing functions If you really want wallclock time, use ./Configure time=ftime make clean && make gp Timer does not work when extern is involved
The time elapsed in commands called via extern("time cmd") instead of extern("cmd") A patch was proposed to take into account the children of the main gp process, but the current behaviour was deemed preferable. How can I timeout a command?Use ? alarm(1, 2*3) %1 = 6 ? alarm(1, bnfinit(x^30  2)) time = 1,000 ms. %2 = error("alarm interrupt after 1,000 ms.") ? E = alarm(1, bnfinit(x^30  2)); time = 1,000 ms. ? E \\ this is a t_ERROR object %3 = error("alarm interrupt after 1,000 ms.") FeaturesShould I use PARI's native kernel or the GMP kernel?The GMP kernel is faster than the native one. Here are detailed benchmarks for integer and floating point arithmetic, comparing the two kernels. The only drawback of using the GMP kernel is that it is sometimes slightly slower for tiny inputs, and that the GMPenabled PARI library is not compatible with the native one. In particular, all programs built using a native shared library must be rebuilt if it is replaced by a GMPenabled one. Can PARI handle arbitrarily large numbers?It depends on what you mean by "handle". On a 32 bit machines, PARI cannot even represent integers larger than 2^(2^29), or floating point numbers whose absolute binary exponent is larger than 2^30. But the main problem is that PARI's native kernel does not include enough fast algorithms that would enable it to process huge numbers in a decent time. (Integer multiplication is almost linear, but integer division is quadratic, for instance.) I would say mantissas of 10000 decimal digits are a sensible practical limit for intensive number crunching with PARI's native kernel. Using the GMP kernel, almost linear algorithms are available, and only the physical limitations of PARI's representation of integers and floats remain. Why are floating point operations so slow when precision is large?
Karatsuba multiplication was not enabled by default for type Almost linear algorithms are available through the GMP kernel. Why are divisions so slow?All division algorithms in the current PARI kernel are quadratic. Almost linear algorithms are available through the GMP kernel. How do I enable the GMP kernel?Type Configure withgmp or possibly Configure withgmp builddir=some/exotic/directory if you do not want to mess up with the binaries built using the native kernel. Using the GMP kernel, my session dies on a huge division!For instance (1 << (1<<25)) % (1<<(1<<24) + 1)
This is a general problem in GMP before version 4.2. It may allocate a huge
amount of memory in the process stack space (using Otherwise, one can increase the maximum size of the process stack segment before starting gp from the shell. Alternatively, you can configure an old GMP with configure enablealloca=mallocnoreentrant but this will slow down GMP. Do you have Fast Fourier Transforms?Not publicly exported. The library functions Why is cos(Pi) = 1 but sin(Pi) = 5.04870979 E29 and not exactly 0?
For gp,
In fact ? cos(Pi) + 1 %1 = 1.2744735289059618216 E57 How do I get the list of variables appearing in an expression ?Here is a possibility, using 2.7.* syntax: vars(E) = { my(v, L, t = type(E)); if (t == "t_RFRAC"  t == "t_POLMOD", return (setunion(vars(component(E,1)), vars(component(E,2)))) ); v = variable(E); if (!v, return ([])); L = [v]; E = Vec(E); for (i = 1, #E, L = setunion(L, vars(E[i]))); L; } ? vars([1/x+y^2, 0; Mod(a*z, z^2), O(t)]) %1 = [x, y, z, t, a] This code recursively inspects all components of an expression. It
works around the following complication: there is no builtin function
returning the components of an object, In version 2.8.* and above, use the builtin
? varables([1/x+y^2, 0; Mod(a*z, z^2), O(t)]) %1 = [x, y, z, t, a] How can I expand a multivariate polynomial ?You cannot. E.g ? simplify((a+b)*(c+d)) %1 = (c + d)*a + (c + d)*b The reason is that PARI only knows about univariate polynomials (whose coefficient may themselves be polynomials, thus emulating multivariate algebra). The result above is really a simplified form of ( c^1 + (d^1 + 0*d^0)*c^0 )*a^1 + ( (c^1 + (d^1 + 0*d^0)*c^0)*b^1 + 0*b^0 )*a^0 There is no flat or sparse representation of polynomials, and in particular no way to obtain parenthesesfree expanded expressions like a*c + a*d + b*c + b*d On the other hand, the following routine (courtesy of Michael Somos) comes close to what was requested: polmonomials(v)= { if (!v, return([])); if (type(v) != "t_POL", return([v])); concat( vector(poldegree(v)+1, n, variable(v)^(n1) * polmonomials(polcoeff(v,n1))) ) } For instance ? polmonomials((a+b)*(c+d)) %1 = [d*b, c*b, d*a, c*a] Mod(y*x,y1) returns 0!If you expected to get Mod(x, y1), you need to understand the concept of variable priority. Due to variable priority, the computation takes place in Q(y)[x] in which 0 is the correct result. Please see ??"Variable priorities, multivariate objects"@2 subst(p, x, polroots(p)[1]) is huge!
Assuming p has exact coefficients, then the output of
For instance, with 28 digits of accuracy: ? \p28 ? p = x^3  10^30; ? a = polroots(p)[2]; subst(p, x, a) %2 = 41.31322575 + 16.13098018*I \\ does not look like 0 ! ? \p 100 ? b = polroots(p)[2]; subst(p, x, b) %3 = 0.E76 + 0.E76*I \\ b fares better ? abs(a  b) / abs(a) %4 = 0.E28 \\ but a is indeed close to b Do you support sparse matrices/polynomials?No. How does PARI factor integers?
The integer factorizer implements a variety of algorithms: Trial Division
(all primes up to certain bound, plus userdefined private primetable, via
How efficient is factorint? How does it compare with other free implementations?It cannot compare with specialpurpose highperformance implementations, especially non portable ones. PARI's ECM is slower than GMPECM (portable), written by Paul Zimmermann on top of GMP. [comparative benches needed here]. PARI's Quadratic Sieve routinely (less than 1 minute) factors general numbers in the 60 digits range. A few minutes are needed for 70 digits, a few hours for 80 and it has not really been tested in the 90+ range. Besides PARI, we are aware of two other free MPQS implementations:
On my P4 1.6GHz, PARI's MPQS is 2 to 4 times faster than PPMPQS2.8 in the
60 digits range, 2 times faster for 70 digits, and gets increasingly
slower afterwards. E.g is already 3 times slower for 80 digits. We have not
tested Are the factors guaranteed to be primes?The factors output are not proven primes if they are larger than 2^{64}. They are BailliePomeranceSelfridgeWagstaff pseudoprimes, among which no composite has been found yet, although it is expected infinitely many exist. If you need a proven factorization, use fa = factor(N); isprime( fa[,1] )Another possibility is to set default(factor_proven, 1);This ensures that a true primality proof is computed whenever we do not explicitly ask for partial factorization. This will slow down PARI if largish primes turn up often. I monitor isprime() at \g2 and I get "untested integer" messages. Can I trust the output?Yes! The message looks like: *** isprime: Warning: IFAC: untested integer declared prime. It is harmless: during tests of PocklingtonLehmer type,
What primality tests do you use?
PARI's APRCL can prove primality of numbers with 1000 digits in a few hours. Some examples on a 2.8GHz Pentium IV:
Do you have AKS?In its present form (January 2006), the AgrawalKayalSaxena primality test is not practical for large numbers. Efficiency not being a primary concern, it is a simple exercise in GP programming to implement the algorithm. I monitor factorint() at \g4, and ECM seems to be stuckYou get messages of the form IFAC: trying LenstraMontgomery ECM ECM: working on 64 curves at a time; initializing for up to 50 rounds... ECM: time = 0 ms ECM: dsn = 12, B1 = 1800, B2 = 198000, gss = 128*420 ECM: time = 68920 ms, B1 phase done, p = 1801, setting up for B2 ECM: time = 1210 ms, entering B2 phase, p = 2017 ECM: time = 42990 ms [...] dsn = 72, B1 = 1073500, B2 = 118085000, gss = 1024*420 : and the last line is repeated seemingly forever. The short answer is: ECM is still making progress, although the diagnostics do not show it (detailed explanation). MPQS gives a "sizing marginal" warningThis problem is specific to version 2.2.10 and occurs while factoring smallish integers with MPQS. For instance factor(590772364016942232621279991); *** factor: Warning: MPQS: sizing marginal, index1 too large or too many primes in A. This diagnostic was left in place to detect suboptimal behaviour with respect to the chosen tunings. This is not a bug and the result is correct. The associated tuning problem is fixed in 2.2.11. Let K=nfinit(x^2+1). Routine xxx dies on ideal J = [5, 4; 0, 1]?
Assuming that ? K = nfinit(x^2+1); J = [5, 4; 0, 1]; nfisideal(K, J) %1 = 0 In fact, the two ideals above 5 are ? P = idealprimedec(K, 5); ? idealhnf(K, P[1]) %3 = [5 3] [0 1] ? idealhnf(K, P[2]) %4 = [5 2] [0 1] PARI routines transform suitable objects (element in K, prime ideal) to
an ideal (matrix in HNF), but do not check that matrices of the right
dimension do indeed correspond to ideals, which would be quite costly. If you
are unsure about how to input ideals, use
If you insist on finding the O_{K}module generated by the columns of your matrix, you may use something like IDEAL(nf, J) = { my(M,i,j); J = mathnf(J); M = [;]; for (i = 1, poldegree(nf.pol), for (j = 1, #J, M = concat(M, nfeltmul(nf, J[,j], nf.zk[i])) )); mathnf(M) }
For better efficiency, J is put in HNF form first. You can also use directly
IDEAL(nf, J) = { J = mathnf(J); mathnfmodid( idealhnf(nf, vecextract(J, "2..")), J[1,1] ) } As written, this assumes J is contained in O_{K} and does not work if J has Zrank 0 or 1, but you get the idea. How to compute nfinit(P) when I cannot factor disc(P)?Use something like nfinitpartial(P, B = 10^5) = nfinit( [P, B] ) This computes an nf structure from P, containing a tentative maximal order, which is only required to be maximal at primes less than B. The result is guaranteed to be correct whenever the field discriminant is Bsmooth, i.e. has no prime divisor larger than B. If it has (at least two distinct) large prime divisors, on the other hand, the result will be wrong. If such prime factors of the discriminant are known, you can use addprimes(p)
for each such p, or
The output can be certified, independently of B:
Which computations depend on the truth of the GRH?
The routines You can use bnf = bnfinit(P); bnfcertify(bnf)
to certify the Note that output from [ This paragraph is relevant for version numbers less than 2.4.0 ] In fact, bnfinit assumed more than GRH, namely that the ideals of norm less than 0.3 log( disc(K) )^{2} generate the class group of K. This is not known even under the GRH, which implies the above with 12 in place of 0.3, a famous result of Eric Bach; the constant can be further optimized depending on the signature and assuming the discriminant is large enough, but not down to 0.3 in any case. Also, there are counterexamples even for relatively large discriminants : unlucky random seeds actually gave a wrong result. So, technically, any result computed using a bnfinit(P,, [0.3, 12]) /* notice the double comma after P */ instead of This is slower, of course. At worst about 40 times slower when the original
result would have been right. The routine quadclassunit(D,, [0.2, 6]) Besides all functions using a ellap(E,p) is very slow when p is large, or even raises an exception ?If E/F_p has complex multiplication by a principal imaginary quadratic order, we use a very fast explicit formula (quadratic in log p). Otherwise we rely on ShanksMestre's babystep giant step method, whose runtime is unfortunately exponential. Hence this naive algorithm becomes unreasonable when p has about 30 decimal digits. To go beyond that (assuming you are running PARI version 2.4.3 or higher), please install the optional package SEAdata, implementing the SchoofElkiesAtkin algorithm. It should work at least up to 400 decimal digits, way beyond cryptographic sizes. Can I use Cremona's mwrank with gp ?You may use SAGE.
As for most external standalone programs without a graphical user interface,
you may also call What is a BIB ? What happens when my input doesn't make sense ?Many routines expect operands of a specified type and shape, for instance nf, bnf, bnr, ell, modpr structures, or satisfying certain documented preconditions, e.g. an integer which is actually a prime. For reasons of efficiency, PARI routines trust the user input and only perform minimal sanity checks. When a subtle undetected violation is performed, any of the following may occur: a regular exception is raised, the PARI stack overflows, a SIGSEGV or SIGBUS signal is generated, or we enter an infinite loop. The function can also quietly return a mathematically meaningless result: junk in, junk out. Bugs in this class (Bad Input Bugs, or BIBs for short) are never fixed whenever a noticeable code complication or performance penalty would occur. All PARI objects and internals are exposed and at your disposal, which is both convenient and unsafe. There are plans to add more semantic to PARI types so that e.g., an ell structure would record the fact that it is not an arbitrary vector, but actually associated to an elliptic curve. Not yet. intnum() gives ridiculous results
[This paragraph applies to versions prior to 2.2.9.]
For instance
? intnum(x = 0, 10^6, x^2 * exp(x^2)) %1 = 0e55 ? intnum(x=0, Pi, sin(2^11 * x)^2) %2 = 3.788253725 E46
The first integral should be indistinguishable from the integral to infinity,
which is Numeric integration evaluates the function at regularly spaced points in the integration interval, then uses a standard quadrature rule. This is tried for a few decreasing values of the subdivision diameter until the value appears to stabilize (in fact, was accurately predicted by interpolation from the four last values). This gives incorrect results for functions of period a large power of 2 as in the second example. Or if most of the weight is concentrated in a very small interval as in the first example, where the function is essentially 0 in most of the interval. For the time being, the user must break the integral into harmless chunks, or perform relevant change of variables herself. E.g make sure the function varies slowly, move singularities to the boundary or (better) remove them, restrict the interval to a region where the function is not negligible. Starting from version 2.2.9, we use the "double exponential method" instead of standard Romberg, and get better results: ? intnum(x = 0, 10^6, x^2 * exp(x^2)) %1 = 0.4431134622969907111829434676 ? intnum(x = 0, [[1], 2], x^2 * exp(x^2)) / (sqrt(Pi) / 4) %2 = 1.000000000000000000000000000 ? intnum(x=0, Pi, sin(2^11 * x)^2) %3 = 1.482067574055964668166042567 \\ not so good ? intnum(x=0, Pi, sin(2^11 * x)^2, 11) / (Pi/2) %4 = 1.000000000000000000000000000 \\ slower but perfect It still helps a lot to split the integral into pieces, and indicate the growth rate and oscillation pattern of the function at their boundary, and possibly to use more sampling points for oscillating functions. Otherwise, loss of accuracy may be expected. Modular objects behave strangelyFor instance ? Mod(1,2) * Mod(1,3) %1 = Mod(0, 1) ? Mod(1,2)*x + Mod(1,3) %2 = Mod(1,2)*x
Elementary operations involving Another example is ? Mod(0,2)^2 %3 = Mod(0, 2)
whereas one might expect To keep track of accuracy, you may use Is PARI suitable for high performance computation?It depends on what you mean by that. PARI was not written to handle huge objects (e.g. millions of digits, dimension in the thousands). It can do it, but different algorithms should be used for these ranges, which are not currently implemented. PARI is quite good for heavyduty computations in algebraic number theory. System SpecificHow can I get/use GP under WindowsA selfinstalling binary is available from the download page. How can I get GP2C under WindowsWe do not distribute any GP2C binaries for Windows currently: GP2C generates C files that need to be compiled with a C compiler. If you do not have a working C compilation environment, then GP2C cannot work for you. Users with a working C compilation environment can build GP2C from source. I cannot read in a GP file
I am assuming that you started the C:\Program Files\PARI This is where GP expects to find its input files. That is if you type in \r foo
this will work if and only if we have a file C:\Program Files\PARI
Update the Another possibility: some Windows editors, e.g. NotePad, automatically
append a Cut'n Paste does not work
Right click on the GP icon and change See also the GAP help pages on the subject. I cannot enter the ^key
You are running a keyboard driver for some nonEnglish languages. These
drivers catch the The Delete key does not work
This depends on your Windows installation and the compilers used when
building the binary. It may work properly, or it may emit a beep and
prints a tilde character ' I would like a 64bit

PARI/GP Development
Last Modified: 20161207 11:36:45
Copyleft © 20032016
the PARI group.