OKlibrary  0.2.1.6
ModularArithmetic.mac
Go to the documentation of this file.
00001 /* Oliver Kullmann, 21.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/DataStructures/Lisp/Lists.mac")$
00023 oklib_include("OKlib/ComputerAlgebra/Algebra/Lisp/Groupoids/Semigroups/Order.mac")$
00024 oklib_include("OKlib/ComputerAlgebra/Algebra/Lisp/Ringframes/Rings/ResidueClasses.mac")$
00025 
00026 
00027 /* The Maxima-function power_mod handles m=1 not always correctly: */
00028 power_mod_corr(a,n,m) := if m=1 then 0 else power_mod(a,n,m)$
00029 
00030 /*
00031   See ComputerAlgebra/Algebra/Lisp/Ringframes/Rings/ResidueClasses.mac
00032   for the ring ZZ_n.
00033 */
00034 
00035 
00036 /* ******************************
00037    * Order and related concepts *
00038    ******************************
00039 */
00040 
00041 /* Index, period, and order w.r.t. multiplication modulo m: */
00042 modular_ipo(a,m) := ipo_element_sgr(mod_mul(m),mod(a,m))$
00043 
00044 
00045 /* ***********************
00046    * Discrete logarithms *
00047    ***********************
00048 */
00049 
00050 /* m >= 1, a, b integers */
00051 modular_log(a,b,m) := if m=1 then 0 else block([found : inf, p : 1],
00052  a : mod(a,m), b : mod(b,m),
00053  for e : 0 thru m-1 do
00054    if p=a then (found : e, return()) else p:mod(p*b,m),
00055  return(found))$
00056 /* Specification:
00057    If modular_log(a,b,m)#inf then
00058      power_mod_corr(b,modular_log(a,b,m),m)=mod(a,m).
00059    Always holds for all integers 0 <= e < modular_log(a,b,m):
00060      power_mod_corr(b,e,m) # mod(a,m).
00061 */
00062 
00063 
00064 /* *******************
00065    * Primitive roots *
00066    *******************
00067 */
00068 
00069 /* The integer m is a primitive root modulo the natural number n >= 1
00070    iff m generates the group of invertible elements of the ring ZZ_n:
00071 */
00072 primitive_modular_root_p(m,n) := gcd(m,n)=1 and
00073  block([phi : totient(n), exponents],
00074   exponents : phi / map(first,ifactors(phi)),
00075   primitive_modular_root_p_inherited(m))$
00076 /* Inherits variables n, exponents (= phi / map(first,ifactors(phi)) for
00077    phi=totient(n)):
00078 */
00079 primitive_modular_root_p_inherited(m) := gcd(m,n)=1 and
00080   every_s(lambda([e], is(power_mod(m,e,n) # 1)), exponents)$
00081 
00082 /* Testing whether for the natural number n >= 1 a primitive root modulo n
00083    exists:
00084 */
00085 has_primite_modular_root_p(n) := elementp(n,{1,2,4}) or
00086  block([f : ifactors(n)],
00087   (length(f) = 1 and first(first(f)) # 2) or 
00088   (length(f) = 2 and first(f)=[2,1]))$
00089 
00090 /* Smallest primitive root modulo n, assuming it exists (otherwise an infinite
00091    loop is entered):
00092 */
00093 smallest_primitive_modular_root(n) := block([phi : totient(n), exponents],
00094  exponents : phi / map(first,ifactors(phi)),
00095  for r : 0 do if primitive_modular_root_p_inherited(r) then return(r))$
00096 
00097