OKlibrary  0.2.1.6
FieldOperationsAnalysis.mac
Go to the documentation of this file.
00001 /* Matthew Gwynne, 26.4.2008 (Swansea) */
00002 /* Copyright 2008, 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 
00057 oklib_include("OKlib/ComputerAlgebra/TestSystem/Lisp/Asserts.mac")$
00058 oklib_include("OKlib/ComputerAlgebra/Hypergraphs/Lisp/SetSystems.mac")$
00059 oklib_include("OKlib/ComputerAlgebra/DataStructures/Lisp/Lists.mac")$
00060 
00061 kill(f)$
00062 
00063 
00064 /* ************************************************************
00065    * General small scale field analysis                       *
00066    ************************************************************
00067 */
00068 
00069 okltest_ss_field_op_fulldnf_gen_fcl(f) := block(
00070   assert(okltest_ssmult_fulldnf_fcl(buildq([f],
00071         lambda([a,b,e,mod_poly],
00072           f(lambda([ap],ss_mul(nat2poly(a,b),ap,b,mod_poly)), b,e))))),    
00073   true)$
00074 
00075 okltest_ss_field_op_fullcnf_gen_fcs(f) := block(
00076   assert(okltest_ssmult_fullcnf_fcs(buildq([f],
00077         lambda([a,b,e,mod_poly],
00078           f(lambda([ap],ss_mul(nat2poly(a,b),ap,b,mod_poly)), b,e))))),    
00079   true)$
00080 
00081 okltest_ss_field_op_gen_cnfp(f) := block(
00082   assert(okltest_ssmult_gen_cnfp(buildq([f],
00083         lambda([a,FF,b,e,mod_poly],
00084           f(FF,lambda([ap],ss_mul(nat2poly(a,b),ap,b,mod_poly)), b,e))))),    
00085   true)$
00086 
00087 
00088 /* ******************************************
00089    * Field Multiplication Analysis          *
00090    ******************************************
00091 */
00092 
00093 okltest_rijnmult_fulldnf_fcs(f) := block(
00094   [mulFullDNF,inputList,outputList],
00095   if oklib_test_level = 0 then return(true),
00096   mulFullDNF : f(2),
00097   assert(length(mulFullDNF[2]) = 256),
00098   assert(length(mulFullDNF[1]) = 16),
00099   assert(elementp({-16,-15,-14,-13,-12,-11,-10,-9,-8,-7,-6,-5,-4,-3,-2,-1},
00100       mulFullDNF[2])),
00101   assert(elementp({-16,-15,-14,-13,-12,-11,-10,-8,-7,-6,-5,-4,-3,-1,2,9},
00102      mulFullDNF[2])),
00103   assert(elementp({-14,-13,-12,-9,-8,-7,-2,1,3,4,5,6,10,11,15,16},
00104      mulFullDNF[2])),
00105   assert(elementp({-15,-13,-12,-11,-9,-4,-2,1,3,5,6,7,8,10,14,16},
00106      mulFullDNF[2])),
00107   mulFullDNF : f(10),
00108   assert(length(mulFullDNF[2]) = 256),
00109   assert(length(mulFullDNF[1]) = 16),
00110   assert(elementp({-16,-15,-14,-13,-12,-11,-10,-9,-8,-7,-6,-5,-4,-3,-2,-1},
00111       mulFullDNF[2])),
00112   assert(elementp({-16,-14,-10,-9,-8,-7,-6,-5,1,2,3,4,11,12,13,15},
00113      mulFullDNF[2])),
00114   assert(elementp({-13,-11,-9,-5,-3,1,2,4,6,7,8,10,12,14,15,16},
00115      mulFullDNF[2])),
00116   assert(elementp({-12,-9,-7,-5,-1,2,3,4,6,8,10,11,13,14,15,16},
00117      mulFullDNF[2])),
00118   mulFullDNF : f(167),
00119   assert(length(mulFullDNF[2]) = 256),
00120   assert(length(mulFullDNF[1]) = 16),
00121   assert(elementp({-16,-15,-14,-13,-12,-11,-10,-9,-8,-7,-6,-5,-4,-3,-2,-1},
00122       mulFullDNF[2])),
00123   assert(elementp({-12,-10,-9,-8,-5,-3,-1,2,4,6,7,11,13,14,15,16},
00124      mulFullDNF[2])),
00125   assert(elementp({-13,-12,-11,-10,-9,-6,-5,-4,1,2,3,7,8,14,15,16},
00126      mulFullDNF[2])),
00127   assert(elementp({-16,-15,-14,-13,-10,-8,-4,-3,-2,-1,5,6,7,9,11,12},
00128      mulFullDNF[2])),
00129   true)$
00130 
00131 
00132 okltest_rijnmult_fullcnf_fcs(f) := block([FF],
00133   if oklib_test_level = 0 then return(true),
00134   FF : f(2),
00135   assert(length(FF[2]) = 2^16 - 256),
00136   assert(elementp({-6,-5,-3,-1,2,4,7,8,9,10,11,12,13,14,15,16},
00137     FF[2])),
00138   assert(elementp({-16,-15,-14,-13,-12,-11,-10,-9,-8,-7,-6,-5,-4,-2,-1,3},
00139     FF[2])),
00140   assert(elementp({-16,-15,-14,-12,-11,-7,-6,-3,1,2,4,5,8,9,10,13},
00141     FF[2])),
00142   true)$
00143 
00144 okltest_rijnmult_cnfp(f) := block(
00145   if oklib_test_level = 0 then return(true),
00146   assert(f(1, [setn(16), lunion(create_list({{-i,i+8},{-(i+8),i}}, i,1,8))]) = true),
00147   assert(f(2,[{},{}]) = false),
00148   assert(f(3,[{},{}]) = false),
00149   assert(f(2,[setn(16),{{1,2},{4,-5,6},{-16}}]) = false),
00150   assert(f(3,[setn(16),{{1,2},{4,-5,6},{-16}}]) = false),
00151   if oklib_test_level = 1 then return(true),
00152   assert(f(2,rijnmult_fullcnf_fcs(2)) = true),
00153   true)$
00154 
00155 /* *********************************************
00156    * Small Scale Field multiplication analysis *
00157    *********************************************
00158 */
00159 
00160 okltest_ssmult_fulldnf_fcl(f) := block(
00161   assert(f(1,2,1,ss_polynomial_2_1) = [[1,2],[{-2,-1},{1,2}]]),
00162   assert(f(4,2,4,ss_polynomial_2_4) =
00163     [[1,2,3,4,5,6,7,8],
00164     [{-8,-7,-6,-5,-4,-3,-2,-1},{-8,-7,-5,-3,-2,-1,4,6},{-8,-7,-6,-4,-2,-1,3,5},
00165      {-8,-7,-2,-1,3,4,5,6},{-6,-5,-4,-3,-1,2,7,8},{-5,-3,-1,2,4,6,7,8},
00166      {-6,-4,-1,2,3,5,7,8},{-1,2,3,4,5,6,7,8},{-8,-5,-4,-3,-2,1,6,7},
00167      {-8,-6,-5,-3,-2,1,4,7},{-8,-4,-2,1,3,5,6,7},{-8,-6,-2,1,3,4,5,7},
00168      {-7,-5,-4,-3,1,2,6,8},{-7,-6,-5,-3,1,2,4,8},{-7,-4,1,2,3,5,6,8},
00169      {-7,-6,1,2,3,4,5,8}]]),
00170   if oklib_test_level = 0 then return(true),
00171   assert(f(3,2,8,ss_polynomial_2_8) = rijnmult_fulldnf_fcl(3)),
00172   true)$
00173 
00174 okltest_ssmult_fullcnf_fcs(f) := block(
00175   assert(f(1,2,1,ss_polynomial_2_1) = [{1,2},{{-2,1},{-1,2}}]),
00176   if oklib_test_level = 0 then return(true),
00177   assert(f(3,2,8,ss_polynomial_2_8) = rijnmult_fullcnf_fcs(3)),
00178   true)$
00179 
00180 okltest_ssmult_gen_cnfp(f) := block(
00181   assert(f(1, [{1,2},{{-2,1},{-1,2}}],2,1,ss_polynomial_2_1)),
00182   assert(not(f(1,[{1,2},{{-2,1},{1,2}}],2,1,ss_polynomial_2_1))),
00183   if oklib_test_level = 0 then return(true),
00184   assert(f(3,rijnmult_fullcnf_fcs(3),2,8,ss_polynomial_2_8)),
00185   true)$
00186 
00187 
00188 /* *********************************************
00189    * Small Scale Field multiplication analysis *
00190    *********************************************
00191 */
00192 
00193 okltest_ssinv_fulldnf_fcl(f) := block(
00194   assert(f(2,1,ss_polynomial_2_1) = [[1,2],[{-2,-1},{1,2}]]),
00195   assert(f(2,4,ss_polynomial_2_4) =
00196     [[1,2,3,4,5,6,7,8],
00197      [{-8,-7,-6,-5,-4,-3,-2,-1},{-7,-6,-5,-3,-2,-1,4,8},
00198       {-7,-6,-4,-2,-1,3,5,8},{-8,-2,-1,3,4,5,6,7},{-7,-4,-3,-1,2,5,6,8},
00199       {-6,-3,-1,2,4,5,7,8},{-5,-4,-1,2,3,6,7,8},{-8,-5,-1,2,3,4,6,7},
00200       {-4,-3,-2,1,5,6,7,8},{-8,-6,-5,-3,-2,1,4,7},{-8,-7,-4,-2,1,3,5,6},
00201       {-7,-5,-2,1,3,4,6,8},{-8,-6,-4,-3,1,2,5,7},{-8,-7,-5,-3,1,2,4,6},
00202       {-6,-5,-4,1,2,3,7,8},{-8,-7,-6,1,2,3,4,5}]]),
00203   true)$
00204 
00205 okltest_ssinv_fullcnf_fcs(f) := block(
00206   assert(f(2,1,ss_polynomial_2_1) = [{1,2},{{-2,1},{-1,2}}]),
00207   assert(elementp({-8,-7,-6,-5,-4,-3,-2,-1},
00208       f(2,4,ss_polynomial_2_4)[2])),
00209   true)$
00210 
00211 okltest_ssinv_cnfp(f) := block(
00212   assert(f([{1,2},{{-2,1},{-1,2}}],2,1,ss_polynomial_2_1)),
00213   assert(not(f([{1,2},{{-2,1},{1,2}}],2,1,ss_polynomial_2_1))),
00214   true)$
00215 
00216 /* ******************************************
00217    * Representations by hitting clause-sets *
00218    ******************************************
00219 */
00220 
00221 okltest_rijnmult2hittingcnf_fcs(f) := block([FF],
00222   if oklib_test_level = 0 then return(true),
00223   FF : f(2,dll_heuristics_first_formal),
00224   assert(hittingcsp(FF[2])),
00225   if oklib_test_level = 1 then return(true),
00226   assert(rijnmult_cnfp(2,cs_to_fcs(FF))),
00227   true)$
00228