class Polynomial(_p: Int) {
val polynomial: Int = _p
def order: Int = = {
...
}
def mul(p: Polynomial): Polynomial = {
...
}
def div(p: Polynomial): (Int, Int) = {
...
}
def add(p: Polynomial): Polynomial = {
...
}
def sub(p: Polynomial): Polynomial = {
...
}
override def toString: String = Integer.toBinaryString(this.polynomial)
}
abstract class FiniteField(_initBitNumber: Int) {
type T = Polynomial
type GFPolynomial <: FiniteFieldPolynomial
protected val checkBitNumber: Int => Int = ???
val modulo: T
val bits: Int = checkBitNumber(_initBitNumber)
protected def createModulo(): Option[Int]
def createPolynomial(_initPolynomial: Int): FiniteFieldPolynomial
abstract class FiniteFieldPolynomial {
protected val p: T
def +(other: GFPolynomial): GFPolynomial
def -(other: GFPolynomial): GFPolynomial = {
this + other
}
def *(other: GFPolynomial): GFPolynomial
def /(other: GFPolynomial): GFPolynomial = this * other.mulInverse
def addInverse: GFPolynomial = self
def mulInverse: GFPolynomial
def self: GFPolynomial
}
}
object IrreduciblePolynomials{
private def check(p: Int, list: List[Int]): Boolean = {
val pol = Polynomial(p)
list.foreach((item: Int) => {
val i = Polynomial(item)
if ((pol div i)._2 == 0){
return false
}
})
true
}
def calcIrreducible(_deg: Int): List[Int] = {
def calc(deg: Int): List[Int] = {
if (deg == 1) return List[Int](2, 3)
// d > 2
var resultList = ListBuffer[Int]()
// generate all polynomials of degree d
val n = 1 << deg
val nd = if (_deg.equals(deg)) deg >> 1 else deg - 1
val list: List[Int] = calc(nd)
for(i <- 0 until n){
val t = i ^ n // polynomial of P set, for testing
if (check(t, list)) resultList += t
}
resultList.toList ::: list
}
if (_deg < 1) return Nil
calc(_deg).filter(_ >= (1 << _deg))
}
}
class GaloisField(_initBitNumber: Int = FiniteField.DEFAULT_BIT_NUMBER) extends FiniteField(_initBitNumber) {
override val modulo: Polynomial = ...
protected def createModulo(): Option[Int] = {
val list = IrreduciblePolynomials(this.bits)
list.headOption
}
def createPolynomial(_initPolynomial: Int): GFPolynomial = {
...
}
def createPolynomial(_binInitPolynomial: String): GFPolynomial = {
...
}
class GFPolynomial private[GaloisField](_p: Int, _m: Int) extends FiniteFieldPolynomial with Comparable[GFPolynomial]{
override def equals(other: Any): Boolean = other match {
case other: GFPolynomial => this.p.polynomial == other.p.polynomial
case _ => false
}
override protected val p = Polynomial(_p)
def this(other: GFPolynomial){
this(other.p.polynomial, bits)
}
override def self: GFPolynomial = this
override def +(other: GFPolynomial): GFPolynomial = {
GFPolynomial(this.p.polynomial ^ other.p.polynomial, bits)
}
override def -(other: GFPolynomial): GFPolynomial = { // In this case add and subtract are the same
this + other
}
override def *(other: GFPolynomial): GFPolynomial = {
val result: Polynomial = this.p mul other.p
if (result.order >= bits){
GFPolynomial((result div modulo)._2, bits)
}
else GFPolynomial(result.polynomial, bits)
}
override def mulInverse: GFPolynomial = {
if (p.polynomial == 0)
throw new NoSuchElementException("Error: there is no multiplicative inverse for zero")
var r1: Polynomial = Polynomial(modulo.polynomial)
var r2: Polynomial = this.p
var s1 = Polynomial(1)
var s2 = Polynomial(0)
var t1 = Polynomial(0)
var t2 = Polynomial(1)
var t = Polynomial(0)
var s = Polynomial(0)
var r = Polynomial(0)
while(r2.polynomial > 0){
val q: Polynomial = Polynomial((r1 div r2)._1)
r = r1 sub (q mul r2)
r1 = r2; r2 = r
s = s1 sub (q mul s2); s1 = s2; s2 = s
t = t1 sub (q mul t2); t1 = t2; t2 = t
}
GFPolynomial(t1.polynomial, bits)
}
}
}
К сожалению, не доступен сервер mySQL