14 Integers
  
  One  of  the most fundamental datatypes in every programming language is the
  integer type. GAP is no exception.
  
  GAP integers are entered as a sequence of decimal digits optionally preceded
  by  a  +  sign  for positive integers or a - sign for negative integers. The
  size  of  integers in GAP is only limited by the amount of available memory,
  so you can compute with integers having thousands of digits.
  
    Example  
    gap> -1234;
    -1234
    gap> 123456789012345678901234567890123456789012345678901234567890;
    123456789012345678901234567890123456789012345678901234567890
  
  
  Note  that in a few places, only certain small integer values can be used. A
  small  integer  (also  referred  to  as  immediate  integer) is an integer n
  satisfying  INTOBJ_MIN  ≤  n  ≤  INTOBJ_MAX, where INTOBJ_MIN and INTOBJ_MAX
  equal  either  -2^28  and 2^28-1 (on 32-bit systems) or -2^60 and 2^60-1 (on
  64-bit  systems).  For  example,  the  elements of a range are restricted to
  small integers (see 21.22).
  
  Many  more  functions  that are mainly related to the prime residue group of
  integers  modulo  an  integer  are  described  in  chapter 15, and functions
  dealing with combinatorics can be found in chapter 16.
  
  
  14.1 Integers: Global Variables
  
  14.1-1 Integers
  
  Integers  global variable
  PositiveIntegers  global variable
  NonnegativeIntegers  global variable
  
  These  global  variables represent the ring of integers and the semirings of
  positive and nonnegative integers, respectively.
  
    Example  
    gap> Size( Integers ); 2 in Integers;
    infinity
    true
  
  
  Integers is a subset of Rationals (17.1-1), which is a subset of Cyclotomics
  (18.1-2).  See  Chapter 18  for  arithmetic  operations  and  comparison  of
  integers.
  
  14.1-2 IsIntegers
  
  IsIntegers( obj )  Category
  IsPositiveIntegers( obj )  Category
  IsNonnegativeIntegers( obj )  Category
  
  are   the   defining   categories   for   the   domains  Integers  (14.1-1),
  PositiveIntegers (14.1-1), and NonnegativeIntegers (14.1-1).
  
    Example  
    gap> IsIntegers( Integers );  IsIntegers( Rationals );  IsIntegers( 7 );
    true
    false
    false
  
  
  
  14.2 Elementary Operations for Integers
  
  14.2-1 IsInt
  
  IsInt( obj )  Category
  
  Every rational integer lies in the category IsInt, which is a subcategory of
  IsRat (17.2-1).
  
  14.2-2 IsPosInt
  
  IsPosInt( obj )  Category
  
  Every positive integer lies in the category IsPosInt.
  
  14.2-3 Int
  
  Int( elm )  attribute
  
  Int  returns  an  integer  int whose meaning depends on the type of elm. For
  example:
  
  If elm is a rational number (see Chapter 17) then int is the integer part of
  the quotient of numerator and denominator of elm (see QuoInt (14.3-1)).
  
  If  elm  is  an element of a finite prime field (see Chapter 59) then int is
  the smallest nonnegative integer such that elm = int * One( elm ).
  
  If  elm  is  a string (see Chapter 27) consisting entirely of decimal digits
  '0',  '1', ..., '9', and optionally a sign '-' (at the first position), then
  int  is the integer described by this string. For all other strings, fail is
  returned. See Int (27.9-1).
  
  The  operation  String (27.7-6) can be used to compute a string for rational
  integers, in fact for all cyclotomics.
  
    Example  
    gap> Int( 4/3 );  Int( -2/3 );
    1
    0
    gap> int:= Int( Z(5) );  int * One( Z(5) );
    2
    Z(5)
    gap> Int( "12345" );  Int( "-27" );  Int( "-27/3" );
    12345
    -27
    fail
  
  
  14.2-4 IsEvenInt
  
  IsEvenInt( n )  function
  
  tests if the integer n is divisible by 2.
  
  14.2-5 IsOddInt
  
  IsOddInt( n )  function
  
  tests if the integer n is not divisible by 2.
  
  14.2-6 AbsInt
  
  AbsInt( n )  function
  
  AbsInt  returns  the  absolute  value  of  the  integer  n,  i.e., n if n is
  positive, -n if n is negative and 0 if n is 0.
  
  AbsInt is a special case of the general operation EuclideanDegree (56.6-2).
  
  See also AbsoluteValue (18.1-8).
  
    Example  
    gap> AbsInt( 33 );
    33
    gap> AbsInt( -214378 );
    214378
    gap> AbsInt( 0 );
    0
  
  
  14.2-7 SignInt
  
  SignInt( n )  function
  
  SignInt returns the sign of the integer n, i.e., 1 if n is positive, -1 if n
  is negative and 0 if n is 0.
  
    Example  
    gap> SignInt( 33 );
    1
    gap> SignInt( -214378 );
    -1
    gap> SignInt( 0 );
    0
  
  
  14.2-8 LogInt
  
  LogInt( n, base )  function
  
  LogInt  returns  the integer part of the logarithm of the positive integer n
  with  respect  to  the  positive  integer  base,  i.e., the largest positive
  integer  e such that base^e ≤ n. The function LogInt will signal an error if
  either n or base is not positive.
  
  For   base   =  2  this  is  very  efficient  because  the  internal  binary
  representation of the integer is used.
  
    Example  
    gap> LogInt( 1030, 2 );
    10
    gap> 2^10;
    1024
    gap> LogInt( 1, 10 );
    0
  
  
  14.2-9 RootInt
  
  RootInt( n[, k] )  function
  
  RootInt  returns  the  integer part of the kth root of the integer n. If the
  optional  integer  argument  k  is not given it defaults to 2, i.e., RootInt
  returns the integer part of the square root in this case.
  
  If  n  is positive, RootInt returns the largest positive integer r such that
  r^k ≤ n. If n is negative and k is odd RootInt returns -RootInt( -n, k ). If
  n  is  negative and k is even RootInt will cause an error. RootInt will also
  cause an error if k is 0 or negative.
  
    Example  
    gap> RootInt( 361 );
    19
    gap> RootInt( 2 * 10^12 );
    1414213
    gap> RootInt( 17000, 5 );
    7
    gap> 7^5;
    16807
  
  
  14.2-10 SmallestRootInt
  
  SmallestRootInt( n )  function
  
  SmallestRootInt returns the smallest root of the integer n.
  
  The  smallest  root  of  an  integer n is the integer r of smallest absolute
  value for which a positive integer k exists such that n = r^k.
  
    Example  
    gap> SmallestRootInt( 2^30 );
    2
    gap> SmallestRootInt( -(2^30) );
    -4
  
  
  Note that (-2)^30 = +(2^30).
  
    Example  
    gap> SmallestRootInt( 279936 );
    6
    gap> LogInt( 279936, 6 );
    7
    gap> SmallestRootInt( 1001 );
    1001
  
  
  14.2-11 IsSquareInt
  
  IsSquareInt( n )  function
  
  IsSquareInt  tests whether the integer n is the square of an integer or not.
  This  test  is  much faster than the simpler RootInt(n)^2=n because it first
  tests whether n is a square residue modulo some small integers.
  
  14.2-12 ListOfDigits
  
  ListOfDigits( n )  function
  
  For  a  positive integer n this function returns a list l, consisting of the
  digits of n in decimal representation.
  
    Example  
    gap> ListOfDigits(3142);   
    [ 3, 1, 4, 2 ]
  
  
  14.2-13 Random
  
  Random( Integers )  method
  
  Random  for  integers  returns  pseudo  random  integers  between -10 and 10
  distributed  according  to  a  binomial  distribution. To generate uniformly
  distributed  integers  from  a  range, use the construction Random( [ low ..
  high ] )  (see Random (30.7-1)).
  
  
  14.3 Quotients and Remainders
  
  14.3-1 QuoInt
  
  QuoInt( n, m )  function
  
  QuoInt returns the integer part of the quotient of its integer operands.
  
  If  n and m are positive, QuoInt returns the largest positive integer q such
  that  q  *  m  ≤ n. If n or m or both are negative the absolute value of the
  integer part of the quotient is the quotient of the absolute values of n and
  m, and the sign of it is the product of the signs of n and m.
  
  QuoInt  is  used  in  a  method  for the general operation EuclideanQuotient
  (56.6-3).
  
    Example  
    gap> QuoInt(5,3);  QuoInt(-5,3);  QuoInt(5,-3);  QuoInt(-5,-3);
    1
    -1
    -1
    1
  
  
  14.3-2 BestQuoInt
  
  BestQuoInt( n, m )  function
  
  BestQuoInt  returns the best quotient q of the integers n and m. This is the
  quotient  such  that  n-q*m  has  minimal  absolute  value. If there are two
  quotients  whose  remainders have the same absolute value, then the quotient
  with the smaller absolute value is chosen.
  
    Example  
    gap> BestQuoInt( 5, 3 );  BestQuoInt( -5, 3 );
    2
    -2
  
  
  14.3-3 RemInt
  
  RemInt( n, m )  function
  
  RemInt returns the remainder of its two integer operands.
  
  If  m is not equal to zero, RemInt returns n - m * QuoInt( n, m ). Note that
  the  rules  given  for QuoInt (14.3-1) imply that the return value of RemInt
  has  the  same  sign  as  n and its absolute value is strictly less than the
  absolute  value  of  m.  Note also that the return value equals n mod m when
  both n and m are nonnegative. Dividing by 0 signals an error.
  
  RemInt  is  used  in  a  method for the general operation EuclideanRemainder
  (56.6-4).
  
    Example  
    gap> RemInt(5,3);  RemInt(-5,3);  RemInt(5,-3);  RemInt(-5,-3);
    2
    -2
    2
    -2
  
  
  14.3-4 GcdInt
  
  GcdInt( m, n )  function
  
  GcdInt returns the greatest common divisor of its two integer operands m and
  n, i.e., the greatest integer that divides both m and n. The greatest common
  divisor is never negative, even if the arguments are. We define GcdInt( m, 0
  ) = GcdInt( 0, m ) = AbsInt( m ) and GcdInt( 0, 0 ) = 0.
  
  GcdInt is a method used by the general function Gcd (56.7-1).
  
    Example  
    gap> GcdInt( 123, 66 );
    3
  
  
  14.3-5 Gcdex
  
  Gcdex( m, n )  function
  
  returns  a record g describing the extended greatest common divisor of m and
  n.  The  component  gcd  is  this  gcd, the components coeff1 and coeff2 are
  integer  cofactors  such  that  g.gcd = g.coeff1 * m + g.coeff2 * n, and the
  components  coeff3 and coeff4 are integer cofactors such that 0 = g.coeff3 *
  m + g.coeff4 * n.
  
  If  m  and  n  both are nonzero, AbsInt( g.coeff1 ) is less than or equal to
  AbsInt(n)  /  (2  *  g.gcd), and AbsInt( g.coeff2 ) is less than or equal to
  AbsInt(m) / (2 * g.gcd).
  
  If m or n or both are zero coeff3 is -n / g.gcd and coeff4 is m / g.gcd.
  
  The  coefficients  always  form  a  unimodular matrix, i.e., the determinant
  g.coeff1 * g.coeff4 - g.coeff3 * g.coeff2 is 1 or -1.
  
    Example  
    gap> Gcdex( 123, 66 );
    rec( coeff1 := 7, coeff2 := -13, coeff3 := -22, coeff4 := 41, 
      gcd := 3 )
  
  
  This means 3 = 7 * 123 - 13 * 66, 0 = -22 * 123 + 41 * 66.
  
    Example  
    gap> Gcdex( 0, -3 );
    rec( coeff1 := 0, coeff2 := -1, coeff3 := 1, coeff4 := 0, gcd := 3 )
    gap> Gcdex( 0, 0 );
    rec( coeff1 := 1, coeff2 := 0, coeff3 := 0, coeff4 := 1, gcd := 0 )
  
  
  GcdRepresentation  (56.7-3)  provides  similar  functionality over arbitrary
  Euclidean rings.
  
  14.3-6 LcmInt
  
  LcmInt( m, n )  function
  
  returns the least common multiple of the integers m and n.
  
  LcmInt is a method used by the general operation Lcm (56.7-6).
  
    Example  
    gap> LcmInt( 123, 66 );
    2706
  
  
  14.3-7 CoefficientsQadic
  
  CoefficientsQadic( i, q )  operation
  
  returns  the  q-adic  representation  of  the  integer  i  as  a  list  l of
  coefficients  satisfying  the  equality  i  =  ∑_{j = 0} q^j ⋅ l[j+1] for an
  integer q > 1.
  
    Example  
    gap> l:=CoefficientsQadic(462,3);
    [ 0, 1, 0, 2, 2, 1 ]
  
  
  14.3-8 CoefficientsMultiadic
  
  CoefficientsMultiadic( ints, int )  function
  
  returns the multiadic expansion of the integer int modulo the integers given
  in  ints  (in  ascending  order).  It  returns a list of coefficients in the
  reverse order to that in ints.
  
  14.3-9 ChineseRem
  
  ChineseRem( moduli, residues )  function
  
  ChineseRem  returns the combination of the residues modulo the moduli, i.e.,
  the  unique  integer  c  from  [0..Lcm(moduli)-1]  such that c = residues[i]
  modulo  moduli[i]  for  all  i,  if it exists. If no such combination exists
  ChineseRem signals an error.
  
  Such  a  combination does exist if and only if residues[i] = residues[k] mod
  Gcd( moduli[i], moduli[k] ) for every pair i, k. Note that this implies that
  such  a combination exists if the moduli are pairwise relatively prime. This
  is called the Chinese remainder theorem.
  
    Example  
    gap> ChineseRem( [ 2, 3, 5, 7 ], [ 1, 2, 3, 4 ] );
    53
    gap> ChineseRem( [ 6, 10, 14 ], [ 1, 3, 5 ] );
    103
  
  
    Example  
    gap> ChineseRem( [ 6, 10, 14 ], [ 1, 2, 3 ] );
    Error, the residues must be equal modulo 2 called from
    <function>( <arguments> ) called from read-eval-loop
    Entering break read-eval-print loop ...
    you can 'quit;' to quit to outer loop, or
    you can 'return;' to continue
    brk> gap> 
  
  
  14.3-10 PowerModInt
  
  PowerModInt( r, e, m )  function
  
  returns r^e mod m for integers r, e and m.
  
  Note  that  PowerModInt  can  reduce  intermediate  results  and  thus  will
  generally  be faster than using r^e mod m, which would compute r^e first and
  reduces the result afterwards.
  
  PowerModInt is a method for the general operation PowerMod (56.7-9).
  
  
  14.4 Prime Integers and Factorization
  
  14.4-1 Primes
  
  Primes  global variable
  
  Primes is a strictly sorted list of the 168 primes less than 1000.
  
  This  is  used  in  IsPrimeInt  (14.4-2) and FactorsInt (14.4-7) to cast out
  small primes quickly.
  
    Example  
    gap> Primes[1];
    2
    gap> Primes[100];
    541
  
  
  14.4-2 IsPrimeInt
  
  IsPrimeInt( n )  function
  IsProbablyPrimeInt( n )  function
  
  IsPrimeInt returns false if it can prove that the integer n is composite and
  true  otherwise.  By convention IsPrimeInt(0) = IsPrimeInt(1) = false and we
  define IsPrimeInt(-n) = IsPrimeInt(n).
  
  IsPrimeInt  will return true for every prime n. IsPrimeInt will return false
  for  all  composite n < 10^18 and for all composite n that have a factor p <
  1000.  So  for integers n < 10^18, IsPrimeInt is a proper primality test. It
  is conceivable that IsPrimeInt may return true for some composite n > 10^18,
  but no such n is currently known. So for integers n > 10^18, IsPrimeInt is a
  probable-primality  test.  IsPrimeInt will issue a warning when its argument
  is  probably  prime but not a proven prime. (The function IsProbablyPrimeInt
  will  do  a similar calculation but not issue a warning.) The warning can be
  switched  off  by  SetInfoLevel(  InfoPrimeInt, 0 );, the default level is 1
  (also see SetInfoLevel (7.4-3) ).
  
  If  composites  that fool IsPrimeInt do exist, they would be extremely rare,
  and  finding  one  by pure chance might be less likely than finding a bug in
  GAP.  We  would  appreciate  being informed about any example of a composite
  number n for which IsPrimeInt returns true.
  
  IsPrimeInt  is  a deterministic algorithm, i.e., the computations involve no
  random  numbers,  and  repeated  calls  will  always return the same result.
  IsPrimeInt  first does trial divisions by the primes less than 1000. Then it
  tests  that  n  is  a strong pseudoprime w.r.t. the base 2. Finally it tests
  whether n is a Lucas pseudoprime w.r.t. the smallest quadratic nonresidue of
  n.  A  better  description  can  be found in the comment in the library file
  primality.gi.
  
  The  time  taken  by  IsPrimeInt  is approximately proportional to the third
  power  of  the  number of digits of n. Testing numbers with several hundreds
  digits is quite feasible.
  
  IsPrimeInt is a method for the general operation IsPrime (56.5-8).
  
  Remark:  In  future  versions  of  GAP  we  hope to change the definition of
  IsPrimeInt  to  return  true  only  for  proven primes (currently, we lack a
  sufficiently   good   primality  proving  function).  In  applications,  use
  explicitly IsPrimeInt or IsProbablyPrimeInt with this change in mind.
  
    Example  
    gap> IsPrimeInt( 2^31 - 1 );
    true
    gap> IsPrimeInt( 10^42 + 1 );
    false
  
  
  14.4-3 PrimalityProof
  
  PrimalityProof( n )  function
  
  Construct  a  machine  verifiable  proof  of  the primality of (the probable
  prime)  n,  following  the  ideas  of [BLS75]. The proof consists of various
  Fermat  and  Lucas  pseudoprimality  tests, which taken as a whole prove the
  primality. The proof is represented as a list of witnesses of two kinds. The
  first   kind,  [  "F",  divisor,  base  ],  indicates  a  successful  Fermat
  pseudoprimality test, where n is a strong pseudoprime at base with order not
  divisible by (n-1)/divisor. The second kind, [ "L", divisor, discriminant, P
  ] indicates a successful Lucas pseudoprimality test, for a quadratic form of
  given discriminant and middle term P with an extra check at (n+1)/divisor.
  
  14.4-4 IsPrimePowerInt
  
  IsPrimePowerInt( n )  function
  
  IsPrimePowerInt  returns  true  if  the integer n is a prime power and false
  otherwise.
  
  An  integer  n  is  a  prime  power if there exists a prime p and a positive
  integer  i  such  that p^i = n. If n is negative the condition is that there
  must  exist a negative prime p and an odd positive integer i such that p^i =
  n. The integers 1 and -1 are not prime powers.
  
  Note   that   IsPrimePowerInt   uses   SmallestRootInt   (14.2-10)   and   a
  probable-primality test (see IsPrimeInt (14.4-2)).
  
    Example  
    gap> IsPrimePowerInt( 31^5 );
    true
    gap> IsPrimePowerInt( 2^31-1 );  # 2^31-1 is actually a prime
    true
    gap> IsPrimePowerInt( 2^63-1 );
    false
    gap> Filtered( [-10..10], IsPrimePowerInt );
    [ -8, -7, -5, -3, -2, 2, 3, 4, 5, 7, 8, 9 ]
  
  
  14.4-5 NextPrimeInt
  
  NextPrimeInt( n )  function
  
  NextPrimeInt  returns  the  smallest prime which is strictly larger than the
  integer n.
  
  Note  that  NextPrimeInt  uses  a  probable-primality  test  (see IsPrimeInt
  (14.4-2)).
  
    Example  
    gap> NextPrimeInt( 541 ); NextPrimeInt( -1 );
    547
    2
  
  
  14.4-6 PrevPrimeInt
  
  PrevPrimeInt( n )  function
  
  PrevPrimeInt  returns  the  largest prime which is strictly smaller than the
  integer n.
  
  Note  that  PrevPrimeInt  uses  a  probable-primality  test  (see IsPrimeInt
  (14.4-2)).
  
    Example  
    gap> PrevPrimeInt( 541 ); PrevPrimeInt( 1 );
    523
    -2
  
  
  14.4-7 FactorsInt
  
  FactorsInt( n )  function
  FactorsInt( n: RhoTrials := trials )  function
  
  FactorsInt returns a list of factors of a given integer n such that Product(
  FactorsInt(  n  )  ) = n. If |n| ≤ 1 the list [n] is returned. Otherwise the
  result  contains probable primes, sorted by absolute value. The entries will
  all be positive except for the first one in case of a negative n.
  
  See  PrimeDivisors  (14.4-8) for a function that returns a set of (probable)
  primes dividing n.
  
  Note   that   FactorsInt  uses  a  probable-primality  test  (see IsPrimeInt
  (14.4-2)).  Thus  FactorsInt  might  return  a list which contains composite
  integers.  In such a case you will get a warning about the use of a probable
  prime. You can switch off these warnings by SetInfoLevel( InfoPrimeInt, 0 );
  (also see SetInfoLevel (7.4-3)).
  
  The  time  taken  by  FactorsInt is approximately proportional to the square
  root  of  the  second  largest prime factor of n, which is the last one that
  FactorsInt has to find, since the largest factor is simply what remains when
  all others have been removed. Thus the time is roughly bounded by the fourth
  root  of  n. FactorsInt is guaranteed to find all factors less than 10^6 and
  will  find  most  factors  less  than  10^10. If n contains multiple factors
  larger than that FactorsInt may not be able to factor n and will then signal
  an error.
  
  FactorsInt is used in a method for the general operation Factors (56.5-9).
  
  In  the  second  form, FactorsInt calls FactorsRho with a limit of trials on
  the  number  of trials it performs. The default is 8192. Note that Pollard's
  Rho  is  the  fastest  method  for  finding  prime factors with roughly 5-10
  decimal  digits,  but  becomes more and more inferior to other factorization
  techniques  like  e.g. the Elliptic Curves Method (ECM) the bigger the prime
  factors are. Therefore instead of performing a huge number of Rho trials, it
  is  usually more advisable to install the FactInt package and then simply to
  use  the  operation  Factors  (56.5-9). The factorization of the 8-th Fermat
  number by Pollard's Rho below takes already a while.
  
    Example  
    gap> FactorsInt( -Factorial(6) );
    [ -2, 2, 2, 2, 3, 3, 5 ]
    gap> Set( FactorsInt( Factorial(13)/11 ) );
    [ 2, 3, 5, 7, 13 ]
    gap> FactorsInt( 2^63 - 1 );
    [ 7, 7, 73, 127, 337, 92737, 649657 ]
    gap> FactorsInt( 10^42 + 1 );
    [ 29, 101, 281, 9901, 226549, 121499449, 4458192223320340849 ]
    gap> FactorsInt(2^256+1:RhoTrials:=100000000);
    [ 1238926361552897, 
      93461639715357977769163558199606896584051237541638188580280321 ]
  
  
  14.4-8 PrimeDivisors
  
  PrimeDivisors( n )  attribute
  
  PrimeDivisors  returns  for  a  non-zero  integer  n  a  set of its positive
  (probable)  primes  divisors.  In  rare  cases  the  result  could contain a
  composite    number    which    passed    certain   primality   tests,   see
  IsProbablyPrimeInt (14.4-2) and FactorsInt (14.4-7) for more details.
  
    Example  
    gap> PrimeDivisors(-12);
    [ 2, 3 ]
    gap> PrimeDivisors(1);
    [  ]
  
  
  14.4-9 PartialFactorization
  
  PartialFactorization( n[, effort] )  operation
  
  PartialFactorization  returns  a  partial factorization of the integer n. No
  assertions  are  made  about  the  primality of the factors, except of those
  mentioned below.
  
  The argument effort, if given, specifies how intensively the function should
  try to determine factors of n. The default is effort = 5.
  
      If  effort = 0,  trial  division  by  the  primes  below  100 is done.
        Returned factors below 10^4 are guaranteed to be prime.
  
      If  effort = 1,  trial  division  by  the  primes  below 1000 is done.
        Returned factors below 10^6 are guaranteed to be prime.
  
      If effort = 2, additionally trial division by the numbers in the lists
        Primes2  and ProbablePrimes2 is done, and perfect powers are detected.
        Returned factors below 10^6 are guaranteed to be prime.
  
      If  effort = 3, additionally FactorsRho (Pollard's Rho) with RhoTrials
        = 256 is used.
  
      If effort = 4, as above, but RhoTrials = 2048.
  
      If  effort = 5, as above, but RhoTrials = 8192. Returned factors below
        10^12 are guaranteed to be prime, and all prime factors below 10^6 are
        guaranteed to be found.
  
      If  effort = 6  and  the package FactInt is loaded, in addition to the
        above quite a number of special cases are handled.
  
      If  effort = 7 and the package FactInt is loaded, the only thing which
        is    not    attempted   to   obtain   a   full   factorization   into
        Baillie-Pomerance-Selfridge-Wagstaff  pseudoprimes  is the application
        of the MPQS to a remaining composite with more than 50 decimal digits.
  
  Increasing  the  value  of  the argument effort by one usually results in an
  increase of the runtime requirements by a factor of (very roughly!) 3 to 10.
  (Also see CheapFactorsInt (CheapFactorsInt???)).
  
    Example  
    gap> List([0..5],i->PartialFactorization(97^35-1,i)); 
    [ [ 2, 2, 2, 2, 2, 3, 11, 31, 43, 
          2446338959059521520901826365168917110105972824229555319002965029 ], 
      [ 2, 2, 2, 2, 2, 3, 11, 31, 43, 967, 
          2529823122088440042297648774735177983563570655873376751812787 ],
      [ 2, 2, 2, 2, 2, 3, 11, 31, 43, 967, 
          2529823122088440042297648774735177983563570655873376751812787 ],
      [ 2, 2, 2, 2, 2, 3, 11, 31, 43, 967, 39761, 262321, 
          242549173950325921859769421435653153445616962914227 ], 
      [ 2, 2, 2, 2, 2, 3, 11, 31, 43, 967, 39761, 262321, 687121, 
          352993394104278463123335513593170858474150787 ], 
      [ 2, 2, 2, 2, 2, 3, 11, 31, 43, 967, 39761, 262321, 687121, 
          20241187, 504769301, 34549173843451574629911361501 ] ]
  
  
  14.4-10 PrintFactorsInt
  
  PrintFactorsInt( n )  function
  
  prints  the prime factorization of the integer n in human-readable form. See
  also StringPP (27.7-9).
  
    Example  
    gap> PrintFactorsInt( Factorial( 7 ) ); Print( "\n" );
    2^4*3^2*5*7
  
  
  14.4-11 PrimePowersInt
  
  PrimePowersInt( n )  function
  
  returns  the prime factorization of the integer n as a list [ p_1, e_1, ...,
  p_k, e_k ] with n = p_1^{e_1} ⋅ p_2^{e_2} ⋅ ... ⋅ p_k^{e_k}.
  
  For  negative  integers, the absolute value is taken. Zero is not allowed as
  input.
  
    Example  
    gap> PrimePowersInt( Factorial( 7 ) );
    [ 2, 4, 3, 2, 5, 1, 7, 1 ]
    gap> PrimePowersInt( 1 );
    [  ]
  
  
  14.4-12 DivisorsInt
  
  DivisorsInt( n )  function
  
  DivisorsInt  returns  a  list  of all divisors of the integer n. The list is
  sorted,  so  that  it  starts  with  1  and  ends  with  n.  We  define that
  DivisorsInt( -n ) = DivisorsInt( n ).
  
  Since  the  set of divisors of 0 is infinite calling DivisorsInt( 0 ) causes
  an error.
  
  DivisorsInt  may call FactorsInt (14.4-7) to obtain the prime factors. Sigma
  (15.5-1)  and  Tau  (15.5-2)  compute  the  sum  and  the number of positive
  divisors, respectively.
  
    Example  
    gap> DivisorsInt( 1 ); DivisorsInt( 20 ); DivisorsInt( 541 );
    [ 1 ]
    [ 1, 2, 4, 5, 10, 20 ]
    [ 1, 541 ]
  
  
  
  14.5 Residue Class Rings
  
  ZmodnZ  (14.5-2)  returns  a  residue  class ring of Integers (14) modulo an
  ideal.  These  residue  class rings are rings, thus all operations for rings
  (see Chapter 56) apply. See also Chapters 59 and 15.
  
  14.5-1 \mod
  
  \mod( r/s, n )  operation
  
  If  r, s and n are integers, r / s as a reduced fraction is p/q, where q and
  n  are  coprime,  then r / s mod n is defined to be the product of p and the
  inverse of q modulo n. See Section 4.14 for more details and definitions.
  
  With the above definition, 4 / 6 mod 32 equals 2 / 3 mod 32 and hence exists
  (and is equal to 22), despite the fact that 6 has no inverse modulo 32.
  
  14.5-2 ZmodnZ
  
  ZmodnZ( n )  function
  ZmodpZ( p )  function
  ZmodpZNC( p )  function
  
  ZmodnZ returns a ring R isomorphic to the residue class ring of the integers
  modulo  the  ideal  generated by n. The element corresponding to the residue
  class  of  the integer i in this ring can be obtained by i * One( R ), and a
  representative  of  the residue class corresponding to the element x ∈ R can
  be computed by Int( x ).
  
  ZmodnZ( n ) is equal to Integers mod n.
  
  ZmodpZ  does the same if the argument p is a prime integer, additionally the
  result is a field. ZmodpZNC omits the check whether p is a prime.
  
  Each  ring  returned  by  these  functions  contains the whole family of its
  elements  if  n  is  not  a prime, and is embedded into the family of finite
  field elements of characteristic n if n is a prime.
  
  14.5-3 ZmodnZObj
  
  ZmodnZObj( Fam, r )  operation
  ZmodnZObj( r, n )  operation
  
  If  the  first argument is a residue class family Fam then ZmodnZObj returns
  the element in Fam whose coset is represented by the integer r.
  
  If  the  two  arguments  are  an  integer  r  and  a positive integer n then
  ZmodnZObj  returns  the  element  in ZmodnZ( n ) (see ZmodnZ (14.5-2)) whose
  coset is represented by the integer r.
  
    Example  
    gap> r:= ZmodnZ(15);
    (Integers mod 15)
    gap> fam:=ElementsFamily(FamilyObj(r));;
    gap> a:= ZmodnZObj(fam,9);
    ZmodnZObj( 9, 15 )
    gap> a+a;
    ZmodnZObj( 3, 15 )
    gap> Int(a+a);
    3
  
  
  14.5-4 IsZmodnZObj
  
  IsZmodnZObj( obj )  Category
  IsZmodnZObjNonprime( obj )  Category
  IsZmodpZObj( obj )  Category
  IsZmodpZObjSmall( obj )  Category
  IsZmodpZObjLarge( obj )  Category
  
  The elements in the rings Z / n Z are in the category IsZmodnZObj. If n is a
  prime  then  the elements are of course also in the category IsFFE (59.1-1),
  otherwise they are in IsZmodnZObjNonprime. IsZmodpZObj is an abbreviation of
  IsZmodnZObj   and   IsFFE.   This   category   is   the  disjoint  union  of
  IsZmodpZObjSmall  and  IsZmodpZObjLarge,  the former containing all elements
  with n at most MAXSIZE_GF_INTERNAL.
  
  The reasons to distinguish the prime case from the nonprime case are
  
      that  objects  in  IsZmodnZObjNonprime have an external representation
        (namely the residue in the range [ 0, 1, ..., n-1 ]),
  
      that  the  comparison  of elements can be defined as comparison of the
        residues, and
  
      that  the  elements  lie in a family of type IsZmodnZObjNonprimeFamily
        (note that for prime n, the family must be an IsFFEFamily).
  
  The reasons to distinguish the small and the large case are that for small n
  the  elements  must be compatible with the internal representation of finite
  field  elements,  whereas  we are free to define comparison as comparison of
  residues for large n.
  
  Note  that we cannot claim that every finite field element of degree 1 is in
  IsZmodnZObj,  since finite field elements in internal representation may not
  know that they lie in the prime field.
  
  
  14.6 Check Digits
  
  14.6-1 CheckDigitISBN
  
  CheckDigitISBN( n )  function
  CheckDigitISBN13( n )  function
  CheckDigitPostalMoneyOrder( n )  function
  CheckDigitUPC( n )  function
  
  These  functions  can  be  used  to compute, or check, check digits for some
  everyday items. In each case what is submitted as input is either the number
  with  check digit (in which case the function returns true or false), or the
  number  without  check digit (in which case the function returns the missing
  check digit). The number can be specified as integer, as string (for example
  in case of leading zeros) or as a sequence of arguments, each representing a
  single  digit.  The check digits tested are the 10-digit ISBN (International
  Standard Book Number) using CheckDigitISBN (since arithmetic is module 11, a
  digit  11  is  represented  by  an  X);  the  newer  13-digit  ISBN-13 using
  CheckDigitISBN13;  the  numbers  of  11-digit  US  postal money orders using
  CheckDigitPostalMoneyOrder; and the 12-digit UPC bar code found on groceries
  using CheckDigitUPC.
  
    Example  
    gap> CheckDigitISBN("052166103");
    Check Digit is 'X'
    'X'
    gap> CheckDigitISBN("052166103X");
    Checksum test satisfied
    true
    gap> CheckDigitISBN(0,5,2,1,6,6,1,0,3,1);
    Checksum test failed
    false
    gap> CheckDigitISBN(0,5,2,1,6,6,1,0,3,'X'); # note single quotes!
    Checksum test satisfied
    true
    gap> CheckDigitISBN13("9781420094527");
    Checksum test satisfied
    true
    gap> CheckDigitUPC("07164183001");
    Check Digit is 1
    1
    gap> CheckDigitPostalMoneyOrder(16786457155);
    Checksum test satisfied
    true
  
  
  14.6-2 CheckDigitTestFunction
  
  CheckDigitTestFunction( l, m, f )  function
  
  This  function  creates  check  digit  test functions such as CheckDigitISBN
  (14.6-1)  for  check  digit schemes that use the inner products with a fixed
  vector  modulo  a  number.  The  scheme creates will use strings of l digits
  (including  the  check  digits),  the  check consists of taking the standard
  product of the vector of digits with the fixed vector f modulo m; the result
  needs  to  be  0.  The function returns a function that then can be used for
  testing or determining check digits.
  
    Example  
    gap> isbntest:=CheckDigitTestFunction(10,11,[1,2,3,4,5,6,7,8,9,-1]); 
    function( arg... ) ... end
    gap> isbntest("038794680");
    Check Digit is 2
    2
  
  
  
  14.7 Random Sources
  
  GAP  provides  Random (30.7-1) methods for many collections of objects. On a
  lower  level  these methods use random sources which provide random integers
  and random choices from lists.
  
  See  IsRandomSource  (14.7-1) for the user interface for random sources, and
  Section 14.7-6 for information about developing new kinds of random sources.
  
  14.7-1 IsRandomSource
  
  IsRandomSource( obj )  Category
  
  This  is the category of random source objects. The user interface for these
  objects consists of the following functions.
  
  RandomSource (14.7-5) creates a new random source rs, say.
  
  Random( rs, list ) yields a random element of the list list, and Random( rs,
  low,  high  )  yields a random integer between low and high (inclusive), see
  Random (14.7-2).
  
  If rs supports resetting (see State (14.7-3)) then State( rs ) yields a copy
  state,  say,  of the current state of rs such that Reset( rs, state ) resets
  rs to the given state.
  
  One  idea behind providing several independent (pseudo) random sources is to
  make  algorithms  which  use some sort of random choices deterministic. They
  can  use  their  own  new  random source created with a fixed seed and so do
  exactly the same in different calls.
  
  Random source objects lie in the family RandomSourcesFamily.
  
  14.7-2 Random
  
  Random( rs, list )  operation
  Random( rs, coll )  operation
  Random( rs, low, high )  operation
  
  This  operation  returns a random element from the dense, nonempty list list
  or  the  nonempty collection coll, or an integer in the range from the given
  (possibly large) integers low to high, respectively.
  
  The  choice should only depend on the random source rs and have no effect on
  other random sources.
  
  It  is not defined what happens if list or coll is empty, list is not dense,
  or low is larger than high.
  
    Example  
    gap> mysource := RandomSource(IsMersenneTwister, 42);;
    gap> Random(mysource, 1, 10^60);
    999331861769949319194941485000557997842686717712198687315183
  
  
  
  14.7-3 State and Reset for Random Sources
  
  State( rs )  operation
  Reset( rs[, seed] )  operation
  
  These  are  the  basic  operations  for  random  sources (see IsRandomSource
  (14.7-1)).
  
  State  returns  a  data  structure  which admits recovering the state of the
  random  source such that a sequence of random calls using this random source
  can  be  reproduced.  If a random source cannot be reset (say, it uses truly
  random physical data) then State returns fail.
  
  Reset(  rs, seed ) resets the random source rs to a state described by seed,
  if  the random source can be reset; otherwise it does nothing. Here seed can
  be  an  output of State and then rs gets reset to that state. For historical
  reasons, random sources accept integer values as seed. We recommend that new
  code should not rely on this; always use the output of a prior call to State
  as seed, or omit it. Without the seed argument a fixed default seed is used.
  Reset returns the state of rs before the call.
  
  Most  methods  for  Random  (30.7-1)  in  the GAP library that do not take a
  random  source  as argument use the GlobalMersenneTwister (14.7-4) as random
  source. It can be reset into a known state as in the following example.
  
    Example  
    gap> seed := Reset(GlobalMersenneTwister);;
    gap> seed = State(GlobalMersenneTwister);
    true
    gap> List([1..10],i->Random(Integers));
    [ -3, 2, -1, -2, -1, -1, 1, -4, 1, 0 ]
    gap> List([1..10],i->Random(Integers));
    [ -1, -1, -1, 1, -1, 1, -2, -1, -2, 0 ]
    gap> Reset(GlobalMersenneTwister, seed);;
    gap> List([1..10],i->Random(Integers));
    [ -3, 2, -1, -2, -1, -1, 1, -4, 1, 0 ]
  
  
  
  14.7-4 Kinds of Random Sources
  
  IsMersenneTwister( rs )  Category
  IsGAPRandomSource( rs )  Category
  IsGlobalRandomSource( rs )  Category
  GlobalMersenneTwister  global variable
  GlobalRandomSource  global variable
  
  Currently,   the  GAP  library  provides  three  types  of  random  sources,
  distinguished by the three listed categories.
  
  IsMersenneTwister are random sources which use a fast random generator of 32
  bit  numbers,  called the Mersenne twister. The pseudo random sequence has a
  period of 2^19937-1 and the numbers have a 623-dimensional equidistribution.
  For  more  details  and  the origin of the code used in the GAP kernel, see:
  http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html.
  
  Use  the  Mersenne  twister  if  possible, in particular for generating many
  large random integers.
  
  There  is also a predefined global random source GlobalMersenneTwister which
  is  used  as  the  default random source by those library methods for Random
  (30.7-1) that do not take a random source as an argument.
  
  IsGAPRandomSource  uses  the  same number generator as IsGlobalRandomSource,
  but  you  can  create  several  of these random sources which generate their
  random numbers independently of all other random sources.
  
  IsGlobalRandomSource  gives  access to the classical global random generator
  which  was  used by GAP in former releases. You do not need to construct new
  random  sources  of  this  kind  which  would  all  use the same global data
  structure. Just use the existing random source GlobalRandomSource. This uses
  the  additive  random  number  generator  described  in [Knu98] (Algorithm A
  in 3.2.2 with lag 30).
  
  Other kinds of random sources are implemented by GAP packages.
  
  14.7-5 RandomSource
  
  RandomSource( cat[, seed] )  operation
  
  This  operation is used to create new random sources. The first argument cat
  is the category describing the type of the random generator, for example one
  of the categories listed in Section 14.7-4.
  
  An optional seed can be given to specify the initial state. For details, see
  Section 14.7-3.
  
    Example  
    gap> rs1 := RandomSource(IsMersenneTwister);
    <RandomSource in IsMersenneTwister>
    gap> l1 := List([1..10000], i-> Random(rs1, [1..6]));;
    gap> state1 := State(rs1);;
    gap> rs2 := RandomSource(IsMersenneTwister);;
    gap> l2 := List([1..10000], i-> Random(rs2, [1..6]));;
    gap> l1 = l2;
    true
    gap> l3 := List([1..10000], i-> Random(rs1, [1..6]));;
    gap> l1 = l3;
    false
    gap> rs3 := RandomSource(IsMersenneTwister, state1);;
    gap> l4 := List([1..10000], i-> Random(rs3, [1..6]));;
    gap> l3 = l4;
    true
    gap> n := Random(rs1, 1, 2^220);
    1077726777923092117987668044202944212469136000816111066409337432400
  
  
  
  14.7-6 Implementing new kinds of random sources
  
  If  one  wants to implement a new kind of random sources then the first step
  is  the  declaration  of  a new category C, say, that implies IsRandomSource
  (14.7-1), analogous to the categories listed in Section 14.7-4, as follows.
  
  DeclareCategory( "C", IsRandomSource );.
  
  Then the following method installations are needed.
  
  InstallMethod( Init, [ C, IsObject ], function( prers, seed ) ... end );
  
  Here  prers  is  an empty component object (which has already the filter C),
  and  seed  is an integer or a state value as returned by State (14.7-3) that
  describes  the  initial state of the random source. The function should fill
  in  the  actual data and then return the (now initialized) object prers. The
  default  used  for  seed  is  the integer 1. A given state value need not be
  copied by the function.
  
  InstallMethod(  Random,  [  C, IsInt, IsInt ], function( rs, low, high ) ...
  end );
  
  Here  rs  is  an already initialized random source object in the category C,
  and  the function returns an integer between low and high (inclusive). It is
  not defined what happens when low is larger than high.
  
  InstallMethod( State, [ C ], function( rs ) ... end );
  
  If  rs  supports  resetting  then  the  function  must return an object that
  describes  the current state of rs. This object must be an independent copy,
  that  is, calling Random (14.7-2) for rs must not change the object that was
  returned   by   State  (14.7-3);  otherwise  ReturnFail  (5.4-3)  should  be
  installed.
  
  InstallMethod( Reset, [ C, IsObject ], function( rs, seed ) ... end );
  
  If  rs  supports  resetting  then  the  function must reinitialize rs to the
  integer  or  State  (14.7-3)  value  seed and must return the State (14.7-3)
  value  of  rs  before  these  changes;  if  resetting  is not supported then
  ReturnNothing  (5.4-4)  should  be  installed.  Reset  need not copy a given
  state.  Note  that  the generic unary Reset (14.7-3) method uses the default
  seed 1.
  
  Examples  of  implementations  as  described  here  are  given by the random
  sources    with    defining    filter    IsMersenneTwister    (14.7-4)    or
  IsRealRandomSource.  (For  the latter, see RandomSource (RandomSource???) in
  the GAP package IO.)
  
  
  14.8 Bitfields
  
  Bitfields  are a low-level feature intended to support efficient subdivision
  of  immediate  integers  into bitfields of various widths. This is typically
  useful   in   implementing   space-efficient   and/or  cache-efficient  data
  structures.  This  feature  should be used with care because (inter alia) it
  has different limitations on 32-bit and 64-bit architectures.
  
  14.8-1 MakeBitfields
  
  MakeBitfields( width.... )  function
  
  This  function  sets  up  the  machinery for a set of bitfields of the given
  widths. All bitfield values are treated as unsigned. The total of the widths
  must  not  exceed  60  bits  on  64-bit  architecture or 28 bits on a 32-bit
  architecture.  For performance reasons some checks that one might wish to do
  are  ommitted.  In particular, the builder and setter functions do not check
  if  the  value[s]  passed  to  them are negative or too large (unless GAP is
  specially  compiled for debugging). Behaviour when such arguments are passed
  is  undefined. You can tell which type of architecture you are running on by
  acccessing  GAPInfo.BytesPerVariable  which is 8 on 64-bits and 4 on 32. The
  return value when n widths are given is a record whose fields are
  
  widths
        a copy of the arguments, for convenience,
  
  getters
        a  list  of  n functions of one argument each of which extracts one of
        the fields from an immediate integer
  
  setters
        a  list of n functions each taking two arguments: a packed value and a
        new  value for one of its fields and returning a new packed value. The
        ith  function returned the new packed value in which the ith field has
        been  replaced  by  the  new value. Note that this does NOT modify the
        original packed value.
  
  Two additional fields may be present if any of the field widths is one. Each
  is  a  list and only has entried bound in the positions corresponding to the
  width 1 fields.
  
  booleanGetters
        if  the ith position of this list is set, it contains a function which
        extracts the ith field (which will have width one) and returns true if
        it contains 1 and false if it contains 0
  
  booleanSetters
        if the ith position of this list is set, it contains a function of two
        arguments. The first argument is a packed value, the second is true or
        false.  It returns a new packed value in which the ith field is set to
        1 if the second argument was true and 0 if it was false. Behaviour for
        any other value is undefined.
  
  14.8-2 BuildBitfields
  
  BuildBitfields( widths, vals... )  function
  
  This  function  takes  one or more argument. Its first argument is a list of
  field  widths,  as  found  in  the  widths  entry  of  a  record returned by
  MakeBitfields. The remaining arguments are unsigned integer values, equal in
  number  to  the  entries  of  the  list  of field widths. It returns a small
  integer  in  which  those  entries  are  packed  into bitfields of the given
  widths.   The   first   entry   occupies   the   least   significant   bits.
  DeclareGlobalFunction("BuildBitfields");
  
    Example  
    gap> bf := MakeBitfields(1,2,3);
    rec( booleanGetters := [ function( data ) ... end ], 
      booleanSetters := [ function( data, val ) ... end ], 
      getters := [ function( data ) ... end, function( data ) ... end, 
          function( data ) ... end ], 
      setters := [ function( data, val ) ... end, function( data, val ) ... end, 
          function( data, val ) ... end ], widths := [ 1, 2, 3 ] )
    gap> x := BuildBitfields(bf.widths,0,3,5);
    46
    gap> bf.getters[3](x);
    5
    gap> y := bf.setters[1](x,1);
    47  
    gap> x;
    46
    gap> bf.booleanGetters[1](x);
    false
    gap> bf.booleanGetters[1](y);
    true