ffops.h File Reference

operations in a finite prime field F_p. More...

#include "cf_globals.h"
#include <NTL/config.h>

Go to the source code of this file.

Macros
#define	FACTORY_INT64   long int

Functions
int	ff_newinv (const int)
int	ff_biginv (const int)
void	ff_setprime (const int)
int	ff_norm (const int a)
long	ff_norm (const long a)
int	ff_symmetric (const int a)
long	ff_symmetric (const long a)
int	ff_add (const int a, const int b)
int	ff_sub (const int a, const int b)
int	ff_neg (const int a)
int	ff_mul (const int a, const int b)
int	ff_inv (const int a)
int	ff_div (const int a, const int b)

Variables
EXTERN_VAR int	ff_prime
EXTERN_VAR int	ff_halfprime
EXTERN_VAR short *	ff_invtab
EXTERN_VAR bool	ff_big

Detailed Description

operations in a finite prime field F_p.

The largest supported p is 536870909, i.e. the largest prime less than 2^29.

Definition in file ffops.h.

Macro Definition Documentation

FACTORY_INT64

#define FACTORY_INT64   long int

Definition at line 24 of file ffops.h.

Function Documentation

ff_add()

int ff_add ( const int  a, const int  b  )

inline

Definition at line 97 of file ffops.h.

{
    //return ff_norm( a + b );
#if defined(NTL_AVOID_BRANCHING)
    int r=( a + b );
    r -= ff_prime;
    r += (r >> 31) & ff_prime;
    return r;
#else
    int r=( a + b );
    if (r >= ff_prime) r -= ff_prime;
    return r;
#endif
}

ff_biginv()

int ff_biginv

(

const int

a

)

Definition at line 72 of file ffops.cc.

{
    if (a < 2)
      return a;
    int p, q, r1, r2, y1, y2;
    r1 = p = ff_prime;
    q = r1 / a;
    y1 = -q;
    r1 -= a * q;
    if (r1 == 1)
      return p + y1;
    r2 = a;
    y2 = 1;
    for (;;)
    {
      q = r2 / r1;
      y2 -= y1 * q;
      r2 -= r1 * q;
      if (r2 == 1)
      {
        if (y2 > 0)
          return y2;
        else
          return p + y2;
      }
      q = r1 / r2;
      y1 -= y2 * q;
      r1 -= r2 * q;
      if (r1 == 1)
      {
        if (y1 > 0)
          return y1;
        else
          return p + y1;
      }
    }
}

ff_div()

int ff_div ( const int  a, const int  b  )

inline

Definition at line 163 of file ffops.h.

{
    return ff_mul( a, ff_inv( b ) );
}

ff_inv()

int ff_inv ( const int  a )

inline

Definition at line 149 of file ffops.h.

{
    if ( ff_big )
        return ff_biginv( a );
    else {
        int b;
        if ( (b = (int)(ff_invtab[a])) )
            return b;
        else
            return ff_newinv( a );
    }
 
}

ff_mul()

int ff_mul ( const int  a, const int  b  )

inline

Definition at line 139 of file ffops.h.

{
#if SIZEOF_LONG==4
    if ( ff_big )
        return ff_bignorm( (FACTORY_INT64)a * (FACTORY_INT64)b );
    else
#endif /* else: FACTORY_INT64 is long, i.e. ff_bignorm is the same as ff_norm(long) */
        return ff_norm ( (long)a * (long)b );
}

ff_neg()

int ff_neg ( const int  a )

inline

Definition at line 126 of file ffops.h.

{
    //return ff_norm( -a );
// EXPERIMENT
#if defined(NTL_AVOID_BRANCHING)
    int r= -a;
    r += (r >> 31) & ff_prime;
    return r;
#else
    return ( a == 0 ? 0 : ff_prime-a );
#endif
}

ff_newinv()

int ff_newinv

(

const int

a

)

Definition at line 30 of file ffops.cc.

{
    if (a < 2)
          return (ff_invtab[a] = a);
    int p, q, r1, r2, y1, y2;
    r1 = p = ff_prime;
    q = r1 / a;
    y1 = -q;
    r1 -= a * q;
    if (r1 == 1)
    {
      y1 += p;
      ff_invtab[y1] = a;
      return (ff_invtab[a] = y1);
    }
    r2 = a;
    y2 = 1;
    for (;;)
    {
      q = r2 / r1;
      y2 -= y1 * q;
      r2 -= r1 * q;
      if (r2 == 1)
      {
        if (y2 < 0)
          y2 += p;
        ff_invtab[y2] = a;
        return (ff_invtab[a] = y2);
      }
      q = r1 / r2;
      y1 -= y2 * q;
      r1 -= r2 * q;
      if (r1 == 1)
      {
        if (y1 < 0)
          y1 += p;
        ff_invtab[y1] = a;
        return (ff_invtab[a] = y1);
      }
    }
}

ff_norm() [1/2]

int ff_norm ( const int  a )

inline

Definition at line 39 of file ffops.h.

{
    int n = a % ff_prime;
#if defined(NTL_AVOID_BRANCHING)
    n += (n >> 31) & ff_prime;
    return n;
#else
    if (n < 0) n += ff_prime;
    return n;
#endif
}

ff_norm() [2/2]

long ff_norm ( const long  a )

inline

Definition at line 51 of file ffops.h.

{
    long n = a % (long)ff_prime;
#if defined(NTL_AVOID_BRANCHING)
    #if SIZEOF_LONG==8
    n += (n >> 63) & ff_prime;
    #else
    n += (n >> 31) & ff_prime;
    #endif
    return n;
#else
    if (n < 0) n += (long)ff_prime;
    return n;
#endif
}

ff_setprime()

void ff_setprime

(

const int

p

)

Definition at line 19 of file ffops.cc.

{
    if ( p != ff_prime )
    {
        ff_prime = p;
        ff_halfprime = ff_prime / 2;
        if ( ! ff_big )
            memset( ff_invtab, 0, ff_prime*sizeof(short) );
    }
}

ff_sub()

int ff_sub ( const int  a, const int  b  )

inline

Definition at line 112 of file ffops.h.

{
    //return ff_norm( a - b );
#if defined(NTL_AVOID_BRANCHING)
    int r=( a - b );
    r += (r >> 31) & ff_prime;
    return r;
#else
    int r=( a - b );
    if (r < 0) r += ff_prime;
    return r;
#endif
}

ff_symmetric() [1/2]

int ff_symmetric ( const int  a )

inline

Definition at line 67 of file ffops.h.

{
    if ( cf_glob_switches.isOn( SW_SYMMETRIC_FF ) )
        return ( a > ff_halfprime ) ? a - ff_prime : a;
    else
        return a;
}

ff_symmetric() [2/2]

long ff_symmetric ( const long  a )

inline

Definition at line 75 of file ffops.h.

{
    if ( cf_glob_switches.isOn( SW_SYMMETRIC_FF ) )
        return ( a > ff_halfprime ) ? a - ff_prime : a;
    else
        return a;
}

Variable Documentation

ff_big

EXTERN_VAR bool ff_big

Definition at line 33 of file ffops.h.

ff_halfprime

EXTERN_VAR int ff_halfprime

Definition at line 31 of file ffops.h.

ff_invtab

EXTERN_VAR short* ff_invtab

Definition at line 32 of file ffops.h.

ff_prime

EXTERN_VAR int ff_prime

Definition at line 30 of file ffops.h.