OKlibrary  0.2.1.6
ModularArithmetic.mac
Go to the documentation of this file.
00001 /* Oliver Kullmann, 22.10.2011 (Swansea) */
00002 /* Copyright 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 
00022 oklib_include("OKlib/ComputerAlgebra/TestSystem/Lisp/Asserts.mac")$
00023 oklib_include("OKlib/ComputerAlgebra/NumberTheory/Lisp/ModularArithmetic.mac")$
00024 
00025 
00026 kill(f)$
00027 
00028 /* ******************************
00029    * Order and related concepts *
00030    ******************************
00031 */
00032 
00033 okltest_modular_ipo(f) := (
00034   for m : 1 thru 5 do
00035     assert(f(0,m) = [1,1,1]),
00036   for m : 1 thru 5 do
00037     assert(f(1,m) = [1,1,1]),
00038   for m : 3 thru 5 do
00039     assert(f(-1,m) = [1,2,2]),
00040   assert(f(2,4) = [2,1,2]),
00041   assert(f(2,5) = [1,4,4]),
00042   assert(f(3,5) = [1,4,4]),
00043   assert(f(2,6) = [1,2,2]),
00044   assert(f(3,6) = [1,1,1]),
00045   assert(f(4,6) = [1,1,1]),
00046   assert(f(2,7) = [1,3,3]),
00047   assert(f(3,7) = [1,6,6]),
00048   assert(f(4,7) = [1,3,3]),
00049   assert(f(5,7) = [1,6,6]),
00050   assert(f(2,8) = [3,1,3]),
00051   assert(f(3,8) = [1,2,2]),
00052   assert(f(4,8) = [2,1,2]),
00053   assert(f(5,8) = [1,2,2]),
00054   assert(f(6,8) = [3,1,3]),
00055   assert(f(2,9) = [1,6,6]),
00056   assert(f(3,9) = [2,1,2]),
00057   assert(f(4,9) = [1,3,3]),
00058   assert(f(5,9) = [1,6,6]),
00059   assert(f(6,9) = [2,1,2]),
00060   assert(f(7,9) = [1,3,3]),
00061   true)$
00062 
00063 
00064 /* ***********************
00065    * Discrete logarithms *
00066    ***********************
00067 */
00068 
00069 okltest_modular_log(f) := block(
00070   assert(f(0,0,1) = 0),
00071   assert(f(0,0,2) = 1),
00072   assert(f(1,2,2) = 0),
00073   assert(f(0,2,2) = 1),
00074   assert(f(5,2,7) = inf),
00075   assert(f(5,3,7) = 5),
00076   assert(f(2,3,5) = 3),
00077   for a : 0 thru if oklib_test_level=0 then 5 else 8 do
00078     for b : 0 thru if oklib_test_level=0 then 5 else 8 do
00079       for m : 1 thru if oklib_test_level=0 then 5 else 10 do
00080        block([l : f(a,b,m)],
00081         for e : 0 thru m-1 while e < l do
00082           assert(power_mod(b,e,m) # mod(a,m)),
00083         if l#inf then
00084           assert(power_mod_corr(b,l,m) = mod(a,m))
00085       ),
00086   assert(f(383814208, 2, 777777777) = 3690),
00087   if oklib_test_level <= 2 then return(true),
00088   assert(f(3,2,777777777) = inf),
00089   assert(f(3, 10,1111111181) = 898664729),
00090 
00091   true)$
00092 
00093 
00094 /* *******************
00095    * Primitive roots *
00096    *******************
00097 */
00098 
00099 okltest_primitive_modular_root_p(f) := (
00100   assert(f(0,1) = true),
00101   assert(f(1,1) = true),
00102   assert(f(-1,1) = true),
00103   assert(f(0,2) = false),
00104   assert(f(1,2) = true),
00105   assert(f(2,2) = false),
00106   assert(f(3,2) = true),
00107   assert(f(-1,2) = true),
00108   assert(f(0,3) = false),
00109   assert(f(1,3) = false),
00110   assert(f(2,3) = true),
00111   assert(f(3,3) = false),
00112   assert(f(4,3) = false),
00113   assert(f(5,3) = true),
00114   assert(f(-1,3) = true),
00115   assert(f(0,4) = false),
00116   assert(f(1,4) = false),
00117   assert(f(2,4) = false),
00118   assert(f(3,4) = true),
00119   assert(f(0,5) = false),
00120   assert(f(1,5) = false),
00121   assert(f(2,5) = true),
00122   assert(f(3,5) = true),
00123   assert(f(4,5) = false),
00124   assert(f(2,6) = false),
00125   assert(f(3,6) = false),
00126   assert(f(4,6) = false),
00127   assert(f(5,6) = true),
00128   assert(f(2,7) = false),
00129   assert(f(3,7) = true),
00130   assert(f(4,7) = false),
00131   assert(f(5,7) = true),
00132   assert(f(6,7) = false),
00133   assert(f(3,31) = true),
00134   assert(f(4,31) = false),
00135   assert(f(17,31) = true),
00136   assert(f(18,31) = false),
00137   assert(f(10,97) = true),
00138   true)$
00139 
00140 okltest_has_primite_modular_root_p(f) := (
00141   for n : 1 thru 27 do
00142     assert(f(n) = (not elementp(n, {8,12,15,16,20,21,24}))),
00143   true)$
00144 
00145 okltest_smallest_primitive_modular_root(f) := block(
00146   assert(f(1) = 0),
00147   assert(f(2) = 1),
00148   assert(f(3) = 2),
00149   assert(f(4) = 3),
00150   assert(f(5) = 2),
00151   assert(f(6) = 5),
00152   assert(f(7) = 3),
00153   assert(f(9) = 2),
00154   assert(f(10) = 3),
00155   if oklib_test_level=0 then return(true),
00156   assert(f(1000000000000000000000000000000000000000000000000000000000007) = 5),
00157   true)$
00158