OKlibrary  0.2.1.6
ResidueClasses.mac
Go to the documentation of this file.
00001 /* Oliver Kullmann, 16.7.2008 (Swansea) */
00002 /* Copyright 2008, 2010, 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/Hypergraphs/Lisp/SetSystems.mac")$
00023 oklib_include("OKlib/ComputerAlgebra/DataStructures/Lisp/HashMaps.mac")$
00024 
00025 
00026 /* ***********************************************
00027    * The basic operations for modular arithmetic *
00028    ***********************************************
00029 */
00030 
00031 /* Prerequisite: n >= 1. */
00032 mod_add(n) := buildq([n],lambda([x,y],mod(x+y,n)))$
00033 mod_mul(n) := buildq([n],lambda([x,y],mod(x*y,n)))$
00034 /* These functions can also be used "modulo n", i.e., their inputs
00035 can be arbitrary integers. */
00036 
00037 /* The ring Z_n of residue classes modulo n, using the standard representation
00038    of the elements by 0, ..., n-1: */
00039 residues_rng(n) := [setmn(0,n-1), mod_add(n), mod_mul(n), [0], [mod(1,n)]]$
00040 
00041 /* The additive inverse: */
00042 mod_add_inv(n) := buildq([n],lambda([x],mod(-x,n)))$
00043 /* The multiplicative inverse (returns false for non-invertible
00044    elements): */
00045 mod_mul_inv(n) := buildq([n],lambda([x],inv_mod(x,n)))$
00046 
00047 /*
00048    These functions can also be used "modulo n", i.e., their inputs
00049    can be arbitrary integers.
00050 */
00051 
00052 
00053 /* Remarks:
00054 
00055  - The additive part of residues_rng(n) is used in
00056    Algebra/Lisp/Groupoids/Groups/CyclicGroups.mac by cyclic_ugrp(n) as the
00057    standard model of a cyclic group of order n.
00058  - The multiplicative group of invertible elements of residues_rng(n) is
00059    a cyclic group iff has_primite_modular_root_p(n) is true (see
00060    NumberTheory/Lisp/ModularArithmetic.mac), and a generator is then given by
00061    smallest_primitive_modular_root(n).
00062 
00063 */
00064 
00065 
00066 /* ***********************
00067    * Invertible elements *
00068    ***********************
00069 */
00070 
00071 /* The set of invertible elements of Z_n: */
00072 inv_residues(n) := subset(setmn(0,n-1), lambda([x], is(gcd(x,n)=1)))$
00073 /* The (multiplicative) group Z_n^* of invertible elements of Z_n: */
00074 inv_residues_ugrp(n) := [inv_residues(n),mod_mul(n),mod(1,n)]$
00075 
00076 
00077 /* The isomorphism of Z_n^* to Z_phi(n) (phi(n) = totient(n)) for n
00078    where Z_n^* is cyclic (see has_primite_modular_root_p(n)), given
00079    by the primitive root r modulo n, which yields for every element x in Z_n^*
00080    its index relative to r.
00081 */
00082 /* Computing the result each time from scratch: */
00083 discrete_log_bydef(n,r) := buildq([n,r], lambda([x], x : mod(x,n),
00084  for i:0 do if power_mod(r,i,n)=x then return(i)))$
00085 /* Precomputing all results, and storing internally in a hash-table: */
00086 discrete_log_bydef_hash(n,r) := block(
00087  [h:sm2hm({}), x : 1, i : 0, phi : totient(n)],
00088   while i < phi do (set_hm(h,x,i), i:i+1, x:mod(x*r,n)),
00089   buildq([h,n], lambda([x], ev_hm(h,mod(x,n)))))$
00090 
00091 /* For prime numbers n=p, where before gf_set(p) has been called (does not
00092    work reliably, due to the general problems with package gf): */
00093 oklib_plain_include(gf)$
00094 discrete_log_bygf(r) := buildq([r],lambda([x],gf_log(x,r)))$
00095 
00096 
00097 /* *****************
00098    * Homomorphisms *
00099    *****************
00100 */
00101 
00102 /* The canonical ring-homomorphisms from Z_n onto Z_m for m | n, given
00103    by 1 -> 1:
00104 */
00105 canhom_residues(m) := buildq([m],lambda([x], mod(x,m)))$
00106 
00107