OKlibrary  0.2.1.6
ByteField.mac
Go to the documentation of this file.
00001 /* Oliver Kullmann, 23.12.2009 (Swansea) */
00002 /* Copyright 2009, 2010, 2011 Oliver Kullmann
00003 This file is part of the OKlibrary. OKlibrary is free software; you can redistribute
00004 it and/or modify it under the terms of the GNU General Public License as published by
00005 the Free Software Foundation and included in this library; either version 3 of the
00006 License, or any later version. */
00007 
00022 oklib_include("OKlib/ComputerAlgebra/CombinatorialMatrices/Lisp/Basics.mac")$
00023 oklib_include("OKlib/ComputerAlgebra/NumberTheory/Lisp/Auxiliary.mac")$
00024 oklib_include("OKlib/ComputerAlgebra/Satisfiability/Lisp/FiniteFunctions/Basics.mac")$
00025 
00026 
00027 /* ******************
00028    * Representation *
00029    ******************
00030 */
00031 
00032 /*
00033    The irreducible polynomial over ZZ_2 used as the modulus in Rijndael to
00034    define the field of order 2^8:
00035 */
00036 rijn_polynomial : '(x^8 + x^4 + x^3 + x + 1)$
00037 rijn_byte_field : [2,8,rijn_polynomial]$
00038 
00039 /* The standard representation of an element of the Rijndael field uses
00040    univariate polynomials in x over the integers, which are treated as
00041    representative of their equivalence class.
00042 */
00043 
00044 /* Standardising a univariate polynomial in x over ZZ as an element
00045    of the Rijndael field, consisting of all polynomial of degree at
00046    most 7 over ZZ_2 = {0,1}:
00047 */
00048 rijn_stand(p) := polymod(divide(p,rijn_polynomial,x)[2],2)$
00049 
00050 /* An alternative representation uses the elements of {0,...,255},
00051    interpreted as polynomial over the formal element "2".
00052    The general conversions are as follows, for integer 0 <= n and
00053    polynomials p over the nonnegative integers:
00054 */
00055 nat2polybin(n) := vecbin2polybin(int2polyadic(n,2))$
00056 polybin2nat(p) := polyadic2int(polybin2vecbin(p),2)$
00057 /* Remark: Note that in the context of the byte-field these operations
00058    only make sense for 0 <= n <= 255 and standardised polynomials p.
00059 */
00060 
00061 /* Finally, the byte-field is an 8-dimensional vector-space over the
00062    field ZZ_2 = {0,1}. Similar to consider the elements of the byte-field
00063    as (arbitrary) polynomials, we can consider here arbitrary integer-vectors,
00064    and standardisation just happens by computing the remainders modulo
00065    2 componentwise.
00066 */
00067 rijn_stand_vec(v) := mod(v,2)$
00068 
00069 /* Converting between the representation by natural numbers and the
00070    vector representation:
00071 */
00072 nat2vecbin(n) := int2polyadic(n,2)$
00073 nat2vecbin_rijn(n) := int2polyadic_padd(n,2,8)$
00074 
00075 vecbin2nat(v) := polyadic2int(v,2)$
00076 
00077 /* Converting between the representation by polynomials and the
00078    vector representation:
00079 */
00080 polybin2vecbin(p) := block([h : hipow(p,'x)],
00081  reverse(create_list(coeff(p,'x,i),i,0,h)))$
00082 polybin2vecbin_rijn(p) := block([L : polybin2vecbin(p)],
00083  append(create_list(0,i,1,8-length(L)),L))$
00084 
00085 vecbin2polybin(v) := sum_l(reverse(v) * create_list(('x)^i,i,0,length(v)-1))$
00086 
00087 /* Include for columnvector */
00088 oklib_plain_include(eigen);
00089 
00090 /* Converting between the representation by polynomials and the
00091    maxima vector representation:
00092 */
00093 polybin2mvecbin(p) := columnvector(polybin2vecbin(p))$
00094 polybin2mvecbin_rijn(p) := columnvector(polybin2vecbin_rijn(p))$
00095 
00096 mvecbin2polybin(v) := vecbin2polybin(column_m(v,1))$
00097 
00098 
00099 /* **************
00100    * Operations *
00101    **************
00102 */
00103 
00104 /* Addition and multiplication in the byte-field is just addition
00105    and multiplication of polynomials, however this does not yield
00106    standardised results; for standardised results use the following:
00107 */
00108 rijn_add(a,b) := rijn_stand(a+b)$
00109 rijn_mul(a,b) := rijn_stand(a*b)$
00110 rijn_matmul(a,b) := matrixmap(rijn_stand, a.b)$
00111 
00112 /* Inversion in the byte-field (yielding a standardised result): */
00113 rijn_inv(a) := rijn_stand(totaldisrep(gcdex(a,rijn_polynomial)[1]))$
00114 /* Extended inversion (with 0 -> 0): */
00115 rijn_einv(a) := if rijn_stand(a)=0 then 0 else rijn_inv(a)$
00116 
00117 
00118 /* The field operations with integers as input and output: */
00119 
00120 rijn_natadd(a,b) := 
00121   polybin2nat(rijn_add(nat2polybin(a), nat2polybin(b)))$
00122 /* The same operation as rijn_natadd, but now using the tge logical operator
00123    on numbers: */
00124 rijn_nataddl(a,b) := xor_ibo(a,b)$
00125 
00126 rijn_natmul(a,b) := 
00127   polybin2nat(rijn_mul(nat2polybin(a), nat2polybin(b)))$
00128 
00129 rijn_natinv(a) := 
00130   polybin2nat(rijn_einv(nat2polybin(a)))$
00131 /* As a permutation-function of {1,...,256}: */
00132 rijn_inv_pmtf(n) := rijn_natinv(n-1)+1$
00133 
00134 /* The field operations with binary vectors (as lists) as input and output: */
00135 
00136 rijn_vecadd(a,b) := rijn_stand_vec(a+b)$
00137 
00138 rijn_vecmul(a,b) := 
00139  polybin2vecbin_rijn(rijn_mul(vecbin2polybin(a), vecbin2polybin(b)))$
00140 
00141 rijn_vecinv(a) := polybin2vecbin_rijn(rijn_einv(vecbin2polybin(a)))$
00142