OKlibrary  0.2.1.6
SmallScaleWordFields.mac
Go to the documentation of this file.
00001 /* Matthew Gwynne, 4.2.2010 (Swansea) */
00002 /* Copyright 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/NumberTheory/Lisp/Auxiliary.mac")$
00023 
00024 
00025 /* ******************
00026    * Representation *
00027    ******************
00028 */
00029 
00030 /*
00031    The irreducible polynomials over ZZ_b used as the modulus in the small
00032    scale variants of Rijndael to define the field of order b^e:
00033 */
00034 ss_polynomial_2_1 : '(x)$
00035 ss_polynomial_2_4 : '(x^4 + x + 1)$
00036 ss_polynomial_2_8 : '(x^8 + x^4 + x^3 + x + 1)$ /* == rijn_polynomial */
00037 /* Function which given the base and the exponent for a
00038    finite field of type GF(b^e) returns the default modulus polynomial
00039    used in the small scale system. */
00040 ss_polynomial(b,e) :=
00041   if b = 2 then
00042     if e = 1 then ss_polynomial_2_1
00043     else if e = 4 then ss_polynomial_2_4
00044     else if e = 8 then ss_polynomial_2_8
00045     else und
00046   else und$
00047 
00048 
00049 /* The standard representation of an element of the (small scale) Rijndael
00050    field uses univariate polynomials in x over the integers, which are treated
00051    as representative of their equivalence class.
00052 */
00053 
00054 /* Standardising a univariate polynomial in x over ZZ as an element
00055    of the field field defined by the characteristic e and
00056    modulo polynomial mod_poly:
00057 */
00058 ss_stand(p,b,mod_poly) := polymod(divide(p,mod_poly,x)[2],b)$
00059 
00060 /* An alternative representation uses the elements of {0,...,b^e-1},
00061    interpreted as polynomial over the formal element "b".
00062    The general conversions are as follows, for integer 0 <= n and
00063    polynomials p over the nonnegative integers:
00064 */
00065 nat2poly(n,b) := vec2poly(int2polyadic(n,b))$
00066 poly2nat(p,b) := polyadic2int(poly2vec(p),b)$
00067 /* Remark: Note that in the context of the word-field these operations
00068    only make sense for 0 <= n <= b^e-1 and standardised polynomials p.
00069 */
00070 
00071 /* Finally, the word-field for small scale variants is an e-dimensional
00072    vector-space over the field ZZ_b = {0,...,b-1}. Similar to consider the
00073    elements of the word-field as (arbitrary) polynomials, we can consider here
00074    arbitrary integer-vectors, and standardisation just happens by computing
00075    the remainders modulo b component-wise.
00076 */
00077 ss_stand_vec(v,b) := mod(v,b)$
00078 
00079 /* Converting between the representation by natural numbers and the
00080    vector representation:
00081 */
00082 nat2vec(n,b) := int2polyadic(n,b)$
00083 nat2vec_ss(n,b,e) := int2polyadic_padd(n,b,e)$
00084 /* Remark: Note that these functions are simply aliases for int2polyadic,
00085    and are provided so as to maintain consistency naming with
00086    ByteField.mac and AdvancedEncryptionStandard.mac . */
00087 
00088 vec2nat(v,b) := polyadic2int(v,b)$
00089 
00090 /* Converting between the representation by polynomials and the
00091    vector representation:
00092 */
00093 poly2vec(p) := block([h : hipow(p,'x)],
00094  reverse(create_list(coeff(p,'x,i),i,0,h)))$
00095 poly2vec_ss(p,e) := block([L : poly2vec(p)],
00096  append(create_list(0,i,1,e-length(L)),L))$
00097 poly2mvec(p) := columnvector(poly2vec(p))$
00098 poly2mvec_ss(p,e) := columnvector(poly2vec_ss(p,e))$
00099 
00100 vec2poly(v) := sum_l(reverse(v) * create_list(('x)^i,i,0,length(v)-1))$
00101 mvec2poly(v) := vec2poly(column_m(v,1))$ /* Maxima vector (matrix) */
00102 
00103 
00104 /* **************
00105    * Operations *
00106    **************
00107 */
00108 
00109 /* Addition and multiplication in the word-field is just addition
00110    and multiplication of polynomials, however this does not yield
00111    standardised results; for standardised results use the following:
00112 */
00113 ss_add(m,n,b,mod_poly) := ss_stand(m+n,b,mod_poly)$
00114 ss_mul(m,n,b,mod_poly) := ss_stand(m*n,b,mod_poly)$
00115 ss_matmul(m,n,b,mod_poly) :=
00116   matrixmap(lambda([p],ss_stand(p,b,mod_poly)), m.n)$
00117 
00118 /* Inversion in the word-field (yielding a standardised result): */
00119 ss_inv(p,b,mod_poly) :=
00120   ss_stand(totaldisrep(gcdex(p,mod_poly)[1]),b,mod_poly)$
00121 /* Extended inversion (with 0 -> 0): */
00122 ss_einv(p,b,mod_poly) :=
00123   if ss_stand(p,b,mod_poly)=0 then 0 else ss_inv(p,b,mod_poly)$
00124 
00125 
00126 /* The field operations with integers as input and output: */
00127 
00128 ss_natadd(m,n,b,mod_poly) := 
00129   poly2nat(ss_add(nat2poly(m,b), nat2poly(n,b),b,mod_poly),b)$
00130 
00131 ss_natmul(m,n,b,mod_poly) := 
00132   poly2nat(ss_mul(nat2poly(m,b), nat2poly(n,b),b,mod_poly),b)$
00133 
00134 ss_natinv(p,b,mod_poly) := 
00135   poly2nat(ss_einv(nat2poly(p,b),b,mod_poly),b)$
00136 
00137 
00138 /* The field operations with b-ary vectors (as lists) as input and output: */
00139 
00140 ss_vecadd(m,n,b) := ss_stand_vec(m+n,b)$
00141 
00142 ss_vecmul(m,n,b,e,mod_poly) := 
00143   poly2vec_ss(ss_mul(vec2poly(m), vec2poly(n),b,mod_poly),e)$
00144 
00145 ss_vecinv(p,b,e,mod_poly) :=
00146   poly2vec_ss(ss_einv(vec2poly(p),b,mod_poly),e)$
00147