[Maxima-commits] CVS: maxima/doc/info Polynomials.texi,1.18,1.19 Number.texi,1.15,1.16 From: Andrej Vodopivec - 2006-03-21 23:11:58 ```Update of /cvsroot/maxima/maxima/doc/info In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv2720 Modified Files: Polynomials.texi Number.texi Log Message: Updating documentation with changes made by importing ifactor into src. Index: Polynomials.texi =================================================================== RCS file: /cvsroot/maxima/maxima/doc/info/Polynomials.texi,v retrieving revision 1.18 retrieving revision 1.19 diff -u -d -r1.18 -r1.19 --- Polynomials.texi 16 Nov 2005 06:43:34 -0000 1.18 +++ Polynomials.texi 21 Mar 2006 23:11:53 -0000 1.19 @@ -257,6 +257,8 @@ @code{factor (@var{expr}, p)} factors @var{expr} over the field of integers with an element adjoined whose minimum polynomial is p. +@code{factor} uses @code{ifactors} function for factoring integers. + @code{factorflag} if @code{false} suppresses the factoring of integer factors of rational expressions. @@ -275,13 +277,13 @@ be used otherwise the Berlekamp algorithm, which is the default, will be used. -@...{intfaclim} is the largest divisor which will be tried when -factoring a bignum integer. If set to @code{false} (this is the case when -the user calls @code{factor} explicitly), or if the integer is a fixnum (i.e. -fits in one machine word), complete factorization of the integer will -be attempted. The user's setting of @code{intfaclim} is used for internal -calls to @code{factor}. Thus, @code{intfaclim} may be reset to prevent Maxima from -taking an inordinately long time factoring large integers. +@code{intfaclim} if @code{false} maxima will give up factorization of +integers if no factor is found after trial divisions and Pollard's rho +method. If set to @code{false} (this is the case when the user calls +@code{factor} explicitly), complete factorization of the integer will be +attempted. The user's setting of @code{intfaclim} is used for internal +calls to @code{factor}. Thus, @code{intfaclim} may be reset to prevent +Maxima from taking an inordinately long time factoring large integers. Examples: @c EXAMPLES BELOW ADAPTED FROM examples (factor) @@ -729,25 +731,22 @@ @end deffn @defvr {Option variable} intfaclim -Default value: 1000 +Default value: true -@... NEED A LINK TO DESCRIPTION OF "BIGNUM" -@...{intfaclim} is the largest divisor which will be tried -when factoring a bignum integer. +If @code{true}, maxima will give up factorization of +integers if no factor is found after trial divisions and Pollard's rho +method and factorization will not be complete. -When @code{intfaclim} is @code{false} (this is the case -@... MAYBE WE WANT TO LINK TO A DESCRIPTION OF "FIXNUM" HERE -when the user calls @code{factor} explicitly), or if the integer is a fixnum -(i.e., fits in one machine word), -factors of any size are considered. -@...{intfaclim} is set to @code{false} when factors are computed in -@...{divsum}, @code{totient}, and @code{primep}. +When @code{intfaclim} is @code{false} (this is the case when the user +calls @code{factor} explicitly), complete factorization will be +attempted. @code{intfaclim} is set to @code{false} when factors are +computed in @code{divisors}, @code{divsum} and @code{totient}. @c ANY OTHERS ?? @c WHAT ARE THESE MYSTERIOUS INTERNAL CALLS ?? (LET'S JUST LIST THE FUNCTIONS INVOLVED) -Internal calls to @code{factor} respect the user-specified value of @code{intfaclim}. -Setting @code{intfaclim} to a smaller value may reduce the -time spent factoring large integers. +Internal calls to @code{factor} respect the user-specified value of +@code{intfaclim}. Setting @code{intfaclim} to @code{false} may reduce +the time spent factoring large integers. @c NEED EXAMPLES HERE @end defvr Index: Number.texi =================================================================== RCS file: /cvsroot/maxima/maxima/doc/info/Number.texi,v retrieving revision 1.15 retrieving revision 1.16 diff -u -d -r1.15 -r1.16 --- Number.texi 10 Feb 2006 16:03:00 -0000 1.15 +++ Number.texi 21 Mar 2006 23:11:53 -0000 1.16 @@ -1,3 +1,4 @@ + @c end concepts Number Theory @menu * Definitions for Number Theory:: @@ -344,6 +345,23 @@ @end deffn +@deffn {Function} ifactors (@var{n}) +For a positive integer @var{n} returns the factorization of @var{n}. If +@code{n=p1^e1..pk^nk} is the decomposition of @var{n} into prime +factors, ifactors returns @code{[[p1, e1], ... , [pk, ek]]}. + +Factorization methods used are trial divisions by primes up to 9973, +Pollard's rho method and elliptic curve method. + +@example +(%i1) ifactors(51575319651600); +(%o1) [[2, 4], [3, 2], [5, 2], [1583, 1], [9050207, 1]] +(%i2) apply("*", map(lambda([u], u[1]^u[2]), %)); +(%o2) 51575319651600 +@end example + +@end deffn + @deffn {Function} inrt (@var{x}, @var{n}) Returns the integer @var{n}'th root of the absolute value of @var{x}. @@ -398,6 +416,29 @@ @end deffn +@deffn {Function} power_mod (@var{a}, @var{n}, @var{m}) +Computes @code{a^n mod m} where @var{a} is an integer and @var{n} +and @var{m} are positive integers. + +@example +(%i1) power_mod(3, 15, 5); +(%o1) 2 +(%i2) ratsimp(3^15), modulus=5; +(%o2) 2 +@end example + +@end deffn + +@deffn {Function} next_prime (@var{n}) +Returns the smallest prime bigger than @var{n}. + +@example +(%i1) next_prime(27); +(%o1) 29 +@end example + +@end deffn + @deffn {Function} partfrac (@var{expr}, @var{var}) Expands the expression @var{expr} in partial fractions with respect to the main variable @var{var}. @code{partfrac} does a complete @@ -424,13 +465,40 @@ x + 2 x + 1 2 (x + 1) @end example - @end deffn @c IS IT POSSIBLE TO MAKE A DECLARATION SUCH THAT primep RETURNS true ?? @deffn {Function} primep (@var{n}) -Returns @code{true} if @code{n} is a prime, @code{false} if not. +Primality test. If @code{primep (n)} returns @code{false}, @var{n} is a +composite number and if it returns @code{true}, @var{n} is a prime number +with very high probability. + +For @var{n} less than 34155071728321 a deterministic version of Miller-Rabin's +test is used. If @code{primep (n)} returns @code{true}, then @var{n} is a +prime number. + +For @var{n} bigger than 34155071728321 @code{primep} uses +@code{primep_number_of_tests} Miller-Rabin's pseudo-primality tests +and one Lucas pseudo-primality test. The probability that @var{n} will +pass one Miller-Rabin test is less than 1/4. Using the default value 25 for +@code{primep_number_of_tests}, the probability of @var{n} beeing +composite is much smaller that 10^-15. + +@end deffn + +@defvr {Option variable} primep_number_of_tests +Default value: 25 + +Number of Miller-Rabin's tests used in @code{primep}. +@end defvr + +@deffn {Function} prev_prime (@var{n}) +Returns the greatest prime smaller than @var{n}. +@example +(%i1) prev_prime(27); +(%o1) 23 +@end example @end deffn @deffn {Function} qunit (@var{n}) ```