OKlibrary  0.2.1.6
SmallScaleWordFields.mac
Go to the documentation of this file.
00001 /* Matthew Gwynne, 4.2.2010 (Swansea) */
00002 /* Copyright 2010 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/TestSystem/Lisp/Asserts.mac")$
00023 oklib_include("OKlib/ComputerAlgebra/Cryptology/Lisp/CryptoSystems/Rijndael/SmallScaleWordFields.mac")$
00024 oklib_include("OKlib/ComputerAlgebra/Algebra/Lisp/FiniteFields.mac")$
00025 oklib_include("OKlib/ComputerAlgebra/MaximaInternals/Auxiliary.mac")$
00026 oklib_include("OKlib/ComputerAlgebra/CombinatorialMatrices/Lisp/Basics.mac")$
00027 oklib_plain_include(eigen)$ /* (for function columnvector) */
00028 
00029 
00030 kill(f)$
00031 
00032 /* ******************
00033    * Representation *
00034    ******************
00035 */
00036 
00037 
00038 okltest_ss_stand(f) := block([x],
00039   assert(f(0,2,ss_polynomial_2_1) = 0),
00040   assert(f(1,2,ss_polynomial_2_1) = 1),
00041   assert(f(x,2,ss_polynomial_2_1) = 0),
00042   assert(f(0,2,ss_polynomial_2_4) = 0),
00043   assert(f(1,2,ss_polynomial_2_4) = 1),
00044   assert(f(x^4,2,ss_polynomial_2_4) = x+1),
00045   assert(f(ss_polynomial_2_4,2,ss_polynomial_2_4) = 0),
00046   assert(f(0,2,ss_polynomial_2_8) = 0),
00047   assert(f(1,2,ss_polynomial_2_8) = 1),
00048   assert(f(x^8,2,ss_polynomial_2_8) = x^4+x^3+x+1),
00049   assert(f(ss_polynomial_2_8,2,ss_polynomial_2_8) = 0),
00050   true)$
00051 
00052 okltest_nat2poly(f) := block([x],
00053   assert(f(0,2) = 0),
00054   assert(f(1,2) = 1),
00055   assert(f(2,2) = x),
00056   assert(f(3,2) = x+1),
00057   assert(f(4,2) = x^2),
00058   for e : 0 thru 5 do
00059     assert(f(2^e,2) = x^e),
00060   assert(f(0,3) = 0),
00061   assert(f(1,3) = 1),
00062   assert(f(2,3) = 2),
00063   assert(f(3,3) = x),
00064   assert(f(4,3) = x+1),
00065   for e : 0 thru 5 do
00066     assert(f(3^e,3) = x^e),
00067   true)$
00068 
00069 okltest_poly2nat(f) := block([x],
00070   assert(f(0,2) = 0),
00071   assert(f(1,2) = 1),
00072   assert(f(x,2) = 2),
00073   assert(f(x+1,2) = 3),
00074   assert(f(x^2,2) = 4),
00075   for e : 0 thru 5 do
00076     assert(f(x^e,2) = 2^e),
00077   assert(f(0,3) = 0),
00078   assert(f(1,3) = 1),
00079   assert(f(2,3) = 2),
00080   assert(f(x,3) = 3),
00081   assert(f(x+1,3) = 4),
00082   for e : 0 thru 5 do
00083     assert(f(x^e,3) = 3^e),
00084   true)$
00085 
00086 okltest_ss_stand_vec(f) := (
00087   assert(f([],2) = []),
00088   assert(f([0],2) = [0]),
00089   assert(f([1],2) = [1]),
00090   assert(f([1,0,0,0,0,1,1],2) = [1,0,0,0,0,1,1]),
00091   assert(f([2],2) = [0]),
00092   assert(f([3],2) = [1]),
00093   assert(f([3,1,1,1,2],2) = [1,1,1,1,0]),
00094   assert(f([],3) = []),
00095   assert(f([0],3) = [0]),
00096   assert(f([1],3) = [1]),
00097   assert(f([1,0,0,0,0,1,1],3) = [1,0,0,0,0,1,1]),
00098   assert(f([3],3) = [0]),
00099   assert(f([4],3) = [1]),
00100   assert(f([4,1,1,1,3],3) = [1,1,1,1,0]),
00101   true)$
00102 
00103 okltest_nat2vec(f) := (
00104   assert(f(0,2) = [0]),
00105   assert(f(1,2) = [1]),
00106   assert(f(2,2) = [1,0]),
00107   assert(f(3,2) = [1,1]),
00108   assert(f(4,2) = [1,0,0]),
00109   for e : 0 thru 10 do
00110     assert(f(2^e,2) = cons(1,create_list(0,i,1,e))),
00111   assert(f(0,3) = [0]),
00112   assert(f(1,3) = [1]),
00113   assert(f(2,3) = [2]),
00114   assert(f(3,3) = [1,0]),
00115   assert(f(4,3) = [1,1]),
00116   assert(f(5,3) = [1,2]),
00117   assert(f(6,3) = [2,0]),
00118   assert(f(9,3) = [1,0,0]),
00119   for e : 0 thru 10 do
00120     assert(f(3^e,3) = cons(1,create_list(0,i,1,e))),
00121   true)$
00122 
00123 okltest_nat2vec_ss(f) := (
00124   assert(f(0,2,8) = [0,0,0,0,0,0,0,0]),
00125   assert(f(1,2,8) = [0,0,0,0,0,0,0,1]),
00126   assert(f(2,2,8) = [0,0,0,0,0,0,1,0]),
00127   assert(f(3,2,8) = [0,0,0,0,0,0,1,1]),
00128   assert(f(4,2,8) = [0,0,0,0,0,1,0,0]),
00129   for e : 0 thru 7 do
00130     assert(f(2^e,2,8) = create_list(if i = 8 - e then 1 else 0, i, 1, 8)),
00131   assert(f(0,3,8) = [0,0,0,0,0,0,0,0]),
00132   assert(f(1,3,8) = [0,0,0,0,0,0,0,1]),
00133   assert(f(2,3,8) = [0,0,0,0,0,0,0,2]),
00134   assert(f(3,3,8) = [0,0,0,0,0,0,1,0]),
00135   assert(f(4,3,8) = [0,0,0,0,0,0,1,1]),
00136   for e : 0 thru 7 do
00137     assert(f(3^e,3,8) = create_list(if i = 8 - e then 1 else 0, i, 1, 8)),
00138   true)$
00139 
00140 okltest_vec2nat(f) := (
00141   assert(f([0],2) = 0),
00142   assert(f([1],2) = 1),
00143   assert(f([1,0],2) = 2),
00144   assert(f([1,1],2) = 3),
00145   assert(f([1,0,0],2) = 4),
00146   for e : 0 thru 10 do
00147     assert(f(cons(1,create_list(0,i,1,e)),2) = 2^e),
00148   assert(f([0],3) = 0),
00149   assert(f([1],3) = 1),
00150   assert(f([2],3) = 2),
00151   assert(f([1,0],3) = 3),
00152   assert(f([1,1],3) = 4),
00153   assert(f([1,0,0],3) = 9),
00154   for e : 0 thru 10 do
00155     assert(f(cons(1,create_list(0,i,1,e)),3) = 3^e),
00156   true)$
00157 
00158 okltest_poly2vec(f) := (
00159   assert(f(0) = [0]),
00160   assert(f(1) = [1]),
00161   assert(f(x) = [1,0]),
00162   assert(f(x+1) = [1,1]),
00163   assert(f(x^2) = [1,0,0]),
00164   for e : 0 thru 10 do
00165     assert(f(x^e) = cons(1,create_list(0,i,1,e))),
00166   assert(f(2*x^2) = [2,0,0]),
00167   true)$
00168 
00169 okltest_poly2mvec(f) := (
00170   assert(okltest_poly2vec(buildq([f], lambda([a],column_m(f(a),1))))),
00171   true)$
00172 
00173 okltest_poly2vec_ss(f) := (
00174   assert(f(0,8) = [0,0,0,0,0,0,0,0]),
00175   assert(f(1,8) = [0,0,0,0,0,0,0,1]),
00176   assert(f(x,8) = [0,0,0,0,0,0,1,0]),
00177   assert(f(x+1,8) = [0,0,0,0,0,0,1,1]),
00178   assert(f(x^2,8) = [0,0,0,0,0,1,0,0]),
00179   for e : 0 thru 7 do
00180     assert(f(x^e,8) = create_list(if i = 8 - e then 1 else 0, i, 1, 8)),
00181   assert(f(2*x^2,8) = [0,0,0,0,0,2,0,0]),
00182   true)$
00183 
00184 okltest_poly2mvec_ss(f) := (
00185   assert(okltest_poly2vec_ss(buildq([f], lambda([a,e],column_m(f(a,e),1))))),
00186   true)$
00187 
00188 okltest_vec2poly(f) := (
00189   assert(f([0]) = 0),
00190   assert(f([1]) = 1),
00191   assert(f([1,0]) = x),
00192   assert(f([1,1]) = x+1),
00193   assert(f([1,0,0]) = x^2),
00194   for e : 0 thru 10 do
00195     assert(f(cons(1,create_list(0,i,1,e))) = x^e),
00196   assert(f([2,0,0]) = 2*x^2),
00197   true)$
00198 
00199 okltest_mvec2poly(f) := (
00200   assert(okltest_vec2poly(buildq([f], lambda([a],f(columnvector(a)))))),
00201   true)$
00202 
00203 
00204 /* **************
00205    * Operations *
00206    **************
00207 */
00208 
00209 okltest_ss_add(f) := block([x],
00210   assert(f(0,0,2,ss_polynomial_2_8) = 0),
00211   assert(f(x,x,2,ss_polynomial_2_8) = 0),
00212   assert(f(x,x^4+x^2+x+3,2,ss_polynomial_2_8) = x^4+x^2+1),
00213   true)$
00214 
00215 okltest_ss_mul(f) := block([x],
00216   assert(f(0,0,2,ss_polynomial_2_8) = 0),
00217   assert(f(0,x^2,2,ss_polynomial_2_8) = 0),
00218   assert(f(1,x^3+x^2+3,2,ss_polynomial_2_8) = x^3+x^2+1),
00219   assert(f(x^4,x^4,2,ss_polynomial_2_8) = x^4+x^3+x+1),
00220   assert(f(ss_polynomial_2_8-1,ss_polynomial_2_8-1,2,ss_polynomial_2_8) = 1),
00221   true)$
00222 
00223 okltest_ss_matmul(f) := block([x],
00224   assert(f(matrix(),matrix(),2,ss_polynomial_2_8) = matrix()),
00225   assert(f(matrix([0]),matrix([0]),2,ss_polynomial_2_8) = matrix([0])),
00226   assert(f(matrix([x,0],[0,x]),matrix([x,0],[0,x]),2,ss_polynomial_2_8) = matrix([x^2,0],[0,x^2])),
00227   assert(f(matrix([x,1],[x,x^2]),matrix([1,x^3],[x,0]),2,ss_polynomial_2_8) = matrix([0,x^4],[x^3+x,x^4])),
00228   assert(f(matrix([x^4,0],[0,x^4]),matrix([x^4,0],[0,x^4]),2,ss_polynomial_2_8) = matrix([x^4+x^3+x+1,0],[0,x^4+x^3+x+1])),
00229   true)$
00230 
00231 okltest_ss_inv(f) := block([x],
00232   assert(f(1,2,ss_polynomial_2_8) = 1),
00233   assert(f(x,2,ss_polynomial_2_8) = x^7+x^3+x^2+1),
00234   assert(tcre_p(f(x+x^2,2,ss_polynomial_2_8)) = false),
00235   true)$
00236 
00237 okltest_ss_einv(f) := (
00238   assert(f(0,2,ss_polynomial_2_8) = 0),
00239   assert(okltest_ss_inv(f) = true),
00240   true)$
00241 
00242 okltest_ss_natadd(f) := (
00243   assert(f(0,0,2,ss_polynomial_2_8) = 0),
00244   assert(okltest_ss_add(buildq([f],
00245         lambda([m,n,b,mod_poly],
00246           nat2poly(f(poly2nat(ss_stand(m,b,mod_poly),b),
00247               poly2nat(ss_stand(n,b,mod_poly),b),b,mod_poly),b)))) = true),
00248   true)$
00249 
00250 okltest_ss_natmul(f) := (
00251   assert(f(0,0,2,ss_polynomial_2_8) = 0),
00252   assert(f(0,1,2,ss_polynomial_2_8) = 0),
00253   assert(f(1,1,2,ss_polynomial_2_8) = 1),
00254   assert(f(2,141,2,ss_polynomial_2_8) = 1),
00255   true)$
00256 
00257 okltest_ss_natinv(f) := (
00258   assert(f(0,2,ss_polynomial_2_8) = 0),
00259   assert(f(1,2,ss_polynomial_2_8) = 1),
00260   assert(f(2,2,ss_polynomial_2_8) = 141),
00261   assert(f(poly2nat(ss_stand(-1,2,ss_polynomial_2_8),2),2,ss_polynomial_2_8) = poly2nat(ss_stand(-1,2,ss_polynomial_2_8),2)),
00262   true)$
00263 
00264 okltest_ss_vecadd(f) := (
00265   assert(f([0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0],2) = [0,0,0,0,0,0,0,0]),
00266   for i : 0 thru 7 do
00267     assert(f(nat2vec_ss(2^i,2,8),nat2vec_ss(0,2,8),2) = nat2vec_ss(2^i,2,8)),
00268   for i : 0 thru 7 do
00269     assert(f(nat2vec_ss(2^i,2,8),nat2vec_ss(2^i,2,8),2) = nat2vec_ss(0,2,8)),
00270   assert(f([1,0,1,1,0,1,0,0], [1,1,1,1,1,1,1,1],2) = [0,1,0,0,1,0,1,1]),
00271   true)$
00272 
00273 okltest_ss_vecmul(f) := (
00274   assert(f([0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0],2,8,ss_polynomial_2_8) = [0,0,0,0,0,0,0,0]),
00275   assert(f([0,0,0,0,0,0,0,1], [0,0,0,0,0,0,0,1],2,8,ss_polynomial_2_8) = [0,0,0,0,0,0,0,1]),
00276   for i : 0 thru 7 do
00277     assert(f(nat2vec_ss(2^i,2,8),nat2vec_ss(0,2,8),2,8,ss_polynomial_2_8) = nat2vec_ss(0,2,8)),
00278   for i : 0 thru 6 do
00279     assert(f(nat2vec_ss(2^i,2,8),nat2vec_ss(2,2,8),2,8,ss_polynomial_2_8) = nat2vec_ss(2^(i+1),2,8)),
00280   for i : 0 thru 3 do
00281     assert(f(nat2vec_ss(2^i,2,8),nat2vec_ss(2^i,2,8),2,8,ss_polynomial_2_8) = nat2vec_ss(2^(2*i),2,8)),
00282   assert(f(nat2vec_ss(2^7,2,8),nat2vec_ss(2,2,8),2,8,ss_polynomial_2_8) = [0,0,0,1,1,0,1,1]),
00283   assert(f(nat2vec_ss(2^4,2,8),nat2vec_ss(2^4,2,8),2,8,ss_polynomial_2_8) = [0,0,0,1,1,0,1,1]),
00284   assert(f(nat2vec_ss(2^7,2,8), nat2vec_ss(2^7,2,8),2,8,ss_polynomial_2_8) = [1,0,0,1,1,0,1,0]),
00285   assert(f(nat2vec_ss(56,2,8), nat2vec_ss(32,2,8),2,8,ss_polynomial_2_8) = [0,1,0,0,0,0,0,1]),
00286   true)$
00287 
00288 okltest_ss_vecinv(f) := (
00289   assert(f([0],2,8,ss_polynomial_2_8) = [0,0,0,0,0,0,0,0]),
00290   assert(f([1],2,8,ss_polynomial_2_8) = [0,0,0,0,0,0,0,1]),
00291   assert(f([0,0,0,0,0,1,0,1],2,8,ss_polynomial_2_8) = [0,1,0,1,0,0,1,0]),
00292   assert(okltest_ss_inv(
00293       buildq([f], lambda([p,b,mod_poly], block([max_coeff : hipow(mod_poly,x)],
00294           vec2poly(f(poly2vec_ss(p,max_coeff),b,max_coeff,mod_poly))))))),
00295   /* XXX */
00296   true)$
00297 
00298