Overview | Package | Class | Use | Tree | Deprecated | Index | Help
| Cryptix V3.2
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

## cryptix.util.math
Class TrinomialLFSR

    java.lang.Object
      |
      +--cryptix.util.math.BigRegister
            |
            +--cryptix.util.math.TrinomialLFSR

public class TrinomialLFSR
extends BigRegister
implements java.lang.Cloneable, java.io.Serializable

A class that implements a special category of Linear Feedback Shift Register (LFSR). Formally speaking, it implements a Fibonacci LFSR --LFSR(II)-- with a Monic, Non-Singular, Trinomial Connection (Characteristic) function of the form f(x) = x L + xK + 1.

Menezes et al. define a generalised LFSR --with an L-degree connection polynomial-- as follows:

An LFSR of length L consists of L stages (or delay elements) numbered 0, 1, ..., L-1, each capable of storing one bit and having one input and one output; and a clock which controls the movement of data. During each unit of time the following operations are performed:

- the contents of stage 0 is output and forms part of the output sequence;
- the contents of stage i is moved to stage i-1 for each i, 1 <= i <= L-1; and
- the new contents of stage L-1 is the feedback bit sj which is calculated by adding together modulo 2 the previous contents of a fixed subset of stages 0, 1, ..., L-1 also called taps.

Such an LFSR, referred to as a Fibonacci LFSR, Type II LFSR , or simply LFSR(II), is denoted by <L, C(D)>, where C(D) is called the connection or characteristic polynomial and is defined as:

> C(D) = 1 + c1D + c 2D2 + ... + cLDL Î Z2[D]

A Linear Feedback Shift Register (LFSR) with a trinomial function of the form 1 + xK + xL as its connection polynomial can be schematised as follows:

>       +--------------------XOR<-------------------------------+
>       |                     ^                                 |
>       |                     |                                 |
>       |   +-----+-----+-----+-----+-----+-----+-----+-----+   |
>       |   |stage|     |stage|stage|     |stage|stage|stage|   |
>       +---| L-1 | ... | L-K |L-K-1| ... |  2  |  1  |  0  |---+--> output
>           +-----+-----+-----+-----+-----+-----+-----+-----+
>             K+1         L-1    0          K-3   K-2   K-1
>           <------- Powers of the polynomial terms -------->

The following, collected from the references, are properties and curiosities inherent to such objects:

- Choosing a primitive trinomial over Z 2, ensures that each of the LFSR's 2L - 1 initial states produces an output sequence with maximum possible period 2 L - 1.
- If 2L - 1 is a prime (a Mersenne prime), then every irreducible polynomial of degree L in Z2[x] is also primitive.
- Irreducible trinomials, f(x), of degree L can be used to represent the elements of the finite field F2L = Z2 [x]/(f(x)), the set of all polynomials in Z 2[x] of degree less than L where the addition and multiplication of polynomials is performed modulo f(x).
- If f(x) is a primitive polynomial of degree L, then xL f(x -1) = f'(x) is also a primitive polynomial. This is easily shown using the definition of a primitive polynomial, and the properties of modulo-2 arithmetic. A little thought shows that the register taps of f'(x) are the mirror image of those of f(x). And the sequence produced by the tap-reversed generator is the time reversal of the original.

Some terms and conventions associated with LFSRs, and used in this implementation, are:

- tap-sequence: the powers of the terms of the polynomial. In a monic (starts with 1 + ...), non- singular (the term xL for an L-long register is part of the polynomial function) trinomial, the sequence consists of 3 elements: 0, K, and L.
- mid-tap: the second/middle value of the tap sequence of a monic, non-singular trinomial.
- state: the value of the LFSR's contents. Also used to represent the coefficients of a polynomial in the field F2L.
- terms of a polynomial: the correspondence between the LFSR stages and the powers of x (the polynomial invariate) in the GF[2L] with f(x) = xL + xK + 1 is such that the term with degree 0 is at stage L - K - 1; the term with degree 1 is at stage L - K - 2, etc... After stage 0, the relationship restarts from `stage` L - 1. The reason for this gymnastic is to facilitate computing the successive powers of x --based on the mathematical fact that g(x) = x is a generator of the monic primitive f(x)-- which in turn are used in the computation of polynomial multiplication modulo f(x) . When so ordered, multiplying a polynomial p(x) by x t modulo f(x) is as simple as loading the LFSR's register with the terms of the polynomial, and clocking it by t cycles.

Finally, Menezes et al. lists (Table 4.9, p.162) some primitive polynomials of degree m over Z2, 2m - 1 a Mersenne prime. The following is an excerpt from this table for values of m, m <= 4096 and k, 1 <= k <= m/2, for which the monic, non-singular trinomial xm + xk + 1 is irreducible over Z2.

>         m  |  k
>      ------+------------------------------
>         2  |    1
>         3  |    1
>         5  |    2
>         7  |    1,    3
>        17  |    3,    5,     6
>        31  |    3,    6,     7,   13
>        89  |   38
>       127  |    1,    7,    15,   30,  63
>       521  |   32,   48,   158,  168
>       607  |  105,  147,   273
>      1279  |  216,  418
>      2281  |  715,  915,  1029
>      3217  |   67,  576

Implementation Notes:

In order to increase performance of this class, and since it's extending `BigRegister`, which assumes a bit numbering using bit index 0 as the rightmost one, our LFSR will actually look like so:

>          +------------------->XOR--------------------------------+
>          |                     ^                                 |
>          |                     |                                 |
>          |   +-----+-----+-----+-----+-----+-----+-----+-----+   |
>          |   | bit |     | bit | bit |     | bit | bit | bit |   |
>       <--+---| L-1 | ... | L-K |L-K-1| ... |  2  |  1  |  0  |<--+
>              +-----+-----+-----+-----+-----+-----+-----+-----+
>                K-1          0    L-1         K+2   K+1    K
>              <------- Powers of the polynomial terms -------->

Obtaining a normal representation of the powers of the polynomial is done by left rotating the LFSR's contents by K positions.

Clocking the LFSR consists of executing the following pseudo-code:

         out = getBit(L-1);
         in = out ^ getBit(L-K-1);
         shiftLeft(1);
         if (in == 1) setBit(0);

References:

1. [HAC] A. J. Menezes, P. C. van Oorschot, S. A. Vanstone, Handbook of Applied Cryptography CRC Press 1997, pp 195-212.

2. [AC2] Bruce Schneier, Applied Cryptography, 2nd edition, John Wiley & Sons, Inc. 1996, pp 372-428.

3. [LFSR] Arthur H. M. Ross, Linear Feedback Shift Registers, WWW page www.cdg.org/a_ross/LFSR.html

Copyright © 1995-1997 Systemics Ltd on behalf of the Cryptix Development Team.
All rights reserved.

$Revision: 1.2 $

Since:
  Cryptix 2.2.2
Author:
  Raif S. Naffah
See Also:
  Serialized Form

Fields inherited from class cryptix.util.math.BigRegister
`MAXIMUM_SIZE`

Constructor Summary
`TrinomialLFSR(int l, int k)` Define an LFSR with `L` stages and with a connection trinomial of the form: xL + xK + 1.

Method Summary
`void` | `add(TrinomialLFSR gx)` Compute `this += gx (mod f(x))`.
`void` | `clock(int ticks)` Repeatedly invoke the `engineClock()` method until the LFSR has been clocked `ticks` times.
`java.lang.Object` | `clone()` Return a reference to a duplicate of `this`.
`int` | `compareTo(TrinomialLFSR x)` Compare this LFSR to the argument, returning -1, 0 or 1 for less than, equal to, or greater than comparison.
`int` | `degreeAt(int index)` Return the power of the term xresult relative to the given register's index.
`protected void` | `engineClock(int ticks)` Clock the register ticks steps.
`int` | `getMidTap()` Return the degree/power of the mid-tap element in this LFSR.
`int` | `getSize()` Return the number of elements in this LFSR, which is also the degree of the trinomial.
`int` | `getSlice()` Return the maximum number of meaningful bits in this LFSR, which is also the maximum number of bits that can be processed in one operation without loss of desired output sequence.
`int` | `indexOfX(int degree)` Return the register's index relative to the polynomial term xdegree.
`boolean` | `isSameGroup(TrinomialLFSR x)` Return true iff the argument is a polynomial that belongs to the same Group as `this`.
`boolean` | `isSameValue(TrinomialLFSR x)` Return true if the TrinomialLFSR x has equal characteristics and contents to this one; false otherwise.
`void` | `multiply(TrinomialLFSR gx)` Compute `this *= gx (mod f(x))`.
`static TrinomialLFSR` | `multiply(TrinomialLFSR p, TrinomialLFSR q)` Return the product of the two arguments modulo f(x)), where both arguments are members of the same polynomial group with the same monic trinomial f(x).
`long` | `next(int count)` Return the value of the leftmost `count` bits of this LFSR and clock it by as many ticks.
`void` | `pow(BigRegister n)` Raise `this` to the `n`th power modulo f(x)).
`void` | `resetX(int n)` Set the LFSR's initial state to a value that corresponds to the polynomial term of the designated degree.
`void` | `setX(int n)` Set (to one) this LFSR's polynomial term of the given degree.
`void` | `subtract(TrinomialLFSR gx)` Compute `this -= gx (mod f(x))`.
`BigRegister` | `toBigRegister()` Return the state of `this` LFSR as a `BigRegister` object where now the powers of the polynomial terms are ordered in ascending succession starting from power 0 at index 0.
`java.lang.String` | `toPolynomial()` Return a formatted `String` representation of the polynomial form represented by `this` LFSR's state.
`java.lang.String` | `toString()` Return a formatted `String` representation of the binary contents of `this`.
`TrinomialLFSR` | `trinomialOne()` Return a `TrinomialLFSR` object whose state is set to the powers of the polynomial p(x) such that p(x) = 1 in the polynomial Group defined over the trinomial function of `this` object.
`TrinomialLFSR` | `trinomialX()` Return a `TrinomialLFSR` object whose state is set to the powers of the polynomial p(x) such that p(x) = x in the polynomial Group defined over the trinomial function of `this` object.

Methods inherited from class cryptix.util.math.BigRegister
`and, andNot, atRandom, atRandom, byteValue, clearBit, compareTo, countSetBits, flipBit, getBit, getBits, highestSetBit, intValue, invertOrder, isSameValue, load, load, longValue, lowestSetBit, not, or, reset, rotateLeft, rotateRight, setBit, setBits, shiftLeft, shiftRight, testBit, toByteArray, valueOf, xor`

Methods inherited from class java.lang.Object
`equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait`

Constructor Detail

### TrinomialLFSR

    public TrinomialLFSR(int l,
                         int k)

  Define an LFSR with `L` stages and with a connection trinomial of the form: xL + xK + 1.
  Parameters:
    `l` - Size of the register; ie. number of levels/stages of this LFSR. Is also the degree of the connection trinomial.
    `k` - Degree/power of the mid-tap within the LFSR.
  Throws:
    java.lang.IllegalArgumentException - If k <= 0 or k >= l.

Method Detail

### clone

    public java.lang.Object clone()

  Description copied from class: BigRegister
  Return a reference to a duplicate of `this`.
  Overrides:
    clone in class BigRegister

### clock

    public void clock(int ticks)

  Repeatedly invoke the `engineClock()` method until the LFSR has been clocked `ticks` times.
  Parameters:
    `ticks` - Number of steps to clock the FSR by. If it is <= 0 nothing happens.

### engineClock

    protected void engineClock(int ticks)

  Clock the register ticks steps.
  Parameters:
    `ticks` - Number of steps to clock the register. It is the responsibility of the caller to ensure that this value never exceeds that of `slice`.

### next

    public long next(int count)

  Return the value of the leftmost `count` bits of this LFSR and clock it by as many ticks. Note however that only the minimum of `count` and `slice` bits, among those returned, are meaningful.
  Parameters:
    `count` - Number of leftmost bits to consider. If this value is zero then return 0.
  Returns:
    The value of the leftmost `count` bits right justified in a `long`.

### add

    public void add(TrinomialLFSR gx)

  Compute `this += gx (mod f(x))`. Note that this operation is only meaningful, when the monic trinomial is primitive.
  Parameters:
    `gx` - A representation of the terms of a polynomial to add to `this`.
  Throws:
    java.lang.IllegalArgumentException - If the argument is not in the same group as `this`.

### subtract

    public void subtract(TrinomialLFSR gx)

  Compute `this -= gx (mod f(x))`. Note that this operation is only meaningful, when the monic trinomial is primitive. When such is the case the result is the same as that obtained by the `add()` method since in F2n every polynomial is its own additive inverse.
  Parameters:
    `gx` - A representation of the terms of a polynomial to subtract from `this`.
  Throws:
    java.lang.IllegalArgumentException - If the argument is not in the same group as `this`.

### multiply

    public void multiply(TrinomialLFSR gx)

  Compute `this *= gx (mod f(x))`. Note that this operation is only meaningful, when the monic trinomial is primitive.
  Parameters:
    `gx` - A representation of the terms of a polynomial to multiply by `this`.
  Throws:
    java.lang.IllegalArgumentException - If the argument is not in the same group as `this`.

### multiply

    public static TrinomialLFSR multiply(TrinomialLFSR p,
                                         TrinomialLFSR q)

  Return the product of the two arguments modulo f(x)), where both arguments are members of the same polynomial group with the same monic trinomial f(x). Note that this operation is only meaningful, when the monic trinomial is primitive.
  Parameters:
    `p` - A representation of the terms of the first polynomial multiplicand.
    `q` - A representation of the terms of the second polynomial multiplicand.
  Returns:
    The product of the two arguments modulo f(x)).
  Throws:
    java.lang.IllegalArgumentException - If the arguments are not from the same group.

### pow

    public void pow(BigRegister n)

  Raise `this` to the `n`th power modulo f(x)). Note that this operation is only meaningful, when the monic trinomial is primitive.
  Parameters:
    `n` - Bit representation of the power to raise this polynomial representation to.
  Throws:
    java.lang.IllegalArgumentException - If the argument's `size` is greater than that of `this`.

### resetX

    public void resetX(int n)

  Set the LFSR's initial state to a value that corresponds to the polynomial term of the designated degree.
  Parameters:
    `n` - Reset the register's contents to all zeroes except for a 1 at the index position corresponding to the term xn.
  Throws:
    java.lang.IllegalArgumentException - If the argument value is negative or greater than or equal to `this` LFSR's trinomial degree.

### setX

    public void setX(int n)

  Set (to one) this LFSR's polynomial term of the given degree. The other `stages`, in contrast to the `resetX()` method, are unaffected.
  Parameters:
    `n` - Set (to one) the register position of the term xn.
  Throws:
    java.lang.IllegalArgumentException - If the argument value is negative or greater than or equal to `this` LFSR's trinomial degree.

### indexOfX

    public int indexOfX(int degree)

  Return the register's index relative to the polynomial term xdegree.
  Parameters:
    `degree` - The power of the invariate x, for which the register's index is to be found.
  Returns:
    The register's index relative to the polynomial term xdegree.
  Throws:
    java.lang.IllegalArgumentException - If the argument value is negative or greater than or equal to `this` LFSR's trinomial degree.

### degreeAt

    public int degreeAt(int index)

  Return the power of the term xresult relative to the given register's index.
  Parameters:
    `index` - The register's index relative to the polynomial term xresult.
  Returns:
    The power of the invariate x relative to the given register's index.
  Throws:
    java.lang.IllegalArgumentException - If the argument value is negative or greater than or equal to `this` LFSR's trinomial degree.

### trinomialOne

    public TrinomialLFSR trinomialOne()

  Return a `TrinomialLFSR` object whose state is set to the powers of the polynomial p(x) such that p(x) = 1 in the polynomial Group defined over the trinomial function of `this` object.
  Returns:
    A `TrinomialLFSR` object whose state is set to the powers of the polynomial p(x) such that p(x) = 1 in the polynomial Group defined over the trinomial function of `this` object.

### trinomialX

    public TrinomialLFSR trinomialX()

  Return a `TrinomialLFSR` object whose state is set to the powers of the polynomial p(x) such that p(x) = x in the polynomial Group defined over the trinomial function of `this` object.
  Returns:
    A `TrinomialLFSR` object whose state is set to the powers of the polynomial p(x) such that p(x) = x in the polynomial Group defined over the trinomial function of `this` object.

### getSize

    public int getSize()

  Return the number of elements in this LFSR, which is also the degree of the trinomial.
  Overrides:
    getSize in class BigRegister
  Returns:
    The number of elements in this LFSR.

### getMidTap

    public int getMidTap()

  Return the degree/power of the mid-tap element in this LFSR.
  Returns:
    The degree/power of the mid-tap element in this LFSR.

### getSlice

    public int getSlice()

  Return the maximum number of meaningful bits in this LFSR, which is also the maximum number of bits that can be processed in one operation without loss of desired output sequence.
  Returns:
    The maximum number of meaningful bits in this LFSR.

### isSameValue

    public boolean isSameValue(TrinomialLFSR x)

  Return true if the TrinomialLFSR x has equal characteristics and contents to this one; false otherwise.

  NOTE: the `equals` method is not used, because this is a mutable object (see the requirements for equals in the Java Language Spec).

  Returns:
    true iff x has equal characteristics and contents.

### compareTo

    public int compareTo(TrinomialLFSR x)

  Compare this LFSR to the argument, returning -1, 0 or 1 for less than, equal to, or greater than comparison.
  Returns:
    -1, 0, +1 If the contents of this object are respectively less than, equal to, or greater than those of the argument.

### isSameGroup

    public boolean isSameGroup(TrinomialLFSR x)

  Return true iff the argument is a polynomial that belongs to the same Group as `this`.
  Returns:
    true iff the argument is a polynomial that belongs to the same Group as `this`.

### toBigRegister

    public BigRegister toBigRegister()

  Return the state of `this` LFSR as a `BigRegister` object where now the powers of the polynomial terms are ordered in ascending succession starting from power 0 at index 0.
  Returns:
    The state of `this` LFSR as a `BigRegister` object where now the powers of the polynomial terms are ordered in ascending succession starting from power 0 at index 0.

### toString

    public java.lang.String toString()

  Return a formatted `String` representation of the binary contents of `this`.
  Overrides:
    toString in class BigRegister
  Returns:
    A formatted string representation of the binary contents of `this`.

### toPolynomial

    public java.lang.String toPolynomial()

  Return a formatted `String` representation of the polynomial form represented by `this` LFSR's state.
  Returns:
    A formatted string representation of the binary contents of `this`.

Overview | Package | Class | Use | Tree | Deprecated | Index | Help
| Cryptix V3.2
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

Copyright (C) 1995-2000 The Cryptix Foundation Ltd. All rights reserved.