HFE
Class RootFinding

java.lang.Object
  |
  +--HFE.RootFinding
All Implemented Interfaces:
CheckRoot

class RootFinding
extends java.lang.Object
implements CheckRoot

This class computes root for a given polynomial over GF(2^n). The algorithm used in this class is described in

Lidl, Rudolf and Niederreiter, Harald:
Introduction to finite fields and their applications
Cambridge University Press, 1986. ISBN 0-521-30706-6,
pp. 150-156

Version:
0.1

Field Summary
(package private)  int[] degF
          registers for root finding algorithm.
(package private)  Poly2_nMax[] f
          registers for root finding algorithm.
(package private) static int regNum
          number of registers in this machine.
(package private)  int regUsed
          bitvector.
(package private)  Poly2_nMax S
          registers for root finding algorithm.
(package private)  Poly2_nMax[] square
          array of squares mod Poly.
(package private)  Field2_n tmpRoot
          temporary register for roots
 
Constructor Summary
RootFinding()
          initializes all variables in this class
 
Method Summary
private  boolean checkRoot(CheckRoot cr)
          checks if S obtains a new root for f[0..regNum-1]
 boolean checkRoot(Field2_n root)
          for debugging purposes only: returns if the root which was found is correct!
private  void compDeg(int reg)
          Method for register handling.
 boolean findRoots(Poly2_nMax poly, CheckRoot cr)
          finds all roots of given polynomial poly
private  int giveFree()
          Method for register handling.
static void main(java.lang.String[] args)
          Tests everything in this class
private  void setFree(int reg)
          Method for register handling.
static void testIt()
          Tests the functionality of the whole class.
 
Methods inherited from class java.lang.Object
, clone, equals, finalize, getClass, hashCode, notify, notifyAll, registerNatives, toString, wait, wait, wait
 

Field Detail

regNum

static final int regNum
number of registers in this machine. This number is calculated as follows: 4 registers are needed as temporary registers during the programme run. The other 6 registers are the maximum number of registers which can be used: Our polynomial has degree 33, each register used _must_ have degree 2 at most. As 2^6=64 (but 2^5=32), at most 6 polynomials of degree 2 can be found as factors of polynomial p. Therefore we obtain 10.

square

Poly2_nMax[] square
array of squares mod Poly. Must be initialized by initAll()

f

Poly2_nMax[] f
registers for root finding algorithm. Are initialized in initAll().

S

Poly2_nMax S
registers for root finding algorithm. Holds polynomial S

degF

int[] degF
registers for root finding algorithm. Hold degrees of polynomials. These degrees must be set by hand!

regUsed

int regUsed
bitvector. If regUsed_0 is 1, f[0] is in use and so on.

tmpRoot

Field2_n tmpRoot
temporary register for roots
Constructor Detail

RootFinding

public RootFinding()
initializes all variables in this class
Method Detail

setFree

private void setFree(int reg)
Method for register handling. Frees a given register.

giveFree

private int giveFree()
Method for register handling. Returns the name of a free register and allocates this register.

compDeg

private void compDeg(int reg)
Method for register handling. Computes the degree of a given register

checkRoot

public boolean checkRoot(Field2_n root)
for debugging purposes only: returns if the root which was found is correct!
Specified by:
checkRoot in interface CheckRoot
Returns:
did we find the correct root?

checkRoot

private boolean checkRoot(CheckRoot cr)
checks if S obtains a new root for f[0..regNum-1]
Returns:
true iff we do not search for more roots

findRoots

public boolean findRoots(Poly2_nMax poly,
                         CheckRoot cr)
finds all roots of given polynomial poly
Parameters:
ply - Polynomial over GF(2^n) which roots are to be found

testIt

public static void testIt()
Tests the functionality of the whole class. If there occurs any error it will be printed on stdout.

main

public static void main(java.lang.String[] args)
Tests everything in this class
See Also:
testIt()