Loading...
Searching...
No Matches
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
}
b
CanonicalForm b
Definition cfModGcd.cc:4111
ff_prime
VAR int ff_prime
Definition ffops.cc:23

## ff_biginv()

int ff_biginv | ( | const int | a | ) |

Definition at line 81 of file ffops.cc.

{
if (UNLIKELY(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;
}
}
}
p
int p
Definition cfModGcd.cc:4086
UNLIKELY
#define UNLIKELY(expression)
Definition ffops.cc:20

## 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)
Definition ffops.h:149
ff_mul
int ff_mul(const int a, const int b)
Definition ffops.h:139

## 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_invtab
VAR short * ff_invtab
Definition ffops.cc:26
ff_big
VAR bool ff_big
Definition ffops.cc:25
ff_biginv
int ff_biginv(const int)
Definition ffops.cc:81
ff_newinv
int ff_newinv(const int)
Definition ffops.cc:39

## 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 );
}
FACTORY_INT64
#define FACTORY_INT64
Definition ffops.h:24
ff_norm
int ff_norm(const int a)
Definition ffops.h:39

## 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 39 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 28 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_halfprime
VAR int ff_halfprime
Definition ffops.cc:24

## 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;
}
SW_SYMMETRIC_FF
static const int SW_SYMMETRIC_FF
set to 1 for symmetric representation over F_q
Definition cf_defs.h:33
cf_glob_switches
INST_VAR CFSwitches cf_glob_switches
Definition cf_switches.cc:54

## 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.