finfield.h

/****************************************************************************
**
**  This file is part of GAP, a system for computational discrete algebra.
**
**  Copyright of GAP belongs to its developers, whose names are too numerous
**  to list here. Please refer to the COPYRIGHT file for details.
**
**  SPDX-License-Identifier: GPL-2.0-or-later
**
**  This file declares the  functions  to compute  with elements  from  small
**  finite fields.
**
**  Finite fields  are an  important   domain in computational   group theory
**  because the classical matrix groups are defined over those finite fields.
**  The GAP kernel supports elements of finite fields up to some fixed size
**  limit stored in MAXSIZE_GF_INTERNAL. To change this limit for 32 resp.
**  64 bit systems, edit `etc/ffgen.c`. Support for fields larger than this
**  is implemented by the GAP library.
**
**  Elements in small finite fields are  represented  as  immediate  objects.
**
**      +----------------+-------------+---+
**      |     <value>    |   <field>   |010|
**      +----------------+-------------+---+
**
**  The least significant 3 bits of such an immediate object are always  010,
**  flagging the object as an object of a small finite field.
**
**  The next group of FIELD_BITS_FFE bits represent the small finite field
**  where the element lies. They are simply an index into a global table of
**  small finite fields, which is constructed at build time.
**
**  The most significant VAL_BITS_FFE bits represent the value of the element.
**
**  If the  value is 0,  then the element is the  zero from the finite field.
**  Otherwise the integer is the logarithm of this  element with respect to a
**  fixed generator of the multiplicative group of the finite field plus one.
**  In the following descriptions we denote this generator always with $z$, it
**  is an element of order $o-1$, where $o$ is the order of the finite field.
**  Thus 1 corresponds to $z^{1-1} = z^0 = 1$, i.e., the  one from the field.
**  Likewise 2 corresponds to $z^{2-1} = z^1 = z$, i.e., the root itself.
**
**  This representation  makes multiplication very easy,  we only have to add
**  the values and subtract 1 , because  $z^{a-1} * z^{b-1} = z^{(a+b-1)-1}$.
**  Addition is reduced to * by the formula $z^a +  z^b = z^b * (z^{a-b}+1)$.
**  This makes it necessary to know the successor $z^a + 1$ of every value.
**
**  The  finite field  bag contains  the  successor for  every nonzero value,
**  i.e., 'SUCC_FF(<ff>)[<a>]' is  the successor of  the element <a>, i.e, it
**  is the  logarithm  of $z^{a-1} +   1$.  This list  is  usually called the
**  Zech-Logarithm  table.  The zeroth  entry in the  finite field bag is the
**  order of the finite field minus one.
*/

#ifndef GAP_FINFIELD_H
#define GAP_FINFIELD_H

#include "common.h"
#include "ffdata.h"
#include "objects.h"

#ifdef HPCGAP
#include "hpc/aobjects.h"
#endif


/****************************************************************************
**
*T  FF  . . . . . . . . . . . . . . . . . . . . . type of small finite fields
**
**  'FF' is the type used to represent small finite fields.
**
**  Small finite fields are represented by an  index  into  a  global  table.
**
**  Depending on the configuration it may be UInt2 or UInt4. The definition
**  is in `ffdata.h` and is calculated by `etc/ffgen.c`
*/
GAP_STATIC_ASSERT(NUM_SHORT_FINITE_FIELDS <= (1<<(8*sizeof(FF))),
                  "NUM_SHORT_FINITE_FIELDS too large for type FF");

GAP_STATIC_ASSERT(FIELD_BITS_FFE + VAL_BITS_FFE + 3 <= 8*sizeof(Obj),
                  "not enough bits in type Obj to store internal FFEs");


/****************************************************************************
**
*F  CHAR_FF(<ff>) . . . . . . . . . . .  characteristic of small finite field
**
**  'CHAR_FF' returns the characteristic of the small finite field <ff>.
**
**  Note that  'CHAR_FF' is a macro,  so do not call  it  with arguments that
**  have side effects.
*/
#define CHAR_FF(ff)             (CharFF[ff])


/****************************************************************************
**
*F  DEGR_FF(<ff>) . . . . . . . . . . . . . . .  degree of small finite field
**
**  'DEGR_FF' returns the degree of the small finite field <ff>.
**
**  Note that 'DEGR_FF' is  a macro, so do   not call it with  arguments that
**  have side effects.
*/
#define DEGR_FF(ff)             (DegrFF[ff])


/****************************************************************************
**
*F  SIZE_FF(<ff>) . . . . . . . . . . . . . . . .  size of small finite field
**
**  'SIZE_FF' returns the size of the small finite field <ff>.
**
**  Note that 'SIZE_FF' is a macro, so do not call  it  with  arguments  that
**  have side effects.
*/
#define SIZE_FF(ff)             (SizeFF[ff])


/****************************************************************************
**
*F  SUCC_FF(<ff>) . . . . . . . . . . . successor table of small finite field
**
**  'SUCC_FF' returns a pointer to the successor table of  the  small  finite
**  field <ff>.
**
**  Note that 'SUCC_FF' is a macro, so do not call  it  with  arguments  that
**  side effects.
*/
#ifdef HPCGAP
#define SUCC_FF(ff)             ((const FFV*)(1+CONST_ADDR_OBJ( ATOMIC_ELM_PLIST( SuccFF, ff ) )))
#else
#define SUCC_FF(ff)             ((const FFV*)(1+CONST_ADDR_OBJ( ELM_PLIST( SuccFF, ff ) )))
#endif

extern  Obj             SuccFF;


/****************************************************************************
**
*T  FFV . . . . . . . . type of the values of elements of small finite fields
**
**  'FFV'  is the  type used  to represent  the values  of elements  of small
**  finite fields.
**
**  Values of  elements  of  small  finite  fields  are  represented  by  the
**  logarithm of the element with respect to the root plus one.
**
**  Depending on the configuration, this type may be a UInt2 or UInt4.
**  This type is actually defined in `ffdata.h` by `etc/ffgen.c`
*/
GAP_STATIC_ASSERT(MAXSIZE_GF_INTERNAL <= (1<<(8*sizeof(FFV))),
                  "MAXSIZE_GF_INTERNAL too large for type FFV");

GAP_STATIC_ASSERT(sizeof(UInt) >= 2 * sizeof(FFV),
                  "Overflow possibility in POW_FFV");

/****************************************************************************
**
*F  PROD_FFV(<a>,<b>,<f>) . . . . . . . . . . . product of finite field value
**
**  'PROD_FFV' returns the product of the two finite field values <a> and <b>
**  from the finite field pointed to by the pointer <f>.
**
**  Note that 'PROD_FFV' may only be used if the  operands are represented in
**  the  same finite field.  If you  want to multiply  two elements where one
**  lies in a subfield of the other use 'ProdFFEFFE'.
**
**  If one of the values is 0 the product is 0.
**  If $a+b <= o$ we have $a * b ~ z^{a-1} * z^{b-1} = z^{(a+b-1)-1} ~ a+b-1$
**  otherwise   we   have $a * b ~ z^{(a+b-2)-(o-1)} = z^{(a+b-o)-1} ~ a+b-o$
*/
EXPORT_INLINE FFV PROD_FFV(FFV a, FFV b, const FFV * f)
{
    GAP_ASSERT(a <= f[0]);
    GAP_ASSERT(b <= f[0]);
    if (a == 0 || b == 0)
        return 0;
    FFV q1 = f[0];
    FFV a1 = a - 1;
    FFV b1 = q1 - b;
    if (a1 <= b1)
        return a1 + b;
    else
        return a1 - b1;
}


/****************************************************************************
**
*F  SUM_FFV(<a>,<b>,<f>)  . . . . . . . . . . . .  sum of finite field values
**
**  'SUM_FFV' returns the sum of the two finite field values <a> and <b> from
**  the finite field pointed to by the pointer <f>.
**
**  Note that 'SUM_FFV' may only  be used if  the operands are represented in
**  the same finite field.  If you want to add two elements where one lies in
**  a subfield of the other use 'SumFFEFFE'.
**
**  If either operand is 0, the sum is just the other operand.
**  If $a <= b$ we have
**  $a + b ~ z^{a-1}+z^{b-1} = z^{a-1} * (z^{(b-1)-(a-1)}+1) ~ a * f[b-a+1]$,
**  otherwise we have
**  $a + b ~ z^{b-1}+z^{a-1} = z^{b-1} * (z^{(a-1)-(b-1)}+1) ~ b * f[a-b+1]$.
*/
EXPORT_INLINE FFV SUM_FFV(FFV a, FFV b, const FFV * f)
{
    GAP_ASSERT(a <= f[0]);
    GAP_ASSERT(b <= f[0]);
    if (a == 0)
        return b;
    if (b == 0)
        return a;
    if (b > a) {
        FFV t = a;
        a = b;
        b = t;
    }
    return PROD_FFV(b, f[a - b + 1], f);
}


/****************************************************************************
**
*F  NEG_FFV(<a>,<f>)  . . . . . . . . . . . .  negative of finite field value
**
**  'NEG_FFV' returns  the negative of the   finite field value  <a> from the
**  finite field pointed to by the pointer <f>.
**
**  If the characteristic is 2, every element is its  own  additive  inverse.
**  Otherwise note that $z^{o-1} = 1 = -1^2$ so $z^{(o-1)/2} = 1^{1/2} = -1$.
**  If $a <= (o-1)/2$ we have
**  $-a ~ -1 * z^{a-1} = z^{(o-1)/2} * z^{a-1} = z^{a+(o-1)/2-1} ~ a+(o-1)/2$
**  otherwise we have
**  $-a ~ -1 * z^{a-1} = z^{a+(o-1)/2-1} = z^{a+(o-1)/2-1-(o-1)} ~ a-(o-1)/2$
*/
EXPORT_INLINE FFV NEG_FFV(FFV a, const FFV * f)
{
    GAP_ASSERT(a <= f[0]);
    UInt q1 = f[0];
    if (a == 0)
        return 0;
    if (q1 % 2)
        return a;
    if (a <= q1 / 2)
        return a + q1 / 2;
    else
        return a - q1 / 2;
}


/****************************************************************************
**
*F  QUO_FFV(<a>,<b>,<f>)  . . . . . . . . . . quotient of finite field values
**
**  'QUO_FFV' returns the quotient of the two finite field values <a> and <b>
**  from the finite field pointed to by the pointer <f>.
**
**  Note that 'QUO_FFV' may  only be used  if the operands are represented in
**  the same finite field.  If you want to divide two elements where one lies
**  in a subfield of the other use 'QuoFFEFFE'.
**
**  A division by 0 is an error,  and dividing 0 by a nonzero value gives  0.
**  If $0 <= a-b$ we have  $a / b ~ z^{a-1} / z^{b-1} = z^{a-b+1-1} ~ a-b+1$,
**  otherwise   we   have  $a / b ~ z^{a-b+1-1}  =  z^{a-b+(o-1)}   ~ a-b+o$.
*/
EXPORT_INLINE FFV QUO_FFV(FFV a, FFV b, const FFV * f)
{
    GAP_ASSERT(a <= f[0]);
    GAP_ASSERT(b <= f[0]);
    if (a == 0)
        return 0;
    if (b <= a)
        return a - b + 1;
    else
        return a + (f[0] - b) + 1;
}


/****************************************************************************
**
*F  POW_FFV(<a>,<n>,<f>)  . . . . . . . . . . . power of a finite field value
**
**  'POW_FFV' returns the <n>th power of the finite  field value <a> from the
**  the finite field pointed to by the pointer <f>.
**
**  Note that 'POW_FFV' may only be used  if the right  operand is an integer
**  in the range $0..order(f)-1$.
**
**  Finally 'POW_FFV' may only be used if the  product of two integers of the
**  size of 'FFV' does not cause an overflow.
**
**  If the finite field element is 0 the power is also 0, otherwise  we  have
**  $a^n ~ (z^{a-1})^n = z^{(a-1)*n} = z^{(a-1)*n % (o-1)} ~ (a-1)*n % (o-1)$
*/
EXPORT_INLINE FFV POW_FFV(FFV a, UInt n, const FFV * f)
{
    GAP_ASSERT(a <= f[0]);
    GAP_ASSERT(n <= f[0]);
    if (!n)
        return 1;
    if (!a)
        return 0;

    // Use UInt to avoid overflow in the multiplication
    UInt a1 = a - 1;
    return ((a1 * n) % f[0]) + 1;
}


/****************************************************************************
**
*F  FLD_FFE(<ffe>)  . . . . . . . field of an element of a small finite field
**
**  'FLD_FFE' returns the small finite field over which the element  <ffe> is
**  represented.
**
*/
EXPORT_INLINE FF FLD_FFE(Obj ffe)
{
    GAP_ASSERT(IS_FFE(ffe));
    return (FF)((UInt)(ffe) >> 3) & ((1 << FIELD_BITS_FFE) - 1);
}


/****************************************************************************
**
*F  VAL_FFE(<ffe>)  . . . . . . . value of an element of a small finite field
**
**  'VAL_FFE' returns the value of the element <ffe> of a small finite field.
**  Thus,  if <ffe> is $0_F$, it returns 0;  if <ffe> is $1_F$, it returns 1;
**  and otherwise if <ffe> is $z^i$, it returns $i+1$.
**
*/
EXPORT_INLINE FFV VAL_FFE(Obj ffe)
{
    GAP_ASSERT(IS_FFE(ffe));
    return (FFV)((UInt)(ffe) >> (3 + FIELD_BITS_FFE)) &
           ((1 << VAL_BITS_FFE) - 1);
}


/****************************************************************************
**
*F  NEW_FFE(<fld>,<val>)  . . . .  make a new element of a small finite field
**
**  'NEW_FFE' returns a new element  <ffe>  of the  small finite  field <fld>
**  with the value <val>.
**
*/
EXPORT_INLINE Obj NEW_FFE(FF fld, FFV val)
{
    GAP_ASSERT(val < SIZE_FF(fld));
    return (Obj)(((UInt)val << (3 + FIELD_BITS_FFE)) | ((UInt)fld << 3) |
                 (UInt)0x02);
}


/****************************************************************************
**
*F  FiniteField(<p>,<d>) .  make the small finite field with <p>^<d> elements
*F  FiniteFieldBySize(<q>) . .  make the small finite field with <q> elements
**
**  'FiniteField' returns the small finite field with <p>^<d> elements.
**  'FiniteFieldBySize' returns the small finite field with <q> elements.
*/
FF FiniteField(UInt p, UInt d);
FF FiniteFieldBySize(UInt q);


/****************************************************************************
**
*F  CommonFF(<f1>,<d1>,<f2>,<d2>) . . . . . . . . . . . . find a common field
**
**  'CommonFF' returns  a small finite field  that can represent  elements of
**  degree <d1> from the small finite field <f1> and  elements of degree <d2>
**  from the small finite field <f2>.  Note that this is not guaranteed to be
**  the smallest such field.  If  <f1> and <f2> have different characteristic
**  or the smallest common field, is too large, 'CommonFF' returns 0.
*/
FF CommonFF(FF f1, UInt d1, FF f2, UInt d2);


/****************************************************************************
**
*F  CharFFE(<ffe>)  . . . . . . . . .  characteristic of a small finite field
**
**  'CharFFE' returns the characteristic of the small finite field  in  which
**  the element <ffe> lies.
*/
UInt CharFFE(Obj ffe);


/****************************************************************************
**
*F  DegreeFFE(<ffe>)  . . . . . . . . . . . .  degree of a small finite field
**
**  'DegreeFFE' returns the degree of the smallest finite field in which  the
**  element <ffe> lies.
*/
UInt DegreeFFE(Obj ffe);


/****************************************************************************
**
*F  TypeFFE(<ffe>)  . . . . . . . . . . type of element of small finite field
**
**  'TypeFFE' returns the type of the element <ffe> of a small finite field.
**
**  'TypeFFE' is the function in 'TypeObjFuncs' for  elements in small finite
**  fields.
*/
Obj TypeFFE(Obj ffe);


/****************************************************************************
**
*F * * * * * * * * * * * * * initialize module * * * * * * * * * * * * * * *
*/


/****************************************************************************
**
*F  InitInfoFinfield()  . . . . . . . . . . . . . . . table of init functions
*/
StructInitInfo * InitInfoFinfield ( void );


#endif // GAP_FINFIELD_H