cryptix.util.math
public class TrinomialLFSR extends BigRegister implements Cloneable, Serializable
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 $
Since: Cryptix 2.2.2
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.
|
Object | clone() |
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.
|
String | toPolynomial()
Return a formatted String representation of the
polynomial form represented by this LFSR's state.
|
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.
|
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: IllegalArgumentException If k <= 0 or k >= l.
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: IllegalArgumentException If the argument is not in
the same group as this
.
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.
Returns: -1, 0, +1 If the contents of this object are respectively less than, equal to, or greater than those of the argument.
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: IllegalArgumentException If the argument value
is negative or greater than or equal to this
LFSR's trinomial degree.
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
.
Returns: The degree/power of the mid-tap element in this LFSR.
Returns: The number of elements in this LFSR.
Returns: The maximum number of meaningful bits in this LFSR.
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: IllegalArgumentException If the argument value
is negative or greater than or equal to this
LFSR's trinomial degree.
this
.
Returns: true iff the argument is a polynomial that belongs to
the same Group as this
.
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.
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: IllegalArgumentException If the argument is not in
the same group as this
.
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: IllegalArgumentException If the arguments are not from the same group.
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
.
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: IllegalArgumentException If the argument's
size
is greater than that of this
.
Parameters: n Reset the register's contents to all zeroes except for a 1 at the index position corresponding to the term xn.
Throws: IllegalArgumentException If the argument value
is negative or greater than or equal to this
LFSR's trinomial degree.
stages
, in contrast
to the resetX()
method, are unaffected.
Parameters: n Set (to one) the register position of the term xn.
Throws: IllegalArgumentException If the argument value
is negative or greater than or equal to this
LFSR's trinomial degree.
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: IllegalArgumentException If the argument is not
in the same group as this
.
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.
String
representation of the
polynomial form represented by this
LFSR's state.
Returns: A formatted string representation of the binary contents
of this
.
String
representation of the binary
contents of this
.
Returns: A formatted string representation of the binary contents
of this
.
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.
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.