From: Volker v. N. <va...@us...> - 2013-03-14 20:43:39
|
This is an automated email from the git hooks/post-receive script. It was generated because a ref change was pushed to the repository containing the project "Maxima CAS". The branch, master has been updated via 9dc000acc86246fe2cd00be1e3588fadb67682f3 (commit) from f47f4fe27e99800c6fa8f03e12a9425f8ce99c2a (commit) Those revisions listed above that are new to this repository have not appeared on any other notification email; so we list those revisions in full, below. - Log ----------------------------------------------------------------- commit 9dc000acc86246fe2cd00be1e3588fadb67682f3 Author: Volker van Nek <vol...@gm...> Date: Thu Mar 14 21:43:10 2013 +0100 renaming gf_set to gf_set_data diff --git a/share/contrib/gf/aes.mac b/share/contrib/gf/aes.mac index afeeddd..50c0f35 100644 --- a/share/contrib/gf/aes.mac +++ b/share/contrib/gf/aes.mac @@ -74,8 +74,6 @@ for byte:0 thru 255 do %_inv_byte_sub[byte]$ inv_sub_bytes(state) := matrixmap(lambda([byte], %_inv_byte_sub[byte]), state)$ -gf_set(2, x^8+x^4+x^3+x+1)$ - /* shift_rows *************************************************************** */ @@ -93,6 +91,8 @@ inv_shift_rows(M) := apply('matrix, makelist(inv_rotate(M[i], i-1), i,1,4))$ /* mix_columns ************************************************************** */ +gf_set_data(2, x^8+x^4+x^3+x+1)$ + mat_n2p(num_mat) := matrixmap('gf_n2p, num_mat)$ mat_p2n(poly_mat) := matrixmap('gf_p2n, poly_mat)$ diff --git a/share/contrib/gf/aes2.mac b/share/contrib/gf/aes2.mac index 68072f1..9fe041e 100644 --- a/share/contrib/gf/aes2.mac +++ b/share/contrib/gf/aes2.mac @@ -39,7 +39,7 @@ /* GF arithmetic by lookup tables ******************************************* */ -gf_set(2, x^8+x^4+x^3+x+1)$ +gf_set_data(2, x^8+x^4+x^3+x+1)$ gf_make_arrays()$ diff --git a/share/contrib/gf/gf_manual.pdf b/share/contrib/gf/gf_manual.pdf index 3718e27..89e9a2d 100644 Binary files a/share/contrib/gf/gf_manual.pdf and b/share/contrib/gf/gf_manual.pdf differ diff --git a/share/contrib/gf/gf_manual.tex b/share/contrib/gf/gf_manual.tex index c40b46c..52849d9 100644 --- a/share/contrib/gf/gf_manual.tex +++ b/share/contrib/gf/gf_manual.tex @@ -47,7 +47,7 @@ \end{tabular} } -\date{April, 2008 - December, 2012} +\date{April, 2008 - March, 2013} \begin{document} \maketitle @@ -64,7 +64,7 @@ and optimizations implemented by Fabrizio Caruso and Jacopo D'Aurizio. A full review was done in 2012 by Volker van Nek. Most of the functions described below became core functions and some function names have been modified. -If you use a version of Maxima prior to 5.29 please refer to an appropriate +If you use a version of Maxima prior to 5.30 please refer to an appropriate version of this file or alternatively load the necessary files from current sources. These are \texttt{src/numth.lisp} (all basic Galois Fields functions) and \texttt{share/contrib/gf/gf.mac} (square and cubic roots). @@ -110,8 +110,8 @@ In these fields, addition and subtraction are performed on the coefficients modulo $p$, and multiplication and division modulo $m(x)$. Given a prime number $p$ and a polynomial $m(x)$ -you can create a field by using the command ``\verb!gf_set(p, m(x))!''. -\verb!gf_set! checks that $p$ is prime, and it also checks +you can create a field by using the command ``\verb!gf_set_data(p, m(x))!''. +\verb!gf_set_data! checks that $p$ is prime, and it also checks whether $m(x)$ is irreducible. If these conditions are met, a primitive element in this field will be computed. Maxima then returns a structure containing the fields data which is @@ -119,24 +119,24 @@ suitable for later use by ``\verb!gf_set_again(gf_data)!'' if needed again. %\begin{maximasession} % \maximaoutput* -% \i1. gf_set(2, x^4+x+1);\\ +% \i1. gf_set_data(2, x^4+x+1);\\ % \o1. [x, x^4+x+1]\\ %\end{maximasession} % \vspace*{2mm} \begin{lstlisting}[escapechar=\#] - #\tr{(\%i1)}# gf_set(2, x^4+x+1); + #\tr{(\%i1)}# gf_set_data(2, x^4+x+1); #\tr{(\%o1)}\bc\rb{$\tb{gf\_data(characteristic = 2, exponent = 4, reduction = x^4+x+1,}$}\ec# #\bc\rb{$\tb{primitive = x, cardinality = 16, order = 15, factors\_of\_order = [\,[\,3, 1\,], [\,5, 1\,]\,])}$}\ec# \end{lstlisting} In case there is no polynomial $m(x)$ irreducible over $\mathbb{F}_p$ available -a field can be created by ``\verb!gf_set(p, n)!''. +a field can be created by ``\verb!gf_set_data(p, n)!''. A suitable $m(x)$ will be computed and returned along with a primitive element. -E.g. ``\verb!gf_set(2, 4)!'' returns the same as ``\verb!gf_set(2, x^4+x+1)!''. +E.g. ``\verb!gf_set_data(2, 4)!'' returns the same as ``\verb!gf_set_data(2, x^4+x+1)!''. -In addition to \verb!gf_set! there is a command ``\verb!gf_minimal_set(p, m(x))!'' +In addition to \verb!gf_set_data! there is a command ``\verb!gf_minimal_set(p, m(x))!'' to allow basic arithmetics without checking irreducibility and without computing a primitive element. @@ -442,7 +442,7 @@ First, Alice must compute her public key: \vspace*{2mm} \begin{lstlisting}[escapechar=\#] - #\tr{(\%i35)}# gf_set(7, x^4+3*x^3+5*x^2+6*x+2)#\$# + #\tr{(\%i35)}# gf_set_data(7, x^4+3*x^3+5*x^2+6*x+2)#\$# #\tr{(\%i36)}# g : 3*x^3+3*x^2+6#\$# #\tr{(\%i37)}# gf_primitive_p(g); #\tr{(\%o37)}\bc\rb{$\tb{true}$}\ec# @@ -517,7 +517,7 @@ Although this is a probabilistic algorithm, in practice it works very quickly: \vspace*{2mm} \begin{lstlisting}[escapechar=\#] - #\tr{(\%i49)}# gf_set(2, x^10+x^3+1)#\$# + #\tr{(\%i49)}# gf_set_data(2, x^10+x^3+1)#\$# #\tr{(\%i50)}# p : gf_random_normal(); #\tr{(\%o50)}\bc\rb{$\tb{x^9+x^7+x^6+x^5+x^2+x+1}$}\ec# \end{lstlisting} @@ -565,7 +565,7 @@ Pohlig-Hellman reduction and Brent's version of Pollard Rho. \vspace*{2mm} \begin{lstlisting}[escapechar=\#] - #\tr{(\%i55)}# gf_set(2, x^20+x^3+1); + #\tr{(\%i55)}# gf_set_data(2, x^20+x^3+1); #\tr{(\%o55)}\bc\rb{$\tb{gf\_data(characteristic = 2, exponent = 20, reduction = x^{20}+x^3+1, }$}\ec# #\bc\rb{$\tb{primitive = x, cardinality = 1048576, order = 1048575, }$}\ec# #\bc\rb{$\tb{factors\_of\_order = [\,[3, 1], [5, 2], [11, 1], [31, 1], [41, 1]\,]) }$}\ec# diff --git a/tests/rtest_numth.mac b/tests/rtest_numth.mac index 2c13c52..10a4599 100644 --- a/tests/rtest_numth.mac +++ b/tests/rtest_numth.mac @@ -78,10 +78,10 @@ chinese(rems, mods); /* Tests adapted from contrib/gf/gf_test.mac */ -gf_set(123127, 5, x^5+2*x+1); +gf_set_data(123127, 5, x^5+2*x+1); gf_data(123127,5,x^5+2*x+1,x+4,28298700309333316062584407,28298700309333316062584406,[[2,1],[3,1],[11,1],[20521,1],[939391,1],[22242194743981,1]]); -gf_set(7, 10, x^10+5*x^2+x+5); +gf_set_data(7, 10, x^10+5*x^2+x+5); gf_data(7,10,x^10+5*x^2+x+5,x,282475249,282475248,[[2,4],[3,1],[11,1],[191,1],[2801,1]]); gf_exp(gf_primitive(), gf_index(x^9+3*x^6+x^5+2*x^2+6)); @@ -90,25 +90,25 @@ x^9+3*x^6+x^5+2*x^2+6; gf_minimal_poly(x^9+3*x^6+x^5+2*x^2+6); z^10+5*z^9+6*z^8+5*z^6+3*z^5+4*z^4+z^3+2*z^2+4*z+3; -gf_set(19); +gf_set_data(19); gf_data(19,1,x,2,19,18,[[2,1],[3,2]]); gf_exp(gf_primitive(), gf_index(17)); 17; -gf_set(10000000019); +gf_set_data(10000000019); gf_data(10000000019,1,x,2,10000000019,10000000018,[[2,1],[131,1],[521,1],[73259,1]]); gf_exp(gf_primitive() ,gf_index(3)); 3; -gf_set(32717, 11, x^11+x^5+x^2+x+1); +gf_set_data(32717, 11, x^11+x^5+x^2+x+1); gf_data(32717,11,x^11+x^5+x^2+x+1,x+2,45973568360012658888852552517205008541393124962933,45973568360012658888852552517205008541393124962932,[[2,2],[8179,1],[20857,1],[137992422569,1],[306802352539,1],[1591410608478398621,1]]); -gf_set(211, 17, x^17+2*x^2+1); +gf_set_data(211, 17, x^17+2*x^2+1); gf_data(211,17,x^17+2*x^2+1,x+6,3256879871129217157345956711624826081171,3256879871129217157345956711624826081170,[[2,1],[3,1],[5,1],[7,1],[137,1],[239,1],[473657018821793557815477348357239,1]]); -gf_set(2, 20, x^20+x^3+x^2+x+1); +gf_set_data(2, 20, x^20+x^3+x^2+x+1); gf_data(2,20,x^20+x^3+x^2+x+1,x^2+x,1048576,1048575,[[3,1],[5,2],[11,1],[31,1],[41,1]]); gf_exp(gf_primitive(), gf_index(x^10+1)); @@ -117,33 +117,33 @@ x^10+1; gf_minimal_poly(x^10+1); z^20+z^13+z^12+z^5+z^4+z^3+1; -gf_set(3, 91, x^91+x^35+x+1); +gf_set_data(3, 91, x^91+x^35+x+1); gf_data(3,91,x^91+x^35+x+1,x,26183890704263137277674192438430182020124347,26183890704263137277674192438430182020124346,[[2,1],[1093,1],[797161,1],[4011586307,1],[3745603812007166116831643,1]]); /* Tests adapted from contrib/gf/gf_hard_test.mac */ -gf_set(7, 61, x^61+x^4+1); +gf_set_data(7, 61, x^61+x^4+1); gf_data(7,61,x^61+x^4+1,x+3,3556153025177363557255317383565515512407041673852007,3556153025177363557255317383565515512407041673852006,[[2,1],[3,1],[367,1],[4759,1],[177237331,1],[1914662449813727660680530326064591907,1]]); -gf_set(197, 24, x^24-x^8+2); +gf_set_data(197, 24, x^24-x^8+2); gf_data(197,24,x^24+196*x^8+2,x+19,11673186598630578538556565100133681446610566511878526881,11673186598630578538556565100133681446610566511878526880,[[2,5],[3,3],[5,1],[7,2],[11,1],[13,1],[19,1],[61,1],[73,1],[211,1],[2053,1],[3217,1],[3881,1],[36013,1],[728809,1],[750457,1],[4147537,1],[10316017,1]]); -gf_set(5, 84, x^84+x^41+x^2+1); +gf_set_data(5, 84, x^84+x^41+x^2+1); gf_data(5,84,x^84+x^41+x^2+1,x^2+1,51698788284564229679463043254372678347863256931304931640625,51698788284564229679463043254372678347863256931304931640624,[[2,4],[3,2],[7,2],[13,1],[29,1],[31,1],[43,1],[127,1],[379,1],[449,1],[601,1],[2521,1],[7603,1],[19531,1],[519499,1],[234750601,1],[24587411156281,1]]); -gf_set(2, 102, x^102+x^29+1); +gf_set_data(2, 102, x^102+x^29+1); gf_data(2,102,x^102+x^29+1,x+1,5070602400912917605986812821504,5070602400912917605986812821503,[[3,2],[7,1],[103,1],[307,1],[2143,1],[2857,1],[6529,1],[11119,1],[43691,1],[131071,1]]); -gf_set(5, 61, x^61+x^15+1); +gf_set_data(5, 61, x^61+x^15+1); gf_data(5,61,x^61+x^15+1,x+4,4336808689942017736029811203479766845703125,4336808689942017736029811203479766845703124,[[2,2],[8419,1],[918585913061,1],[140194179307171898833699259,1]]); -gf_set(8796519617, 8, x^8+3*x^6+x+1); +gf_set_data(8796519617, 8, x^8+3*x^6+x+1); gf_data(8796519617,8,x^8+3*x^6+x+1,x+9,35849822058178726610670969179311817327626124038937602048832281182665519944803841,35849822058178726610670969179311817327626124038937602048832281182665519944803840,[[2,9],[3,1],[5,1],[127,1],[181,1],[1777,1],[2777,1],[4157,1],[6353,1],[59273,1],[77347,1],[136537,1],[247853,1],[82605209,1],[97755241,1],[7210741073,1],[172484071933,1]]); -gf_set(3, 120, x^120+x^4-1); +gf_set_data(3, 120, x^120+x^4-1); gf_data(3,120,x^120+x^4+2,x^3+x^2+2,1797010299914431210413179829509605039731475627537851106401,1797010299914431210413179829509605039731475627537851106400,[[2,5],[5,2],[7,1],[11,2],[13,1],[31,1],[41,1],[61,1],[73,1],[241,1],[271,1],[1181,1],[4561,1],[6481,1],[298801,1],[26050081,1],[42521761,1],[47763361,1]]); -gf_set(18659817111137); +gf_set_data(18659817111137); gf_data(18659817111137,1,x,3,18659817111137,18659817111136,[[2,5],[29347,1],[19869809,1]]); gf_log(7); @@ -151,7 +151,7 @@ gf_log(7); /* Examples adapted from contrib/gf/gf_manual.pdf */ -gf_set(2, 4, x^4+x+1); +gf_set_data(2, 4, x^4+x+1); gf_data(2,4,x^4+x+1,x,16,15,[[3,1],[5,1]]); (a : x^3+x^2+1, b : x^3+x+1, 0); @@ -229,7 +229,7 @@ p : subst(a, z, p); gf_eval(p); 0; -gf_set(7, 4, x^4+3*x^3+5*x^2+6*x+2); +gf_set_data(7, 4, x^4+3*x^3+5*x^2+6*x+2); gf_data(7,4,x^4+3*x^3+5*x^2+6*x+2,x+4,2401,2400,[[2,5],[3,1],[5,2]]); (char : 7, exp : 4, g : 3*x^3+3*x^2+6, 0); @@ -268,7 +268,7 @@ x^4+4*x^3+8*x^2+8*x+7; gf_factor(s); x*(x+2)*(x+3)*(x+6); -gf_set(2,4,x^4+x+1); +gf_set_data(2,4,x^4+x+1); gf_data(2,4,x^4+x+1,x,16,15,[[3,1],[5,1]]); (M : matrix([x^3+x^2+x, x^3, x^3+x^2], [x^2, x^3+x^2+1, x^3+x+1], [x^2+x, x^3+x^2+x+1, x^2]), 0); @@ -280,7 +280,7 @@ matrix([x^2, x^3+x^2+x+1, x^3], [x^3+x+1, x^2+x, x^3+1], [x, 0, x^3+x+1]); gf_matmult(M, MI); matrix([1,0,0], [0,1,0], [0,0,1]); -gf_set(2, 10, x^10+x^3+1); +gf_set_data(2, 10, x^10+x^3+1); gf_data(2,10,x^10+x^3+1,x,1024,1023,[[3,1],[11,1],[31,1]]); pe : gf_normal(); @@ -305,7 +305,7 @@ gf_normal_basis_rep(a, M); gf_normal_basis_rep(gf_exp(a, 2), M); [1,1,1,0,1,0,1,1,1,0]; -gf_set(2, 20, x^20+x^3+1); +gf_set_data(2, 20, x^20+x^3+1); gf_data(2,20,x^20+x^3+1,x,1048576,1048575,[[3,1],[5,2],[11,1],[31,1],[41,1]]); (a : x^15+x^5+1, 0); @@ -319,31 +319,31 @@ x^17+x^16+x^13+x^12+x^11+x^3+x^2+x; /* some new tests */ -gf_set(2, 12, x^12+x^3+1); +gf_set_data(2, 12, x^12+x^3+1); gf_data(2,12,x^12+x^3+1,x+1,4096,4095,[[3,2],[5,1],[7,1],[13,1]]); gf_log(gf_exp(x+1, 1234)); 1234; -gf_set(8796519617, 2, x^2+3); +gf_set_data(8796519617, 2, x^2+3); gf_data(8796519617,2,x^2+3,x+9,77378757372265826689,77378757372265826688,[[2,7],[3,1],[127,1],[1777,1],[2777,1],[4157,1],[77347,1]]); gf_log(gf_exp(x+9, 1234567890)); 1234567890; -gf_set(2, 4); +gf_set_data(2, 4); gf_data(2,4,x^4+x+1,x,16,15,[[3,1],[5,1]]); (prod : (z - 0), for i:1 thru 15 do prod : prod*(z - gf_exp(x,i)), gf_eval(prod)); z^16+z; -(kill(a), gf_set(2, 4, a^4+a+1), p : z^4+z+1, 0); +(kill(a), gf_set_data(2, 4, a^4+a+1), p : z^4+z+1, 0); 0; map(gf_eval, divide(p, z - a)); [z^3+a*z^2+a^2*z+a^3+1, 0]; -gf_set(13, 7,x^7+3*x+2); +gf_set_data(13, 7,x^7+3*x+2); gf_data(13,7,x^7+3*x+2,x,62748517,62748516,[[2,2],[3,1],[5229043,1]]); p : 9*x^6+12*x^5+5*x^4+x^3+8*x^2+2*x; @@ -360,7 +360,7 @@ matrix([9,12,5,1,8,2,0],[7,1,12,5,4,2,6],[10,8,8,6,11,12,10], gf_normal_basis_rep(p, M); [0,0,0,0,0,0,1]; -gf_set(2, x^8+x^4+x^3+x+1); +gf_set_data(2, x^8+x^4+x^3+x+1); gf_data(2,8,x^8+x^4+x^3+x+1,x+1,256,255,[[3,1],[5,1],[17,1]]); M : matrix([2,3,1,1], [1,2,3,1], [1,1,2,3], [3,1,1,2]); @@ -381,25 +381,25 @@ matrix([14,11,13,9], [9,14,11,13], [13,9,14,11], [11,13,9,14]); fs_ord : ifactors(7^4-1); [[2,5],[3,1],[5,2]]; -gf_set(7, 4); +gf_set_data(7, 4); gf_data(7,4,x^4+x+1,x+5,2401,2400,[[2,5],[3,1],[5,2]]); -gf_set(7, 4, fs_ord); +gf_set_data(7, 4, fs_ord); gf_data(7,4,x^4+x+1,x+5,2401,2400,[[2,5],[3,1],[5,2]]); -gf_set(7, x^4+x^2+3); +gf_set_data(7, x^4+x^2+3); gf_data(7,4,x^4+x^2+3,x+1,2401,2400,[[2,5],[3,1],[5,2]]); -gf_set(7, 4, x^4+x^2+3); +gf_set_data(7, 4, x^4+x^2+3); gf_data(7,4,x^4+x^2+3,x+1,2401,2400,[[2,5],[3,1],[5,2]]); -gf_set(7, x^4+x^2+3, fs_ord); +gf_set_data(7, x^4+x^2+3, fs_ord); gf_data(7,4,x^4+x^2+3,x+1,2401,2400,[[2,5],[3,1],[5,2]]); -gf_set(7, 4, x^4+x^2+3, fs_ord); +gf_set_data(7, 4, x^4+x^2+3, fs_ord); gf_data(7,4,x^4+x^2+3,x+1,2401,2400,[[2,5],[3,1],[5,2]]); -gf_set(2, x^8+1); +gf_set_data(2, x^8+1); gf_data(2,8,x^8+1,false,256,128,[[2,7]]); gf_order(); @@ -414,19 +414,22 @@ false; gf_gcdex(x+1, gf_reduction()); [1, 0, x+1]; -gf_set(3, x^8+1); +gf_set_data(3, x^8+1); gf_data(3,8,x^8+1,false,6561,6400,[[2,8],[5,2]]); gf_order(); 6400; -gf_set(3, x^8+x+1); +gf_set_data(3, x^8+x+1); gf_data(3,8,x^8+x+1,false,6561,4368,[[2,4],[3,1],[7,1],[13,1]]); gf_order(); 4368; -gf_set(13, x^8+2); +gf_set_data(13, x^8+2); +gf_data(13,8,x^8+2,x+2,815730721,815730720,[[2,5],[3,1],[5,1],[7,1],[17,1],[14281,1]]); + +gf_get_data(); gf_data(13,8,x^8+2,x+2,815730721,815730720,[[2,5],[3,1],[5,1],[7,1],[17,1],[14281,1]]); (a : x^7+x+1, b : x^3+3*x^2+9*x+7, 0); @@ -438,6 +441,30 @@ x^2+2*x+7; gf_gcdex(a, b); [7, 6*x^4+8*x^3+3*x, x^2+2*x+7]; +gf_primitive_poly(7, 8); +x^8+x+3; + +gf_primitive_poly_p(x^8+x+3, 7); +true; + +gf_primitive_poly_p(gf_irreducible(7, 8), 7); +true; + +gf_primitive_poly(2, 8); +x^8+x^4+x^3+x^2+1; + +gf_primitive_poly_p(x^8+x^4+x^3+x^2+1, 2); +true; + +gf_primitive_poly_p(gf_irreducible(2, 8), 2); +false; + +block([count:0, end:2*3^4], + for n:3^4 thru end do + if gf_primitive_poly_p(p:gf_n2p(n, 3), 3) then count:count+1, + count); +8; + (remvalue(a,b,c,d,p,g,M,MI,ord,pe,r,s,u,prod,MP,MPI,fs_ord), modulus : modulus_copy, 0); 0; ----------------------------------------------------------------------- Summary of changes: share/contrib/gf/aes.mac | 4 +- share/contrib/gf/aes2.mac | 2 +- share/contrib/gf/gf_manual.pdf | Bin 96308 -> 96480 bytes share/contrib/gf/gf_manual.tex | 24 +++++----- tests/rtest_numth.mac | 101 +++++++++++++++++++++++++--------------- 5 files changed, 79 insertions(+), 52 deletions(-) hooks/post-receive -- Maxima CAS |