OKlibrary  0.2.1.6
FiniteFields.mac
Go to the documentation of this file.
00001 /* Matthew Gwynne, 4.6.2008 (Swansea) */
00002 /* Copyright 2008, 2010, 2012 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/Algebra/Lisp/FiniteFields.mac")$
00024 oklib_include("OKlib/ComputerAlgebra/Cryptology/Lisp/Conversions.mac")$
00025 
00026 kill(f)$
00027 
00028 
00029 /* ***************************************
00030    * Finite Field Wrapper Functions      *
00031    ***************************************
00032 */
00033 
00034 okltest_egf_add(f) := block([field, element, elemSet],
00035   field : [2,1,x],
00036   assert(f(field, 0,0) = 0),
00037   assert(f(field, 1,0) = 1),
00038   assert(f(field, 0,1) = 1),
00039   assert(f(field, 1,1) = 0),
00040   field : [2,2,x^2+x+1],
00041   for i : 0 thru 3 do block([ip : int2poly(i,2)],
00042     assert(f(field, ip,0) = ip),
00043     assert(f(field, ip, ip) = 0),
00044     for j : 0 thru 3 do block([jp : int2poly(j,2)],
00045       assert(f(field,ip,jp) = f(field,jp,ip))
00046     )
00047   ),
00048   if oklib_test_level = 0 then return(true),
00049   field : [3,3,x^3+x^2+x+2],
00050   for i : 0 thru 26 do block([ip : int2poly(i,3)],
00051     assert(f(field,f(field,ip,ip),ip) = 0),
00052     for j : 0 thru 26 do block([jp : int2poly(j,3)],
00053       assert(f(field,ip,jp) = f(field,jp,ip))
00054     )
00055   ),
00056   if oklib_test_level = 1 then return(true),
00057   field : [2,8,x^8+x^4+x^3+x+1],
00058   for i : 0 thru 255 do block([ip : int2poly(i,2)],
00059     assert(f(field,ip,0) = ip),
00060     assert(f(field,ip,ip) = 0)
00061   ),
00062   assert(f(field,x^5+x^3+x+1,x^7+x^3+x^2) = x^7+x^5+x^2+x+1),
00063   assert(f(field,x^7+x^2,x^4+x^3+x^2+x+1) = x^7+x^4+x^3+x+1),
00064   assert(f(field,x^5+x^3+x+1, 1) = x^5+x^3+x),
00065   true)$
00066 
00067 okltest_egf_sub(f) := block([field, element, elemSet],
00068   field : [2,1,x],
00069   assert(f(field, 0,0) = 0),
00070   assert(f(field, 1,0) = 1),
00071   assert(f(field, 0,1) = 1),
00072   assert(f(field, 1,1) = 0),
00073   field : [2,2,x^2+x+1],
00074   for i : 0 thru 3 do block([ip : int2poly(i,2)],
00075     assert(f(field, ip,0) = ip),
00076     assert(f(field, ip, ip) = 0),
00077     for j : 0 thru 3 do block([jp : int2poly(j,2)],
00078       assert(f(field,ip,jp) = f(field,jp,ip))
00079     )
00080   ),
00081   if oklib_test_level = 0 then return(true),
00082   field : [3,3,x^3+x^2+x+2],
00083   for i : 0 thru 26 do block([ip : int2poly(i,3)],
00084     assert(f(field,ip,ip) = 0),
00085     assert(f(field,f(field,f(field,0,ip),ip),ip) = 0)
00086   ),
00087   if oklib_test_level = 1 then return(true),
00088   field : [2,8,x^8+x^4+x^3+x+1],
00089   for i : 0 thru 255 do block([ip : int2poly(i,2)],
00090     assert(f(field,ip,0) = ip),
00091     assert(f(field,ip,ip) = 0)
00092   ),
00093   assert(f(field,x^5+x^3+x+1,x^7+x^3+x^2) = x^7+x^5+x^2+x+1),
00094   assert(f(field,x^7+x^2,x^4+x^3+x^2+x+1) = x^7+x^4+x^3+x+1),
00095   assert(f(field,x^5+x^3+x+1, 1) = x^5+x^3+x),
00096   true)$
00097 
00098 okltest_egf_mul(f) := block([field, element, elemSet, elemGenerator],
00099   field : [2,1,x],
00100   assert(f(field, 0,0) = 0),
00101   assert(f(field, 1,0) = 0),
00102   assert(f(field, 0,1) = 0),
00103   assert(f(field, 1,1) = 1),
00104   field : [2,2,x^2+x+1],
00105   for i : 0 thru 3 do block([ip : int2poly(i,2)],
00106     assert(f(field, ip,0) = 0),
00107     assert(f(field, ip, 1) = ip),
00108     for j : 0 thru 3 do block([jp : int2poly(j,2)],
00109       assert(f(field,ip,jp) = f(field,jp,ip))
00110     )
00111   ),
00112   if oklib_test_level = 0 then return(true),
00113   field : [3,3,x^3+x^2+x+2],
00114   for i : 0 thru 26 do block([ip : int2poly(i,3)],
00115     assert(f(field, ip,0) = 0),
00116     for j : 0 thru 26 do block([jp : int2poly(j,3)],
00117       assert(f(field,ip,jp) = f(field,jp,ip))
00118     )
00119   ),
00120   if oklib_test_level = 1 then return(true),
00121   field : [2,8,x^8+x^4+x^3+x+1],
00122   assert(f(field,0,0) = 0),
00123   for i : 1 thru 255 do block([ip : int2poly(i,2)],
00124     assert(f(field,ip,0) = 0),
00125     assert(f(field,ip,1) = ip)
00126   ),
00127   assert(f(field,x^5+x^3+x+1, x^7+x^3+x^2) = x^7+x^5+x^4+x+1),
00128   assert(f(field,x^7+x^2, x^4+x^3+x^2+x+1) = x^6+x^5+x^2+1),
00129   assert(f(field,x^5+x^3+x+1, 1) = x^5+x^3+x+1),
00130   elemGenerator : x+1,
00131   element : 1,
00132   elemSet : {0},
00133   for i : 1 thru 255 do block(
00134     element : f(field,element,elemGenerator),
00135     elemSet : adjoin(element, elemSet)
00136   ),
00137   assert(length(elemSet) = 256),
00138   true)$
00139 
00140 okltest_egf_div(f) := block([field, element, elemSet, elemGenerator],
00141   field : [2,1,x],
00142   assert(f(field, 0,1) = 0),
00143   assert(f(field, 1,1) = 1),
00144   field : [2,2,x^2+x+1],
00145   for i : 1 thru 3 do block([ip : int2poly(i,2)],
00146     assert(f(field, 0, ip) = 0),
00147     assert(f(field, ip, 1) = ip),
00148     assert(f(field, ip, ip) = 1),
00149     assert(f(field, 1, f(field, 1, ip)) = ip)
00150   ),
00151   if oklib_test_level = 0 then return(true),
00152   field : [3,3,x^3+x^2+x+2],
00153   for i : 1 thru 26 do block([ip : int2poly(i,3)],
00154     assert(f(field, 0, ip) = 0),
00155     assert(f(field, ip, ip) = 1),
00156     assert(f(field, 1, f(field, 1, ip)) = egf_stand(field,ip))
00157   ),
00158   if oklib_test_level = 1 then return(true),
00159   field : [2,8,x^8+x^4+x^3+x+1],
00160   for i : 1 thru 255 do block([ip : int2poly(i,2)],
00161     assert(f(field, 0, ip) = 0),
00162     assert(f(field, ip, 1) = ip),
00163     assert(f(field, 1, f(field, 1, ip)) = egf_stand(field,ip))
00164   ),
00165   assert(f(field,x^5+x^3+x+1, x^7+x^3+x^2) = x^5+x^4+x),
00166   assert(f(field,x^7+x^2, x^4+x^3+x^2+x+1) = x^3+x^2),
00167   assert(f(field,x^5+x^3+x+1, 1) = x^5+x^3+x+1),
00168   elemGeneratorInv : x^7+x^6+x^5+x^4+x^2+x,
00169   element : 1,
00170   elemSet : {0},
00171   for i : 1 thru 255 do block(
00172     element : f(field,element,elemGeneratorInv),
00173     elemSet : adjoin(element, elemSet)
00174   ),
00175   assert(length(elemSet) = 256),
00176   true)$
00177 
00178 okltest_egf_inv(f) := block([field],
00179   field : [2,1,x],
00180   assert(f(field,1) = 1),
00181   field : [2,2,x^2+x+1],
00182   for i : 1 thru 3 do block([ip : int2poly(i,2)],
00183     assert(egf_mul(field,f(field,ip),ip) = 1)
00184   ),
00185   if oklib_test_level = 0 then return(true),
00186   field : [3,3,x^3+x^2+x+2],
00187   assert(f(field,1) = 1),
00188   for i : 1 thru 26 do block([ip : int2poly(i,3)],
00189     assert(egf_mul(field,f(field,ip),ip) = 1)
00190   ),
00191   if oklib_test_level = 1 then return(true),
00192   field : [2,8,x^8+x^4+x^3+x+1],
00193   assert(f(field,1) = 1),
00194   for i : 1 thru 255 do block([ip : int2poly(i,2)],
00195     assert(egf_mul(field,f(field,ip),ip) = 1)
00196   ),
00197   assert(f(field,x^6+x^5+x+1) = x^7+x^6+x^4+x+1),
00198   assert(f(field,x^7+x^5+x^4+x+1) = x^7+x^6+x^5+x^3+x^2+x+1),
00199   true)$
00200 
00201 okltest_egf_matmul(f) := block([field],
00202   field : [2,1,x],
00203   for n : 2 thru 4 do block([nMatrixIdentity, nMatrixZero],
00204     nMatrixIdentity : ident(n),
00205     nMatrixZero : zeromatrix(n,n),
00206     for m : 2 thru 4 do block([matrixElement],
00207       matrixElement : genmatrix(lambda([i,j],mod((i-1)*n+j,2)),n,m),
00208       /* MG : totaldisrep seems necessary as the matrices returned are in CRE
00209          form */
00210       assert(totaldisrep(f(field,matrixElement,ident(m))) = matrixElement),
00211       assert(totaldisrep(f(field,nMatrixIdentity,matrixElement)) = 
00212         matrixElement),
00213       assert(totaldisrep(f(field,matrixElement,zeromatrix(m,m))) = 
00214         zeromatrix(n,m)),
00215       assert(totaldisrep(f(field,nMatrixZero,matrixElement)) = zeromatrix(n,m))
00216     )
00217   ),
00218   field : [3,3,x^3+x^2+x+2],
00219   assert(totaldisrep(f(field,matrix([2*x^2+x,2,x^2+1,2*x+1,x^2+2*x+1],[x^2+2,
00220     x^2+x,2*x^2+x+2,x^2+x+2,x^2+2*x],[x^2,x,2*x^2+2*x+1,2*x+2,2*x^2+2*x],
00221     [2*x^2+2*x,x^2,x^2+x+2,x^2+2*x,2*x+2],[2*x^2+x,x^2+2*x,x^2+x,x^2+x+2,
00222     x^2+2*x]),matrix([2*x^2+1,x^2+x+1,1,x^2+x,0],[x^2+2*x+1,2*x^2+x,x^2+1,x^2+2,
00223     2*x^2+2*x],[2*x^2+x,x^2+x,x^2,2*x^2,2*x^2+x+1],[2*x^2+x+2,2,2*x^2+x+1,x+1,
00224     x+1],[x^2+1,2*x+1,0,x^2+1,2*x^2+x]))) = matrix([1,x^2,2*x^2+2*x,x^2+x,x^2+2*x+1],
00225     [2*x+2,2*x^2+1,2*x^2+1,x^2+x+2,2*x^2+2*x+1],[2*x^2+x,2*x,x^2+2*x+1,x^2+2*x,x^2],
00226     [x^2,2*x+1,2*x^2+2,x^2+2*x,2*x^2+2*x+2],[2*x^2+2,x^2+2,2*x+1,2*x^2+2*x,x^2+x+2])),
00227   if oklib_test_level = 0 then return(true),
00228   for n : 2 thru 10 do block([nMatrixIdentity, nMatrixZero],
00229     nMatrixIdentity : ident(n),
00230     nMatrixZero : zeromatrix(n,n),
00231     for m : 2 thru 10 do block(
00232      [matrixElement : genmatrix(lambda([i,j],
00233         int2poly(mod((i-1)*n+j,27),3)),n,m)],
00234       assert(totaldisrep(f(field,matrixElement,zeromatrix(m,m))) = 
00235         zeromatrix(n,m)),
00236       assert(totaldisrep(f(field,nMatrixZero,matrixElement)) = zeromatrix(n,m))
00237     )
00238   ),
00239   true)$
00240 
00241 okltest_egf_matinv(f) := block([field],
00242   field : [2,1,x],
00243   for n : 2 thru 5 do block([nMatrixIdentity],
00244     nMatrixIdentity : ident(n),
00245     matrixElement : genmatrix(lambda([i,j],if (n-j+1) = i then 1 else 0),n,n),
00246     /* MG : totaldisrep seems necessary as the matrices returned are in CRE
00247        form */
00248     assert(totaldisrep(f(field,nMatrixIdentity)) = nMatrixIdentity),
00249     assert(totaldisrep(egf_matmul(field,f(field,matrixElement),matrixElement)) 
00250       = nMatrixIdentity),
00251     assert(totaldisrep(egf_matmul(field,matrixElement,f(field,matrixElement))) 
00252       = nMatrixIdentity)
00253   ),
00254   if oklib_test_level = 0 then return(true),
00255   field : [3,3,x^3+x^2+x+2],
00256   for n : 2 thru 10 do block([nMatrixIdentity],
00257     nMatrixIdentity : ident(n),
00258     matrixElement : genmatrix(lambda([i,j],
00259       if (n-j+1) = i then int2poly(mod(i*j,27),3) else 0),n,n),
00260     /* MG : totaldisrep seems necessary as the matrices returned are in CRE
00261        form */
00262     assert(totaldisrep(f(field,nMatrixIdentity)) = nMatrixIdentity),
00263     assert(totaldisrep(egf_matmul(field,f(field,matrixElement),matrixElement)) 
00264       = nMatrixIdentity),
00265     assert(totaldisrep(egf_matmul(field,matrixElement,f(field,matrixElement))) 
00266       = nMatrixIdentity)
00267   ),
00268   true)$
00269 
00270 okltest_egf_exp(f) := block([field, elemSet],
00271   field : [2,1,x],
00272   assert(f(field, 0,0) = 1),
00273   assert(f(field, 1,0) = 1),
00274   assert(f(field, 0,1) = 0),
00275   assert(f(field, 1,1) = 1),
00276   field : [2,2,x^2+x+1],
00277   for i : 1 thru 3 do block([ip : int2poly(i,2)],
00278     assert(f(field, ip,0) = 1),
00279     assert(f(field, ip, 1) = ip),
00280     /* egf_exp is incorrect for negative exponents:
00281     assert(f(field, 1,-1) = 1),
00282     assert(f(field, ip, -1) = f(field,ip,2)),
00283     */
00284     assert(f(field, ip, 3) = 1)
00285   ),
00286   if oklib_test_level = 0 then return(true),
00287   field : [3,3,x^3+x^2+x+2],
00288   for i : 1 thru 26 do block([ip : int2poly(i,3)],
00289     assert(f(field, ip,0) = 1),
00290     assert(f(field, ip, 1) = egf_stand(field,ip)),
00291     /*assert(f(field, ip, -1) = f(field,ip,25)),*/
00292     assert(f(field, ip, 26) = 1)
00293   ),
00294   if oklib_test_level = 1 then return(true),
00295   field : [2,8,x^8+x^4+x^3+x+1],
00296   assert(f(field,0,0) = 1),
00297   for i : 1 thru 255 do block([ip : int2poly(i,2)],
00298     assert(f(field,ip,0) = 1),
00299     assert(f(field,ip,1) = ip),
00300     /*assert(f(field, ip, -1) = f(field,ip,254)),*/
00301     assert(f(field, ip, 255) = 1)
00302   ),
00303   assert(f(field,x^5+x^3+x+1, 23) = x^6+x^5+x),
00304   assert(f(field,x^7+x^2, 5) = x^4+x^3+x+1),
00305   assert(f(field,x^5+x^3+x+1, 204) = x^3+x^2),
00306   elemSet : map(lambda([a], f(field,x+1,a)), setify(create_list(i,i,0,255))),
00307   elemSet : adjoin(0, elemSet),
00308   assert(length(elemSet) = 256),
00309   true)$
00310 
00311 
00312 okltest_egf_findprim(f) := block([field],
00313   field : [2,1,x],
00314   /* assert(egf_primep(field,f(field)) = true), */
00315   field : [2,2,x^2+x+1],
00316   assert(egf_primep(field,f(field)) = true),
00317   field : [3,3,x^3+x^2+x+2],
00318   assert(egf_primep(field, f(field)) = true),
00319   field : [2,8,x^8+x^4+x^3+x+1], 
00320   assert(egf_primep(field, f(field)) = true),
00321   true)$
00322 
00323 okltest_egf_ind(f) := block([field],
00324   field : [2,1,x],
00325   assert(f(field, 1) = 0),
00326   /* XXX */
00327   true)$
00328 
00329 okltest_egf_primep(f) := (
00330   /* XXX */
00331   true)$
00332 
00333 okltest_egf_poly2num(f) := (
00334   /* XXX */
00335   true)$
00336 
00337 okltest_egf_num2poly(f) := (
00338   /* XXX */
00339   true)$
00340 
00341 okltest_egf_coeffs(f) := block([field],
00342   field : [3,3,x^3+x^2+x+2],
00343   assert(f(field,2*x^2 -x + 1,7) = [0,0,0,0,0,2,2,1]),
00344   field : [2,8,x^8+x^4+x^3+x+1], 
00345   assert(f(field, x^4+x+1,7) = [0,0,0,1,0,0,1,1]),
00346   assert(f(field, x^5+x^3+x,7) = [0,0,1,0,1,0,1,0]),
00347   true)$
00348 
00349 
00350 /* ****************************
00351    * Standard representations *
00352    ****************************
00353 */
00354 
00355 okltest_gf_stand(f) := block(
00356   gf_set(3),
00357   assert(f(0) = 0),
00358   assert(f(1) = 1),
00359   assert(f(2) = 2),
00360   assert(f(3) = 0),
00361   assert(f(5 * x) = 2*x),
00362   true)$
00363 
00364 okltest_egf_stand(f) := block([gf],
00365   gf : [3],
00366   assert(f(gf,0) = 0),
00367   assert(f(gf,1) = 1),
00368   assert(f(gf,2) = 2),
00369   assert(f(gf,3) = 0),
00370   gf : [5],
00371   assert(f(gf,2) = 2),
00372   assert(f(gf,5) = 0),
00373   true)$
00374 
00375 
00376 okltest_gf_equalp(f) := block(
00377   gf_set(3),
00378   assert(f(0,0) = true),
00379   assert(f(0,1) = false),
00380   assert(f(5,8) = true),
00381   assert(f(5,9) = false),
00382   assert(f(4*x - 7, x+2) = true),
00383   assert(f(x^2,x^2) = true),
00384   true)$
00385 
00386 okltest_egf_equalp(f) := block([gf],
00387   gf : [3],
00388   assert(f(gf,5,8) = true),
00389   gf : [5],
00390   assert(f(gf,5,8) = false),
00391   true)$
00392 
00393