|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object | +--cryptix.util.math.BigRegister | +--cryptix.util.math.TrinomialLFSR
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:
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:
The following, collected from the references, are properties and curiosities inherent to such objects:+--------------------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 -------->
Some terms and conventions associated with LFSRs, and used in this implementation, are:
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.
Implementation Notes: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
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:
Obtaining a normal representation of the powers of the polynomial is done by left rotating the LFSR's contents by K positions.+------------------->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 -------->
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:
Copyright © 1995-1997
Systemics Ltd on behalf of the
Cryptix Development Team.
All rights reserved.
$Revision: 1.2 $
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 |
|
Constructor Detail |
public TrinomialLFSR(int l, int k)
L
stages and with a connection
trinomial of the form: xL +
xK + 1.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.java.lang.IllegalArgumentException
- If k <= 0 or k >= l.Method Detail |
public java.lang.Object clone()
BigRegister
this
.clone
in class BigRegister
public void clock(int ticks)
engineClock()
method until
the LFSR has been clocked ticks
times.ticks
- Number of steps to clock the FSR by. If it is
<= 0 nothing happens.protected void engineClock(int ticks)
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
.public long next(int count)
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.count
- Number of leftmost bits to consider. If this
value is zero then return 0.count
bits
right justified in a long
.public void add(TrinomialLFSR gx)
this += gx (mod f(x))
. Note that this
operation is only meaningful, when the monic trinomial is primitive.gx
- A representation of the terms of a polynomial to add
to this
.java.lang.IllegalArgumentException
- If the argument is not in
the same group as this
.public void subtract(TrinomialLFSR gx)
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.gx
- A representation of the terms of a polynomial to
subtract from this
.java.lang.IllegalArgumentException
- If the argument is not
in the same group as this
.public void multiply(TrinomialLFSR gx)
this *= gx (mod f(x))
. Note that this
operation is only meaningful, when the monic trinomial is primitive.gx
- A representation of the terms of a polynomial to
multiply by this
.java.lang.IllegalArgumentException
- If the argument is not in
the same group as this
.public static TrinomialLFSR multiply(TrinomialLFSR p, TrinomialLFSR q)
p
- A representation of the terms of the first polynomial
multiplicand.q
- A representation of the terms of the second polynomial
multiplicand.java.lang.IllegalArgumentException
- If the arguments are not
from the same group.public void pow(BigRegister n)
this
to the n
th power modulo
f(x)). Note that this operation is only meaningful,
when the monic trinomial is primitive.n
- Bit representation of the power to raise this
polynomial representation to.java.lang.IllegalArgumentException
- If the argument's
size
is greater than that of this
.public void resetX(int n)
n
- Reset the register's contents to all zeroes except
for a 1 at the index position corresponding to
the term xn.java.lang.IllegalArgumentException
- If the argument value
is negative or greater than or equal to this
LFSR's trinomial degree.public void setX(int n)
stages
, in contrast
to the resetX()
method, are unaffected.n
- Set (to one) the register position of the term
xn.java.lang.IllegalArgumentException
- If the argument value
is negative or greater than or equal to this
LFSR's trinomial degree.public int indexOfX(int degree)
degree
- The power of the invariate x, for which
the register's index is to be found.java.lang.IllegalArgumentException
- If the argument value
is negative or greater than or equal to this
LFSR's trinomial degree.public int degreeAt(int index)
index
- The register's index relative to the polynomial term
xresult.java.lang.IllegalArgumentException
- If the argument value
is negative or greater than or equal to this
LFSR's trinomial degree.public TrinomialLFSR trinomialOne()
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
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.public TrinomialLFSR trinomialX()
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.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.public int getSize()
getSize
in class BigRegister
public int getMidTap()
public int getSlice()
public boolean isSameValue(TrinomialLFSR x)
NOTE: the equals
method is not used, because this is
a mutable object (see the requirements for equals in the Java Language
Spec).
public int compareTo(TrinomialLFSR x)
public boolean isSameGroup(TrinomialLFSR x)
this
.this
.public BigRegister toBigRegister()
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.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.public java.lang.String toString()
String
representation of the binary
contents of this
.toString
in class BigRegister
this
.public java.lang.String toPolynomial()
String
representation of the
polynomial form represented by this
LFSR's state.this
.
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |