HFE
Class Poly2_nMax

java.lang.Object
  |
  +--HFE.Poly2_nMax

class Poly2_nMax
extends java.lang.Object

This class encapsulates the operations for polynomials over the finite field F_64 which is an extension over F_4. The generation polynomial is f(x) = x^3 + x^2 + 2x + 3
The polynomials are bounded by maxLen.

Version:
0.15

Field Summary
private static Field2_n aqlTmp
          register for the use in applyQL.
private static Field2_n aqlTmp2
          register for the use in applyQL.
private static Field2_n[] aqlVec
          registers for the use in applyQL.
(package private) static Poly2_nMax div_tmp
          static variable for method div
private static Poly2_nMax[] gcd_tmp
          local variable for gcd algorithm.
private static Field2_n gcd_tmpCoeff
          local variable for gcd algorithm.
(package private) static int maxLen
          Maximal length of the polynomials
(package private) static Field2_n mod_divRes
          second static variable for our mod method
(package private) static Field2_n mod_tmp
          static variable for mod method
(package private) static Poly2_nMax modS_additive
          static variable for our mod method
(package private) static Field2_n modS_tmp
          second static variable for our mod method
(package private) static Poly2_nMax modulus
          Modulus for the mod version of the operations
(package private) static Field2_n mul_tmp
          Static register for multiplication
(package private)  Field2_n mulAdd_coeff
          static variable for mulAdd
(package private) static Field2_n[] squareMul_tmp
          local variable for squareMod.
(package private) static Field2_n squareMul_tmpCoeff
          local variable for squareMod.
(package private)  Field2_n[] value
          Current value of the polynomial.
 
Constructor Summary
(package private) Poly2_nMax()
          sets all the coefficients to zero and allocates new memory
(package private) Poly2_nMax(Poly2_nMax father)
          Creates a copy from the given polynomial
(package private) Poly2_nMax(Poly2_nMax father, int shift)
          Takes one polynomial and shifts it by the given shift.
(package private) Poly2_nMax(java.util.Random rnd)
          Generates a polynomial with random coefficients.
(package private) Poly2_nMax(java.util.Random rnd, int degree)
          Generates a polynomial with random coefficient.
 
Method Summary
(package private)  void add(Poly2_nMax whom)
          calculate this += whom as polynomial addition
(package private)  void add(Poly2_nMax a, Poly2_nMax b)
          calculates this = wen1 + wen2 as polynomial addition
(package private)  void addOne()
          calculate this += 1 as polynomial addition
(package private)  void allocMem()
          Allocates new memory.
(package private)  Field2_n applyPoly(Field2_n num)
          Uses the given polynomial as a function.
(package private)  void applyQL(Field2_n res, Field2_n num)
          res = P(num) Assumes that the polynomial has a special form, namely no constant term, and all other terms have a power of Hamming weight 2 at most.
(package private)  void copy(Poly2_nMax father)
          Takes one polynomial and copies it.
(package private)  void copyShift(Poly2_nMax father, int shift)
          Takes one polynomial and shifts it by the given shift.
(package private)  int degree()
          Returns the degree of the object.
(package private)  void div(Poly2_nMax a, Poly2_nMax b)
          Calculates this = a / b and assumes that there is _no_ remainder, i.e.
(package private)  void divS(Poly2_nMax a, Poly2_nMax b)
          Calculates this = a / b and assumes that there is _no_ remainder! Slow implementation, use div(HFE.Poly2_nMax, HFE.Poly2_nMax) instead!
(package private)  void gcd(Poly2_nMax a, Poly2_nMax b)
          Computes this = gcd(a,b) using an iterative gcd algorithm for polynomials.
(package private)  void getCoeff(Field2_n res, int pos)
          get coefficient at position pos by copying it to res
(package private)  Field2_n getCoeff(int pos)
          get coefficient at position pos by constructing a new object from type Field2_n
(package private) static void initAll()
          Initializes the static variables
(package private)  boolean isEqual(Poly2_nMax whom)
          Compares the current polynomial with the given one.
(package private)  boolean isZero()
          Checks if a polynomial is the zero polynomial.
static void main(java.lang.String[] args)
          Mainly invoces the testIt() method.
(package private)  void mod()
          Calculates this %= moduls.
(package private)  void mod(Poly2_nMax b)
          Calculates this %= b
(package private)  void mod(Poly2_nMax a, Poly2_nMax b)
          Calculates this = a % b
(package private)  void modS(Poly2_nMax b)
          Calculates this %= b slow but working implementation of mod
(package private)  void mul(Poly2_nMax a, Poly2_nMax b)
          calculates this = a * b as polynomial multiplication Assumes that a.degree + b.degree < maxLen
(package private)  void mulAdd(Field2_n coeff, Poly2_nMax poly)
          compute this = coeff*poly where coeff is from GF(2^n) and poly is an object of type Poly2_nMax
(package private)  void mulFactor(Field2_n factor)
          multiplies all coefficients by the given factor in GF(2^n) uses static memory to store the result of each step
(package private)  void setCoeff(Field2_n whom, int pos)
          set coefficient at position pos _with_ copying it
(package private)  void setCoeff(java.util.Random rnd, int pos)
          set coefficient at position pos with a random value
(package private) static void setModulus(Poly2_nMax newModulus)
          Sets the private field modulus.
(package private)  void setZero()
          Sets all the coefficients to zero without allocating new memory
(package private)  void shiftL(int shift)
          Shifts the current polynomial by the given number of places.
static void speedIt()
           
(package private)  void squareMod(Poly2_nMax in, Poly2_nMax modul, int degree)
          Calculates this = in^2 mod modul and used the fact that characteristic p=2 for GF(2^n) which means that squaring in GF(2^n) is cheaper than multiplication.
(package private)  java.lang.String stringIt()
          transfer the polynomial to a string
(package private) static void testIt()
          Tests the functionality for the whole class.
 
Methods inherited from class java.lang.Object
, clone, equals, finalize, getClass, hashCode, notify, notifyAll, registerNatives, toString, wait, wait, wait
 

Field Detail

maxLen

static final int maxLen
Maximal length of the polynomials

modulus

static Poly2_nMax modulus
Modulus for the mod version of the operations

value

Field2_n[] value
Current value of the polynomial. The polynomial has at most degree (maxLen-1). Its coefficients are taken from F_64. The element value[i] is the coefficient for x^i so value[0] is the constant term for this polynomial.

mul_tmp

static Field2_n mul_tmp
Static register for multiplication

modS_additive

static Poly2_nMax modS_additive
static variable for our mod method

modS_tmp

static Field2_n modS_tmp
second static variable for our mod method

mod_tmp

static Field2_n mod_tmp
static variable for mod method

mod_divRes

static Field2_n mod_divRes
second static variable for our mod method

div_tmp

static Poly2_nMax div_tmp
static variable for method div

mulAdd_coeff

Field2_n mulAdd_coeff
static variable for mulAdd

squareMul_tmp

static Field2_n[] squareMul_tmp
local variable for squareMod. Is glocal static for the sake of speed.

squareMul_tmpCoeff

static Field2_n squareMul_tmpCoeff
local variable for squareMod. Is glocal static for the sake of speed.

gcd_tmp

private static Poly2_nMax[] gcd_tmp
local variable for gcd algorithm. Is static glocal for the sake of speed.

gcd_tmpCoeff

private static Field2_n gcd_tmpCoeff
local variable for gcd algorithm. Is static glocal for the sake of speed.

aqlTmp

private static Field2_n aqlTmp
register for the use in applyQL. Static for the sake of speed.

aqlTmp2

private static Field2_n aqlTmp2
register for the use in applyQL. Static for the sake of speed.

aqlVec

private static Field2_n[] aqlVec
registers for the use in applyQL. Static for the sake of speed.
Constructor Detail

Poly2_nMax

Poly2_nMax()
sets all the coefficients to zero and allocates new memory

Poly2_nMax

Poly2_nMax(Poly2_nMax father)
Creates a copy from the given polynomial
Parameters:
father - polynomial to be copied

Poly2_nMax

Poly2_nMax(Poly2_nMax father,
           int shift)
Takes one polynomial and shifts it by the given shift. It basicly leaves out shift number of coefficients and starts copying at value[shift]. Another point of view is that the polynomial constructed is father * x^(shift) Makes a copy of this polynomial.
Parameters:
father - polynomial to be copied
shift - the number of elements to be shifted.

Poly2_nMax

Poly2_nMax(java.util.Random rnd)
Generates a polynomial with random coefficients. The degree of this polynomial can be expected to be (maxLen-1).
Parameters:
rnd - Random source

Poly2_nMax

Poly2_nMax(java.util.Random rnd,
           int degree)
Generates a polynomial with random coefficient. The degree of this polynomial is degree. Degree has to be non-negative (i.e. the zero polynomial can not be obtained using this function).
Parameters:
rnd - Random source
degree - degree of the resulting polynomial
Method Detail

setModulus

static void setModulus(Poly2_nMax newModulus)
Sets the private field modulus. Does not clone the moduls but storing it. Checks if the degree of the moduls is less than (maxLen/2).

degree

int degree()
Returns the degree of the object. The degree of a constant polynomial is 0, the degree of the zero polynomial is -1.

isEqual

boolean isEqual(Poly2_nMax whom)
Compares the current polynomial with the given one.
Returns:
true iff (this == whom) for all coefficients

isZero

boolean isZero()
Checks if a polynomial is the zero polynomial.
Returns:
true iff all coefficients are zero

setZero

void setZero()
Sets all the coefficients to zero without allocating new memory

getCoeff

Field2_n getCoeff(int pos)
get coefficient at position pos by constructing a new object from type Field2_n

getCoeff

void getCoeff(Field2_n res,
              int pos)
get coefficient at position pos by copying it to res

setCoeff

void setCoeff(Field2_n whom,
              int pos)
set coefficient at position pos _with_ copying it

setCoeff

void setCoeff(java.util.Random rnd,
              int pos)
set coefficient at position pos with a random value

allocMem

void allocMem()
Allocates new memory. As a side effect, sets everything to zero

copyShift

void copyShift(Poly2_nMax father,
               int shift)
Takes one polynomial and shifts it by the given shift. It basicly leaves out shift number of coefficients and starts copying at value[shift]. Makes a copy of this polynomial.
Parameters:
father - Polynomial to be copied
shift - number of elements to be shifted.

shiftL

void shiftL(int shift)
Shifts the current polynomial by the given number of places.
Parameters:
shift - number of places to be shifted

copy

void copy(Poly2_nMax father)
Takes one polynomial and copies it.

mulFactor

void mulFactor(Field2_n factor)
multiplies all coefficients by the given factor in GF(2^n) uses static memory to store the result of each step

add

void add(Poly2_nMax a,
         Poly2_nMax b)
calculates this = wen1 + wen2 as polynomial addition

add

void add(Poly2_nMax whom)
calculate this += whom as polynomial addition

addOne

void addOne()
calculate this += 1 as polynomial addition

mul

void mul(Poly2_nMax a,
         Poly2_nMax b)
calculates this = a * b as polynomial multiplication Assumes that a.degree + b.degree < maxLen

mod

void mod()
Calculates this %= moduls. Uses the static field modulus.

mod

void mod(Poly2_nMax a,
         Poly2_nMax b)
Calculates this = a % b

modS

void modS(Poly2_nMax b)
Calculates this %= b slow but working implementation of mod

mod

void mod(Poly2_nMax b)
Calculates this %= b

divS

void divS(Poly2_nMax a,
          Poly2_nMax b)
Calculates this = a / b and assumes that there is _no_ remainder! Slow implementation, use div(HFE.Poly2_nMax, HFE.Poly2_nMax) instead!

div

void div(Poly2_nMax a,
         Poly2_nMax b)
Calculates this = a / b and assumes that there is _no_ remainder, i.e. a is a multiple of b.

mulAdd

void mulAdd(Field2_n coeff,
            Poly2_nMax poly)
compute this = coeff*poly where coeff is from GF(2^n) and poly is an object of type Poly2_nMax
Parameters:
coeff - coefficient from GF(2^n) which is multiplied
poly - polynomial over GF(2^n) in x

initAll

static void initAll()
Initializes the static variables

squareMod

void squareMod(Poly2_nMax in,
               Poly2_nMax modul,
               int degree)
Calculates this = in^2 mod modul and used the fact that characteristic p=2 for GF(2^n) which means that squaring in GF(2^n) is cheaper than multiplication. Assumes that in.degree() < modul.degree() and also that the leading coefficient of modul is 1.
Parameters:
in - Polynomial to be squared
modul - Modul which is used for reduction
degree - degree of the modul (only for the sake of speed)

gcd

void gcd(Poly2_nMax a,
         Poly2_nMax b)
Computes this = gcd(a,b) using an iterative gcd algorithm for polynomials. Assumes b != zero.
Parameters:
a - Polynomial
b - Polynomial

applyPoly

Field2_n applyPoly(Field2_n num)
Uses the given polynomial as a function. Applies the value num (from F_64) to the polynomial.
Returns:
f(num)

applyQL

void applyQL(Field2_n res,
             Field2_n num)
res = P(num) Assumes that the polynomial has a special form, namely no constant term, and all other terms have a power of Hamming weight 2 at most. This is exactly the case for a QuartzLight polynomial.

stringIt

java.lang.String stringIt()
transfer the polynomial to a string

testIt

static void testIt()
Tests the functionality for the whole class. Reports errors to stdout. Works only for maxLen == 15

speedIt

public static final void speedIt()

main

public static void main(java.lang.String[] args)
Mainly invoces the testIt() method.