From: Volker v. N. <va...@us...> - 2013-07-30 14:16:03
|
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 2037eb93e07b3944e9d0f62467d05d7d7e949115 (commit) from 95326997c88257dde5628e5c4b662ed50a9893fe (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 2037eb93e07b3944e9d0f62467d05d7d7e949115 Author: Volker van Nek <vol...@gm...> Date: Tue Jul 30 16:15:44 2013 +0200 updating tests and doc for numth diff --git a/doc/info/Number.texi b/doc/info/Number.texi index 99694f7..0fe5f5a 100644 --- a/doc/info/Number.texi +++ b/doc/info/Number.texi @@ -396,17 +396,16 @@ Example: See @mref{ifactors}. @deffn {Function} fib (@var{n}) Returns the @var{n}'th Fibonacci number. -@code{fib(0)} equal to 0 and @code{fib(1)} equal to 1, -and +@code{fib(0)} is equal to 0 and @code{fib(1)} equal to 1, and @code{fib (-@var{n})} equal to @code{(-1)^(@var{n} + 1) * fib(@var{n})}. After calling @code{fib}, -@code{prevfib} is equal to @code{fib (@var{x} - 1)}, +@code{prevfib} is equal to @code{fib(@var{n} - 1)}, the Fibonacci number preceding the last one computed. @example -(%i1) map (fib, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]); -(%o1) [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55] +(%i1) map (fib, [-4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8]); +(%o1) [- 3, 2, - 1, 1, 0, 1, 1, 2, 3, 5, 8, 13, 21] @end example @opencatbox @@ -545,7 +544,7 @@ if @var{n} is a zero divisor modulo @var{m}. @example (%i1) inv_mod(3, 41); (%o1) 14 -(%i2) ratsimp(3^-1), modulus=41; +(%i2) ratsimp(3^-1), modulus = 41; (%o2) 14 (%i3) inv_mod(3, 42); (%o3) false @@ -600,6 +599,37 @@ The arguments may be general expressions as well as integers. @end deffn @c ----------------------------------------------------------------------------- +@anchor{lucas} +@deffn {Function} lucas (@var{n}) + +Returns the @var{n}'th Lucas number. +@code{lucas(0)} is equal to 2 and @code{lucas(1)} equal to 1, and +@code{lucas(-@var{n})} equal to @code{(-1)^(-@var{n}) * lucas(@var{n})}. + +@example +(%i1) map (lucas, [-4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8]); +(%o1) [7, - 4, 3, - 1, 2, 1, 3, 4, 7, 11, 18, 29, 47] +@end example + +After calling @code{lucas}, the global variable +@code{next_lucas} is equal to @code{lucas (@var{n} + 1)}, +the Lucas number following the last returned. The example shows +how Fibonacci numbers can be computed via @code{lucas} and @code{next_lucas}. + +@example +(%i1) fib_via_lucas(n) := + block([lucas : lucas(n)], + signum(n) * (2*next_lucas - lucas)/5 )$ +(%i2) map (fib_via_lucas, [-4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8]); +(%o2) [- 3, 2, - 1, 1, 0, 1, 1, 2, 3, 5, 8, 13, 21] +@end example + +@opencatbox +@category{Number theory} +@closecatbox +@end deffn + +@c ----------------------------------------------------------------------------- @anchor{mod} @deffn {Function} mod (@var{x}, @var{y}) @@ -892,6 +922,91 @@ Examples: @end defvr @c ----------------------------------------------------------------------------- +@anchor{zn_add_table} +@deffn {Function} zn_add_table (@var{n}) + +Shows an addition table of all elements in (Z/@var{n}Z). + +See also @mref{zn_mult_table}, @mref{zn_power_table}. + +@opencatbox +@category{Number theory} +@closecatbox +@end deffn + +@c ----------------------------------------------------------------------------- +@anchor{zn_determinant} +@deffn {Function} zn_determinant (@var{matrix}, @var{p}) + +Uses the technique of LU-decomposition to compute the determinant of @var{matrix} +over (Z/@var{p}Z). @var{p} must be a prime. + +However if the determinant is equal to zero the LU-decomposition might fail. +In that case @code{zn_determinant} computes the determinant non-modular +and reduces thereafter. + +See also @mref{zn_invert_by_lu}. + +Examples: + +@example +(%i1) m : matrix([1,3],[2,4]); + [ 1 3 ] +(%o1) [ ] + [ 2 4 ] +(%i2) zn_determinant(m, 5); +(%o2) 3 +(%i3) m : matrix([2,4,1],[3,1,4],[4,3,2]); + [ 2 4 1 ] + [ ] +(%o3) [ 3 1 4 ] + [ ] + [ 4 3 2 ] +(%i4) zn_determinant(m, 5); +(%o4) 0 +@end example + +@opencatbox +@category{Number theory} +@closecatbox +@end deffn + +@c ----------------------------------------------------------------------------- +@anchor{zn_invert_by_lu} +@deffn {Function} zn_invert_by_lu (@var{matrix}, @var{p}) + +Uses the technique of LU-decomposition to compute the modular inverse of +@var{matrix} over (Z/@var{p}Z). @var{p} must be a prime and @var{matrix} +invertible. @code{zn_invert_by_lu} returns @code{false} if @var{matrix} +is not invertible. + +See also @mref{zn_determinant}. + +Example: + +@example +(%i1) m : matrix([1,3],[2,4]); + [ 1 3 ] +(%o1) [ ] + [ 2 4 ] +(%i2) zn_determinant(m, 5); +(%o2) 3 +(%i3) mi : zn_invert_by_lu(m, 5); + [ 3 4 ] +(%o3) [ ] + [ 1 2 ] +(%i4) matrixmap(lambda([a], mod(a, 5)), m . mi); + [ 1 0 ] +(%o4) [ ] + [ 0 1 ] +@end example + +@opencatbox +@category{Number theory} +@closecatbox +@end deffn + +@c ----------------------------------------------------------------------------- @anchor{zn_log} @deffn {Function} zn_log (@var{a}, @var{g}, @var{n}) @deffnx {Function} zn_log (@var{a}, @var{g}, @var{n}, [[@var{p1}, @var{e1}], @dots{}, [@var{pk}, @var{ek}]]) @@ -957,6 +1072,40 @@ The run time primarily depends on the bitlength of the totient's greatest prime @end deffn @c ----------------------------------------------------------------------------- +@anchor{zn_mult_table} +@deffn {Function} zn_mult_table (@var{n}) +@deffnx {Function} zn_mult_table (@var{n}, all) + +Without the optional argument @var{all} @code{zn_mult_table(n)} +shows a multiplication table of all elements in (Z/@var{n}Z)* +which are all elements invertible modulo @var{n}. + +The optional argument @var{all} causes the table to be printed for all +non-zero elements. + +See also @mref{zn_add_table}, @mref{zn_power_table}. + +Examples: + +@example +(%i1) zn_mult_table(4); + [ 1 3 ] +(%o1) [ ] + [ 3 1 ] +(%i2) zn_mult_table(4, all); + [ 1 2 3 ] + [ ] +(%o2) [ 2 0 2 ] + [ ] + [ 3 2 1 ] +@end example + +@opencatbox +@category{Number theory} +@closecatbox +@end deffn + +@c ----------------------------------------------------------------------------- @anchor{zn_order} @deffn {Function} zn_order (@var{x}, @var{n}) @deffnx {Function} zn_order (@var{x}, @var{n}, [[@var{p1}, @var{e1}], @dots{}, [@var{pk}, @var{ek}]]) @@ -1015,6 +1164,47 @@ The optional third argument must be of the same form as the list returned by @end deffn @c ----------------------------------------------------------------------------- +@anchor{zn_power_table} +@deffn {Function} zn_power_table (@var{n}) +@deffnx {Function} zn_power_table (@var{n}, all) + +Without the optional argument @var{all} @code{zn_power_table(n)} +shows a power table of all elements in (Z/@var{n}Z)* +which are all elements invertible modulo @var{n}. +The exponent loops from @code{1} to @code{totient(n)} and the table ends with +a column of ones on the right side. + +The optional argument @var{all} causes the table to be printed for all +non-zero elements. In this case the exponent loops from @code{1} to +@code{totient(n) + 1} and the last column is therefore equal to the first. + +See also @mref{zn_add_table}, @mref{zn_mult_table}. + +Examples: + +@example +(%i1) zn_power_table(6); + [ 1 1 ] +(%o1) [ ] + [ 5 1 ] +(%i2) zn_power_table(6, all); + [ 1 1 1 ] + [ ] + [ 2 4 2 ] + [ ] +(%o2) [ 3 3 3 ] + [ ] + [ 4 4 4 ] + [ ] + [ 5 1 5 ] +@end example + +@opencatbox +@category{Number theory} +@closecatbox +@end deffn + +@c ----------------------------------------------------------------------------- @anchor{zn_primroot} @deffn {Function} zn_primroot (@var{n}) @deffnx {Function} zn_primroot (@var{n}, [[@var{p1}, @var{e1}], @dots{}, [@var{pk}, @var{ek}]]) diff --git a/tests/rtest_numth.mac b/tests/rtest_numth.mac index 10a4599..5a38630 100644 --- a/tests/rtest_numth.mac +++ b/tests/rtest_numth.mac @@ -73,16 +73,17 @@ chinese(rems, mods); (remvalue(p,fs,g,a,n,mods,x,rems), 0); 0; -(kill(all), modulus_copy : modulus, modulus : false, 0); +(kill(all), modulus_copy : modulus, modulus : false, +gf_coeff_limit_copy : gf_coeff_limit, gf_coeff_limit : 256, 0); 0; /* Tests adapted from contrib/gf/gf_test.mac */ -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_data(123127, x^5+2*x+1), gf_infolist() ); +[123127,x^5+2*x+1,x+4,28298700309333316062584407,28298700309333316062584406]; -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_set_data(7, x^10+5*x^2+x+5), gf_infolist() ); +[7,x^10+5*x^2+x+5,x,282475249,282475248]; gf_exp(gf_primitive(), gf_index(x^9+3*x^6+x^5+2*x^2+6)); x^9+3*x^6+x^5+2*x^2+6; @@ -90,26 +91,29 @@ 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_data(19); -gf_data(19,1,x,2,19,18,[[2,1],[3,2]]); +( gf_set_data(19), gf_infolist() ); +[19,x,2,19,18]; gf_exp(gf_primitive(), gf_index(17)); 17; -gf_set_data(10000000019); -gf_data(10000000019,1,x,2,10000000019,10000000018,[[2,1],[131,1],[521,1],[73259,1]]); +( gf_set_data(10000000019), gf_infolist() ); +[10000000019,x,2,10000000019,10000000018]; gf_exp(gf_primitive() ,gf_index(3)); 3; -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_data(32717, x^11+x^5+x^2+x+1), gf_infolist() ); +[32717,x^11+x^5+x^2+x+1,x+2, + 45973568360012658888852552517205008541393124962933, + 45973568360012658888852552517205008541393124962932]; -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_data(211, x^17+2*x^2+1), gf_infolist() ); +[211,x^17+2*x^2+1,x+6,3256879871129217157345956711624826081171, + 3256879871129217157345956711624826081170]; -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_set_data(2, x^20+x^3+x^2+x+1), gf_infolist() ); +[2,x^20+x^3+x^2+x+1,x^2+x,1048576,1048575]; gf_exp(gf_primitive(), gf_index(x^10+1)); x^10+1; @@ -117,42 +121,54 @@ x^10+1; gf_minimal_poly(x^10+1); z^20+z^13+z^12+z^5+z^4+z^3+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]]); +( gf_set_data(3, x^91+x^35+x+1), gf_infolist() ); +[3,x^91+x^35+x+1,x,26183890704263137277674192438430182020124347, + 26183890704263137277674192438430182020124346]; /* Tests adapted from contrib/gf/gf_hard_test.mac */ -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_data(7, x^61+x^4+1), gf_infolist() ); +[7,x^61+x^4+1,x+3,3556153025177363557255317383565515512407041673852007, + 3556153025177363557255317383565515512407041673852006]; -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_data(197, x^24-x^8+2), gf_infolist() ); +[197,x^24+196*x^8+2,x+19, + 11673186598630578538556565100133681446610566511878526881, + 11673186598630578538556565100133681446610566511878526880]; -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_data(5, x^84+x^41+x^2+1), gf_infolist() ); +[5,x^84+x^41+x^2+1,x^2+1, + 51698788284564229679463043254372678347863256931304931640625, + 51698788284564229679463043254372678347863256931304931640624]; -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_data(2, x^102+x^29+1), gf_infolist() ); +[2,x^102+x^29+1,x+1,5070602400912917605986812821504, + 5070602400912917605986812821503]; -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_data(5, x^61+x^15+1), gf_infolist() ); +[5,x^61+x^15+1,x+4,4336808689942017736029811203479766845703125, + 4336808689942017736029811203479766845703124]; -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_data(8796519617, x^8+3*x^6+x+1), gf_infolist() ); +[8796519617,x^8+3*x^6+x+1,x+9, + 35849822058178726610670969179311817327626124038937602048832281182665519944803841, + 35849822058178726610670969179311817327626124038937602048832281182665519944803840]; -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_data(3, x^120+x^4-1), gf_infolist() ); +[3,x^120+x^4+2,x^3+x^2+2, + 1797010299914431210413179829509605039731475627537851106401, + 1797010299914431210413179829509605039731475627537851106400]; -gf_set_data(18659817111137); -gf_data(18659817111137,1,x,3,18659817111137,18659817111136,[[2,5],[29347,1],[19869809,1]]); +( gf_set_data(18659817111137), gf_infolist() ); +[18659817111137,x,3,18659817111137,18659817111136]; gf_log(7); 15962290024269; /* Examples adapted from contrib/gf/gf_manual.pdf */ -gf_set_data(2, 4, x^4+x+1); -gf_data(2,4,x^4+x+1,x,16,15,[[3,1],[5,1]]); +( gf_set_data(2, x^4+x+1), gf_infolist() ); +[2,x^4+x+1,x,16,15]; (a : x^3+x^2+1, b : x^3+x+1, 0); 0; @@ -187,7 +203,7 @@ gf_index(a); ev(a = gf_exp(x, 13)), pred; true; -(gf_make_arrays(), 0); +(gf_make_logs(), 0); 0; gf_logs[10]; @@ -229,8 +245,8 @@ p : subst(a, z, p); gf_eval(p); 0; -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]]); +( gf_set_data(7, x^4+3*x^3+5*x^2+6*x+2), gf_infolist() ); +[7,x^4+3*x^3+5*x^2+6*x+2,x+4,2401,2400]; (char : 7, exp : 4, g : 3*x^3+3*x^2+6, 0); 0; @@ -250,10 +266,10 @@ ord : char^exp - 1; c : makelist(mod(a[i] + d, ord), i, 1, 7); [330,1237,1356,310,2081,1082,1925]; -M : [1,0,1,1,0,0,1]; +m : [1,0,1,1,0,0,1]; [1,0,1,1,0,0,1]; -c : mod(sum(M[i] * c[i], i, 1, 7), ord); +c : mod(sum(m[i] * c[i], i, 1, 7), ord); 1521; r : mod(c - exp*d, ord); @@ -268,45 +284,45 @@ x^4+4*x^3+8*x^2+8*x+7; gf_factor(s); x*(x+2)*(x+3)*(x+6); -gf_set_data(2,4,x^4+x+1); -gf_data(2,4,x^4+x+1,x,16,15,[[3,1],[5,1]]); +( gf_set_data(2, x^4+x+1), gf_infolist() ); +[2,x^4+x+1,x,16,15]; -(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); +(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); 0; -MI : gf_matinv(M); +mi : gf_invert_by_lu(m); 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); +gf_matmult(m, mi); matrix([1,0,0], [0,1,0], [0,0,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]]); +( gf_set_data(2, x^10+x^3+1), gf_infolist() ); +[2,x^10+x^3+1,x,1024,1023]; -pe : gf_normal(); +elem : gf_normal(); x^7; -M : gf_normal_basis(pe); -matrix([0,0,1,0,0,0,0,0,0,0], [0,0,1,0,0,1,0,0,0,0], - [0,1,1,0,0,1,0,0,0,0], [1,1,1,1,0,1,0,0,0,0], - [1,0,1,1,1,0,0,1,1,0], [0,1,1,0,1,1,1,0,1,1], - [1,1,1,0,0,1,1,1,0,0], [1,0,1,0,0,1,0,0,1,0], - [0,0,1,0,0,0,0,1,1,0], [0,0,1,0,0,0,0,1,0,0]); +m : gf_normal_basis(elem); +matrix([0,0,0,1,1,0,1,1,0,0],[0,0,1,1,0,1,1,0,0,0], + [1,1,1,1,1,1,1,1,1,1],[0,0,0,1,1,0,0,0,0,0], + [0,0,0,0,1,1,0,0,0,0],[0,1,1,1,0,1,1,1,0,0], + [0,0,0,0,0,1,1,0,0,0],[0,0,0,0,1,0,1,0,1,1], + [0,0,0,0,1,1,0,1,1,0],[0,0,0,0,0,1,0,0,0,0]); -gf_normal_basis_rep(pe, M); -[0,0,0,0,0,0,0,0,0,1]; +gf_normal_basis_rep(elem, mi : gf_invert_by_lu(m)); +[1,0,0,0,0,0,0,0,0,0]; (a : x^9+x^7+x^6+x^5+x^3+x^2+x, 0); 0; -gf_normal_basis_rep(a, M); -[0,1,1,1,0,1,0,1,1,1]; - -gf_normal_basis_rep(gf_exp(a, 2), M); +gf_normal_basis_rep(a, mi); [1,1,1,0,1,0,1,1,1,0]; -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]]); +gf_normal_basis_rep(gf_exp(a, 2), mi); +[0,1,1,1,0,1,0,1,1,1]; + +( gf_set_data(2, x^20+x^3+1), gf_infolist() ); +[2,x^20+x^3+1,x,1048576,1048575]; (a : x^15+x^5+1, 0); 0; @@ -319,32 +335,37 @@ x^17+x^16+x^13+x^12+x^11+x^3+x^2+x; /* some new tests */ -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_set_data(2, x^12+x^3+1), gf_infolist() ); +[2,x^12+x^3+1,x+1,4096,4095]; gf_log(gf_exp(x+1, 1234)); 1234; -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_set_data(8796519617, x^2+3), gf_infolist() ); +[8796519617,x^2+3,x+9,77378757372265826689,77378757372265826688]; gf_log(gf_exp(x+9, 1234567890)); 1234567890; -gf_set_data(2, 4); -gf_data(2,4,x^4+x+1,x,16,15,[[3,1],[5,1]]); +( gf_set_data(2, 4), gf_infolist() ); +[2,x^4+x+1,x,16,15]; -(prod : (z - 0), for i:1 thru 15 do prod : prod*(z - gf_exp(x,i)), gf_eval(prod)); +( prod : (z - 0), + for i:1 thru 15 do prod : prod*(z - gf_exp(x,i)), + block([modulus:2], polymod(remainder(prod, x^4+x+1))) ); z^16+z; -(kill(a), gf_set_data(2, 4, a^4+a+1), p : z^4+z+1, 0); +fs : gf_factor(x^16-x, 2); +x*(x+1)*(x^2+x+1)*(x^4+x+1)*(x^4+x^3+1)*(x^4+x^3+x^2+x+1); + +(gf_minimal_set(2, x^17), 0); 0; -map(gf_eval, divide(p, z - a)); -[z^3+a*z^2+a^2*z+a^3+1, 0]; +apply(gf_mult, args(fs)); +x^16+x; -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]]); +( gf_set_data(13, x^7+3*x+2), gf_infolist() ); +[13,x^7+3*x+2,x,62748517,62748516]; p : 9*x^6+12*x^5+5*x^4+x^3+8*x^2+2*x; 9*x^6+12*x^5+5*x^4+x^3+8*x^2+2*x; @@ -352,55 +373,28 @@ p : 9*x^6+12*x^5+5*x^4+x^3+8*x^2+2*x; gf_normal_p(p); true; -M : gf_normal_basis(p); -matrix([9,12,5,1,8,2,0],[7,1,12,5,4,2,6],[10,8,8,6,11,12,10], - [4,5,9,8,6,11,2],[4,9,10,11,12,1,2],[2,2,3,8,6,5,8], - [3,2,5,0,5,6,5]); - -gf_normal_basis_rep(p, M); -[0,0,0,0,0,0,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]); -matrix([2,3,1,1], [1,2,3,1], [1,1,2,3], [3,1,1,2]); +m : gf_normal_basis(p); +matrix([9,7,10,4,4,2,3],[12,1,8,5,9,2,2],[5,12,8,9,10,3,5], + [1,5,6,8,11,8,0],[8,4,11,6,12,6,5],[2,2,12,11,1,5,6],[0,6,10,2,2,8,5]); -MP : matrixmap(gf_n2p, M); -matrix([x,x+1,1,1], [1,x,x+1,1], [1,1,x,x+1], [x+1,1,1,x]); - -MPI : gf_matinv(MP); -matrix([x^3+x^2+x, x^3+x+1, x^3+x^2+1, x^3+1 ], - [x^3+1, x^3+x^2+x, x^3+x+1, x^3+x^2+1], - [x^3+x^2+1, x^3+1, x^3+x^2+x, x^3+x+1 ], - [x^3+x+1, x^3+x^2+1, x^3+1, x^3+x^2+x]); - -matrixmap(gf_p2n, MPI); -matrix([14,11,13,9], [9,14,11,13], [13,9,14,11], [11,13,9,14]); +gf_normal_basis_rep(p, mi : gf_invert_by_lu(m)); +[1,0,0,0,0,0,0]; -fs_ord : ifactors(7^4-1); -[[2,5],[3,1],[5,2]]; +coeffs : gf_normal_basis_rep(x^2+4*x+7, mi); +[8,8,7,2,5,1,2]; -gf_set_data(7, 4); -gf_data(7,4,x^4+x+1,x+5,2401,2400,[[2,5],[3,1],[5,2]]); +( basis : map(gf_l2p, args(transpose(m))), + apply(gf_add, map(gf_mult, coeffs, basis)) ); +x^2+4*x+7; -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_data(7, 4), gf_infolist() ); +[7,x^4+x+1,x+5,2401,2400]; -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_data(7, x^4+x^2+3), gf_infolist() ); +[7,x^4+x^2+3,x+1,2401,2400]; -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_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_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_data(2, x^8+1); -gf_data(2,8,x^8+1,false,256,128,[[2,7]]); +( gf_set_data(2, x^8+1), gf_infolist() ); +[2,x^8+1,unknown,256,128]; gf_order(); 128; @@ -414,23 +408,20 @@ false; gf_gcdex(x+1, gf_reduction()); [1, 0, x+1]; -gf_set_data(3, x^8+1); -gf_data(3,8,x^8+1,false,6561,6400,[[2,8],[5,2]]); +( gf_set_data(3, x^8+1), gf_infolist() ); +[3,x^8+1,unknown,6561,6400]; gf_order(); 6400; -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_set_data(3, x^8+x+1), gf_infolist() ); +[3,x^8+x+1,unknown,6561,4368]; gf_order(); 4368; -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]]); +( gf_set_data(13, x^8+2), gf_infolist() ); +[13,x^8+2,x+2,815730721,815730720]; (a : x^7+x+1, b : x^3+3*x^2+9*x+7, 0); 0; @@ -465,8 +456,212 @@ block([count:0, end:2*3^4], 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); +/* lu decomposition: */ + +( gf_set_data(2, x^8+x^4+x^3+x+1), gf_infolist() ); +[2,x^8+x^4+x^3+x+1,x+1,256,255]; + +m : matrix([2,3,1,1], [1,2,3,1], [1,1,2,3], [3,1,1,2]); +matrix([2,3,1,1], [1,2,3,1], [1,1,2,3], [3,1,1,2]); + +mp : matrixmap(gf_n2p, m); +matrix([x,x+1,1,1], [1,x,x+1,1], [1,1,x,x+1], [x+1,1,1,x]); + +mpi : gf_invert_by_lu(mp); +matrix([x^3+x^2+x, x^3+x+1, x^3+x^2+1, x^3+1 ], + [x^3+1, x^3+x^2+x, x^3+x+1, x^3+x^2+1], + [x^3+x^2+1, x^3+1, x^3+x^2+x, x^3+x+1 ], + [x^3+x+1, x^3+x^2+1, x^3+1, x^3+x^2+x]); + +mi : matrixmap(gf_p2n, mpi); +matrix([14,11,13,9], [9,14,11,13], [13,9,14,11], [11,13,9,14]); + +( ef_set_data(x), ef_infolist() ); +[x,3,256,255]; + +is( ef_invert_by_lu(m) = mi ); +true; + +ef_unset(); +true; + +( p : 17, n : 4, gf_set_data(p,n), 0); +0; + +(elem : 6*x^3+13*x^2+4*x+2, gf_normal_p(elem)); +true; + +m : gf_normal_basis(elem); +matrix([6,7,11,10],[13,4,13,4],[4,1,13,16],[2,2,2,2]); + +mi : gf_invert_by_lu(m); +matrix([5,1,16,15],[14,16,13,15],[12,1,1,15],[3,16,4,15]); + +is(gf_matmult(m, mi) = diagmatrix(n, 1)); +true; + +is(zn_invert_by_lu(m, p) = mi); +true; + +mod(determinant(m), p); +3; + +mod(determinant_by_lu(m, 'generalring), p); +3; + +gf_determinant(m); +3; + +zn_determinant(m, p); +3; + +/* extension fields: AES mix columns operation */ + +( gf_set_data(2, 8), gf_infolist() ); +[2,x^8+x^4+x^3+x+1,x+1,256,255]; + +(ef_minimal_set(x^4+1), 0); +0; + +ef_irreducible_p(x^4+1); +false; + +(ibase : obase : 16, 0); +0; + +m : matrix([0d4,0e0,0b8, 1e], [0bf,0b4, 41, 27], [ 5d, 52, 11, 98], [ 30,0ae,0f1,0e5]); +matrix([0D4,0E0,0B8,1E],[0BF,0B4,41,27],[5D,52,11,98],[30,0AE,0F1,0E5]); + +c : ef_l2p(reverse(flatten(args(col(m, 1))))); +30*x^3+5D*x^2+0BF*x+0D4; + +p3 : 3*x^3+x^2+x+2; +3*x^3+x^2+x+2; + +ef_add(p3, c); +33*x^3+5C*x^2+0BE*x+0D6; + +ef_mult(p3, c); +0E5*x^3+81*x^2+66*x+4; + +i3 : ef_inv(p3); +0B*x^3+0D*x^2+9*x+0E; + +ef_div(1, p3); +0B*x^3+0D*x^2+9*x+0E; + +ef_exp(p3, -1); +0B*x^3+0D*x^2+9*x+0E; + +ef_mult(p3, i3); +1; + +(ibase : obase : 10., 0); +0; + +/* this time use lookup tables : */ + +(gf_make_logs(), 0); +0; + +ord : gf_order(); +255; + +( gf_coeff_mult(a, b) := + if a = 0 or b = 0 then 0 + else gf_powers[ ?mod(gf_logs[a] + gf_logs[b], ord) ], + + gf_coeff_inv(a) := + if a = 0 then 0 + else gf_powers[ord - gf_logs[a]], + + gf_coeff_add : ?logxor, + +0); +0; + +(ibase : obase : 16, 0); +0; + +ef_add(p3, c); +33*x^3+5C*x^2+0BE*x+0D6; + +ef_mult(p3, c); +0E5*x^3+81*x^2+66*x+4; + +i3 : ef_inv(p3); +0B*x^3+0D*x^2+9*x+0E; + +ef_div(1, p3); +0B*x^3+0D*x^2+9*x+0E; + +ef_exp(p3, -1); +0B*x^3+0D*x^2+9*x+0E; + +ef_mult(p3, i3); +1; + +(ibase : obase : 10., 0); +0; + +/* +extension fields: + +examples taken from +Efficient Software Implementations of Large Finite Fields +by LUO, BOWERS, OPREA, XU +*/ + +( gf_set_data(2, x^8+x^4+x^3+x^2+1), gf_infolist() ); +[2,x^8+x^4+x^3+x^2+1,x,256,255]; + +ef_irreducible_p(x^4+x^2+6*x+1); +true; + +ef_irreducible_p(x^6+x^2+x+32); +true; + +ef_irreducible_p(x^8+x^3+x+9); +true; + +ef_irreducible_p(x^10+x^3+x+32); +true; + +ef_irreducible_p(x^12+x^3+x+2); +true; + +ef_irreducible_p(x^14+x^3+x+33); +true; + +ef_irreducible_p(x^16+x^3+x+6); +true; + +( gf_set_data(2, x^16+x^12+x^3+x+1), gf_infolist() ); +[2,x^16+x^12+x^3+x+1,x,65536,65535]; + +ef_irreducible_p(x^2+x+8192); +true; + +ef_irreducible_p(x^3+x+1); +true; + +ef_irreducible_p(x^4+x^2+2*x+1); +true; + +ef_irreducible_p(x^5+x^2+1); +true; + +ef_irreducible_p(x^6+x^3+8192); +true; + +ef_irreducible_p(x^7+x+1); +true; + +ef_irreducible_p(x^8+x^3+x+8); +true; + +(remvalue(a,b,c,d,p,n,g,m,mi,ord,elem,r,s,u,prod,mp,mpi,fs,fs_ord,basis,coeffs,p3,i3), + modulus : modulus_copy, gf_coeff_limit : gf_coeff_limit_copy, 0); 0; gf_unset(); ----------------------------------------------------------------------- Summary of changes: doc/info/Number.texi | 202 +++++++++++++++++++++- tests/rtest_numth.mac | 451 +++++++++++++++++++++++++++++++++++-------------- 2 files changed, 519 insertions(+), 134 deletions(-) hooks/post-receive -- Maxima CAS |