A group ring
{{{id=88| S = SymmetricGroup(3); R=GroupAlgebra(S, QQ) /// }}} {{{id=168| R /// Group algebra of group "SymmetricGroup(3)" over base ring Rational Field }}} {{{id=95| S.gens() /// [(1,2,3), (1,2)] }}} {{{id=169| a = R(S.0) + (2/3)*R(S.1); a /// 2/3*(1,2) + (1,2,3) }}} {{{id=171| a*a /// 4/9*() + 2/3*(2,3) + (1,3,2) + 2/3*(1,3) }}} {{{id=170| /// }}}A quaternion algebra
{{{id=86| A.Monoids
A monoid is just like a group, but without the axiom that every element has an inverse. Sage has code that David Kohel wrote several years ago for working with monoids.
PROJECT: This code has not been touched in years, so it would likely be easy to improve, optimize, and extend it.
{{{id=273| ls('monoids') /// __init__.py free_monoid_element.py all.py monoid.py free_abelian_monoid.py string_monoid.py free_abelian_monoid_element.py string_monoid_element.py free_monoid.py string_ops.py }}} {{{id=342| S = HexadecimalStrings(); S /// Free hexadecimal string monoid }}} {{{id=343| x = S.gen(0); y = S.gen(10); z = S.gen(15) x*y^3*z /// 0aaaf }}} {{{id=388| /// }}} {{{id=59| /// }}}Rings
The huge rings module implements much of the underlying arithmetic in Sage. It is most complicated and mature module in Sage.
Algebraic rings: All of the standard rings, such as $\mathbf{Z}$, $\mathbf{Q}$, finite fields $\mathbf{F}_{p^n}$, and polynomial and power series rings over any other ring in Sage. Substantial code for number fields, and threes models of $p$-adic numbers: capped relative, capped absolute, fixed modulus. The algebraic closure of $\mathbf{Q}$ and its maximal totally real subfield are also implemented, using intervals.
Numerical: Real and complex numbers of any fixed precision. Double precisions reals and complex (for speed). Rings that model $\mathbf{R}$ and $\mathbf{C}$ with intervals (interval arithmetic).
At any given time, some parts of the code are very mature, and others are being actively improved.
PROJECT: The $p$-adics and numbers fields are currently actively being improved by David Roe, John Cremona, Kiran Kedlaya, and others.
PROJECT: Function fields are not sufficiently well supported yet.
PROJECT: Substantial work needs to be put into optimizing arithmetic with relative numbers fields. (Nick Alexander has worked some on this recently).
PROJECT: Groebner basis functionality is in the rings/polynomial directory, and currently mainly uses Singular. There is a huge need in Sage for an optimized F4 implementation, and we hope that this will eventually get developed by somebody (the EU has just funded Singular, which is part of Sage, to do this).
{{{id=282| ls('rings') /// __init__.py integral_domain_element.py all.py laurent_series_ring.py arith.py laurent_series_ring_element.c bernmm laurent_series_ring_element.pxd bernmm.cpp laurent_series_ring_element.pyx bernmm.pyx memory.c bernoulli_mod_p.cpp memory.pyx bernoulli_mod_p.pyx misc.py big_oh.py monomials.py coerce_python.py morphism.c commutative_algebra.py morphism.pxd commutative_algebra_element.py morphism.pyx commutative_ring.py mpfi.pxi commutative_ring_element.py noetherian_ring.py complex_double.c notes complex_double.h number_field complex_double.pxd padics complex_double.pyx pari_ring.py complex_double_api.h polynomial complex_field.py power_series_mpoly.c complex_interval.c power_series_mpoly.pxd complex_interval.pxd power_series_mpoly.pyx complex_interval.pyx power_series_poly.c complex_interval_field.py power_series_poly.pxd complex_number.c power_series_poly.pyx complex_number.pxd power_series_ring.py complex_number.pyx power_series_ring_element.c contfrac.py power_series_ring_element.pxd dedekind_domain.py power_series_ring_element.pyx dedekind_domain_element.py principal_ideal_domain.py euclidean_domain.py principal_ideal_domain_element.py euclidean_domain_element.py qqbar.py fast_arith.c quotient_ring.py fast_arith.pxd quotient_ring_element.py fast_arith.pyx rational.c field.py rational.h field_element.py rational.pxd finite_field.py rational.pxi finite_field_element.py rational.pyx finite_field_ext_pari.py rational_field.py finite_field_givaro.cpp real_double.c finite_field_givaro.pxd real_double.pxd finite_field_givaro.pyx real_double.pxi finite_field_morphism.py real_double.pyx finite_field_ntl_gf2e.cpp real_interval_field.py finite_field_ntl_gf2e.pxd real_lazy.c finite_field_ntl_gf2e.pyx real_lazy.pxd finite_field_prime_modn.py real_lazy.pyx fraction_field.py real_mpfi.c fraction_field_element.c real_mpfi.pxd fraction_field_element.pyx real_mpfi.pyx homset.py real_mpfr.c ideal.py real_mpfr.pxd ideal_monoid.py real_mpfr.pyx infinity.py real_rqdf.cpp integer.c real_rqdf.pxd integer.h real_rqdf.pyx integer.pxd residue_field.c integer.pyx residue_field.pxd integer_mod.c residue_field.pyx integer_mod.pxd ring.c integer_mod.pyx ring.pxd integer_mod_ring.py ring.pyx integer_ring.c ring_element.py integer_ring.pxd rqdf_fix.h integer_ring.pyx solaris_fix.h integer_ring_python.py stdint.h integral_domain.py tests.py }}} {{{id=339| ls('rings/number_field') /// __init__.py number_field_ideal.py all.py number_field_ideal_rel.py class_group.py number_field_morphisms.c galois_group.py number_field_morphisms.pyx maps.py number_field_rel.py morphism.py order.py number_field.py small_primes_of_degree_one.py number_field_base.c totallyreal.c number_field_base.pxd totallyreal.pyx number_field_base.pyx totallyreal_data.c number_field_element.cpp totallyreal_data.pxd number_field_element.pxd totallyreal_data.pyx number_field_element.pyx totallyreal_dsage.py number_field_element_quadratic.cpp totallyreal_phc.py number_field_element_quadratic.pxd totallyreal_rel.py number_field_element_quadratic.pyx unit_group.py }}} {{{id=340| ls('rings/polynomial') /// __init__.py polynomial_element.pyx all.py polynomial_element_generic.py complex_roots.py polynomial_fateman.py convolution.py polynomial_gf2x.cpp cyclotomic.c polynomial_gf2x.pxd cyclotomic.pyx polynomial_gf2x.pyx groebner_fan.py polynomial_integer_dense_flint.cpp infinite_polynomial_element.py polynomial_integer_dense_flint.pxd infinite_polynomial_ring.py polynomial_integer_dense_flint.pyx laurent_polynomial.c polynomial_integer_dense_ntl.cpp laurent_polynomial.pxd polynomial_integer_dense_ntl.pxd laurent_polynomial.pyx polynomial_integer_dense_ntl.pyx laurent_polynomial_ring.py polynomial_modn_dense_ntl.cpp multi_polynomial.c polynomial_modn_dense_ntl.pxd multi_polynomial.pxd polynomial_modn_dense_ntl.pyx multi_polynomial.pyx polynomial_quotient_ring.py multi_polynomial_element.py polynomial_quotient_ring_element.py multi_polynomial_ideal.py polynomial_real_mpfr_dense.c multi_polynomial_ideal_libsingular.cpp polynomial_real_mpfr_dense.pyx multi_polynomial_ideal_libsingular.pyx polynomial_ring.py multi_polynomial_libsingular.cpp polynomial_ring_constructor.py multi_polynomial_libsingular.pxd polynomial_singular_interface.py multi_polynomial_libsingular.pyx polynomial_template.pxi multi_polynomial_ring.py polynomial_template_header.pxi multi_polynomial_ring_generic.c polynomial_zmod_flint.c multi_polynomial_ring_generic.pxd polynomial_zmod_flint.pxd multi_polynomial_ring_generic.pyx polynomial_zmod_flint.pyx padics real_roots.c pbori.cpp real_roots.pxd pbori.pxd real_roots.pyx pbori.pyx symmetric_ideal.py polydict.c symmetric_reduction.c polydict.pxd symmetric_reduction.pxd polydict.pyx symmetric_reduction.pyx polynomial_compiled.c term_order.py polynomial_compiled.pxd toy_buchberger.py polynomial_compiled.pyx toy_d_basis.py polynomial_element.c toy_variety.py polynomial_element.pxd }}} {{{id=337| parent(2/3) /// Rational Field }}} {{{id=338| var('x') K.%s Random Rings
'%number) i=0 for R in sage.rings.tests.random_rings(1): print R #show(R) i += 1 if i > number: break ///
|
Working in $\overline{\mathbf{Q}}$.
{{{id=381| R.Structure
The structure module
- defines the SageObject base class for most objects in Sage
- provides the base classes for all elements and parent structures
- implements much of the coercion model
- formal sums, sequences, and factorizations
- the proof object, which allows you to determine whether or not certain classes of algorithms are only required to succeed with high probability or can assume conjectures (such as GRH),
- .. and much more.
After having undergone at least 3 major and painful revisions, the structure module is fairly mature at this point. It will gradually improve as the coercion model in Sage is slightly tweaked, as categories are improved, etc.
{{{id=297| ls('structure') /// __init__.py generators.pyx all.py gens_py.py category_object.c mutability.c category_object.pxd mutability.pxd category_object.pyx mutability.pyx coerce.c mutability_py.py coerce.pxd nonexact.py coerce.pxi parent.c coerce.pyx parent.pxd coerce_actions.c parent.pyx coerce_actions.pxd parent_base.c coerce_actions.pyx parent_base.pxd coerce_dict.c parent_base.pyx coerce_dict.pxd parent_gens.c coerce_dict.pyx parent_gens.pxd coerce_maps.c parent_gens.pyx coerce_maps.pxd parent_old.c coerce_maps.pyx parent_old.pxd element.c parent_old.pyx element.pxd proof element.pyx sage_object.c element_py.py sage_object.pxd element_verify.py sage_object.pyx factorization.py sequence.py factory.c test.sobj factory.pyx unique_representation.py formal_sum.py wrapper_parent.c generators.c wrapper_parent.pxd generators.pxd wrapper_parent.pyx }}} {{{id=191| sage.structure.element.Element ///A coercion example:
Notice that the sum below is in the parent of neither the left or right hand ring. These natural nontrivial coercions are done systematically throughout Sage. Getting this right was very hard work of Robert Bradshaw, David Roe, Craig Citro, etc.
{{{id=195| R.Surprisingly, even Magma's coercion model is way behind Sage's:
{{{id=396| %magma RSets
The sets module implements basic notions of sets of Python objects, and operations on them. It's similar to what's in the standard Python library (the set class) but with more mathematical semantics, and support for infinite sets.
Example: primes.py defines the set of prime numbers, as a sort of example of how to define an infinite set.
PROJECT: Add more examples of interesting sets to this module.
{{{id=294| ls('sets') /// __init__.py all.py family.py primes.py set.py }}} {{{id=341| %hide def f(s, braces=True): t = ', '.join(sorted(list(s))) if braces: return '{' + t + '}' return t def g(s): return set(str(s).replace(',',' ').split()) @interact def _(X='1,2,3,a', Y='2,a,3,4,apple', Z='a,b,10,apple'): S = [g(X), g(Y), g(Z)] X,Y,Z = S XY = X.intersection(Y) XZ = X.intersection(Z) YZ = Y.intersection(Z) XYZ = XY.intersection(Z) html('
|
This seems dumb, since clearly the result should just be a finite set with all elements enumerated.
{{{id=176| Z = X.intersection(Primes()); Z /// Set-theoretic intersection of {'orange', 1, 2, 5} and Set of all prime numbers: 2, 3, 5, 7, ... }}} {{{id=183| 2 in Z /// True }}} {{{id=184| 3 in Z /// False }}} {{{id=185| /// }}} {{{id=77| /// }}}Combinat
The combinat directory is well over 50,000 lines of code that implements a wide range of algebraic combinatorics functionality in Sage. It is under very active development.
- Started in 2007, when Mike Hansen (then an undergrad) decided to single-handedly port as much as possible of the MuPAD-combinat project (a major effort of nearly a dozen mathematicians) over to Sage. He got about halfway through.
- In 2008, the MuPAD combinat group decided to switch to Sage... just in time as it turns out, right before MuPAD was bought out by MATLAB.
- They have been working on porting all of MuPAD-combinat to Sage during the last year, and greatly cleaning up and improved much of the design and code. (Doing things right.)
- Major new functionality: ode for combinatorics of words, representation theory of Lie groups, etc.
PROJECT: Completely finish the port of MuPAD-combinat.
PROJECT: Dan Bump has been adding substantial new functionality for root systems.
{{{id=247| ls('combinat') /// __init__.py partition_algebra.py all.py partitions.cpp alternating_sign_matrix.py partitions.pyx backtrack.py partitions_c.cc cartesian_product.py partitions_c.h choose_nk.py permutation.py combinat.py permutation_nk.py combination.py posets combinatorial_algebra.py q_analogues.py composition.py ranker.py composition_signed.py restricted_growth.py crystals ribbon.py designs ribbon_tableau.py dlx.py root_system dyck_word.py schubert_polynomial.py expnums.c set_partition.py expnums.pyx set_partition_ordered.py family.py sf finite_class.py skew_partition.py free_module.py skew_tableau.py generator.py sloane_functions.py graph_path.py species integer_list.py split_nk.py integer_vector.py subset.py integer_vector_weighted.py subword.py lyndon_word.py symmetric_group_algebra.py matrices tableau.py misc.py tools.py multichoose_nk.py tuple.py necklace.py words output.py yamanouchi.py partition.py }}}Cartesian Products
{{{id=133| S = CartesianProduct([1,2,3],['x','y']); S /// Cartesian product of [1, 2, 3], ['x', 'y'] }}} {{{id=134| S.list() /// [[1, 'x'], [1, 'y'], [2, 'x'], [2, 'y'], [3, 'x'], [3, 'y']] }}} {{{id=411| /// }}}Root Systems
{{{id=130| S = RootSystem(['B',3]); S /// Root system of type ['B', 3] }}} {{{id=410| S.root_lattice() /// Root lattice of the Root system of type ['B', 3] }}} {{{id=131| /// }}}Partitions of an integer:
{{{id=404| P = Partitions(5); P /// Partitions of the integer 5 }}} {{{id=405| P.cardinality() /// 7 }}} {{{id=132| P.list() /// [[5], [4, 1], [3, 2], [3, 1, 1], [2, 2, 1], [2, 1, 1, 1], [1, 1, 1, 1, 1]] }}} {{{id=406| time Partitions(10^6).cardinality() /// 1471684986358223398631004760609895943484030484439142125334612747351666117418918618276330148873983597555842015374130600288095929387347128232270327849578001932784396072064228659048713020170971840761025676479860846908142829356706929785991290519899445490672219997823452874982974022288229850136767566294781887494687879003824699988197729200632068668735996662273816798266213482417208446631027428001918132198177180646511234542595026728424452592296781193448139994664730105742564359154794989181485285351370551399476719981691459022015599101959601417474075715430750022184895815209339012481734469448319323280150665384042994054179587751761294916248142479998802936507195257074485047571662771763903391442495113823298195263008336489826045837712202455304996382144601028531832004519046591968302787537418118486000612016852593542741980215046267245473237321845833427512524227465399130174076941280847400831542217999286071108336303316298289102444649696805395416791875480010852636774022023128467646919775022348562520747741843343657801534130704761975530375169707999287040285677841619347472368171772154046664303121315630003467104673818 Time: CPU 0.04 s, Wall: 0.08 s }}}Dyck words are the expressions containing $n$ pairs of correctly matched parentheses.
{{{id=407| @interact def _(n=(1..6)): for w in DyckWords(n): print w ///
|
Graphs
The Sage graphs module implements a huge amount of functionality for working with graphs (mostly by Robert Miller, Emily Kirkman, and Jason Grout, and built partly on NetworkX).
- Complete new implementation of computation of automorphism groups of graphs, determining isomorphism between graphs, and canonical labelings.
- Extensive code for plotting graphs.
- Queryable relational database of all graphs on at most 7 vertices.
- New highly optimized data structure for implementing algorithms that manipulate
- Enumerating certain types of graphs efficiently (e.g., trees).
PROJECT: Robert Miller's vision for graphs is to have graphs/base completely production level (under active development now!), so that if someone wants to write some functions in Cython, then this is the clear graph theory library to use. We need a couple submodules:
- sage/graphs/coloring/
- sage/graphs/structured_graphs/ (or something similar, for bipartite graphs, bundles, etc.)
- sage/graphs/generators/
graph.py needs to get split into several levels like the matrix code, and mostly Cythonized.
{{{id=256| ls('graphs') /// __init__.py graph_database.py linearextensions.py all.py graph_fast.c planarity base graph_fast.pyx planarity.c bipartite_graph.py graph_generators.py planarity.pyx chrompoly.c graph_isom.c print_graphs.py chrompoly.pyx graph_isom.pxd schnyder.py graph.py graph_isom.pyx trees.c graph_bundle.py graph_list.py trees.pxd graph_coloring.py graph_plot.py trees.pyx }}} {{{id=109| G = graphs.KrackhardtKiteGraph() H = G.coloring(hex_colors=True) G.plot(vertex_colors=H).show(figsize=3) ///
}}}
{{{id=110|
G.automorphism_group()
///
Permutation Group with generators [(1,10)(2,4)(5,6)]
}}}
{{{id=108|
G.chromatic_polynomial()
///
x^10 - 18*x^9 + 142*x^8 - 643*x^7 + 1837*x^6 - 3424*x^5 + 4152*x^4 - 3151*x^3 + 1356*x^2 - 252*x
}}}
{{{id=111|
///
}}}
{{{id=33|
///
}}}
Crypto
The cryptography module is under current active developmen (mainly by Martin Albrecht and Minh Nguyen), with the goal of making Sage the standard tool of choice for analysing symmetric ciphers using algebraic and numerical methods. The crypto module has two purposes:
- Teaching of fundamental building blocks of cryptography (stream ciphers and e.g. LSFRs, block ciphers and their S-Boxes).
- Aids research in cryptography by providing common building blocks.
The crypto module
- provides elementary cryptographic primitives for the purposes of teaching and cryptanalysis,
- includes scaled-down versions of standard cryptographic algorithms, and
- provides interfaces to standard cryptographic algorithms, and
- toolboxes for encryption, decryption, signatures, and hashing.
PROJECT: Minh Nguyen is working on expanding the teaching aspect right now by adding a MiniAES to sage.crypto and Martin Albrecht is expanding its usefulness for algebraic cryptanalysis by (a) adding more ciphers (e.g. DES and PRESENT) and (b) e.g. a SAT-Solver interface.
PROJECT: Create a number of modules that wrap common number theoretic building blocks related to public-key cryptography, and package them up in a form useful for performing public-key cryptographic operations. All the building blocks are there (optimized arithmetic over the integers, support for basic and advanced number theory).
{{{id=249| ls('crypto') /// __init__.py classical_cipher.py stream.py all.py cryptosystem.py stream_cipher.py cipher.py lfsr.py classical.py mq }}}Teaching crypto (there is a free undergrad cryptography book by David Kohel and Sage includes all the code he wrote for that book):
{{{id=137| M = AlphabeticStrings() E = SubstitutionCryptosystem(M); E /// Substitution cryptosystem on Free alphabetic string monoid on A-Z }}} {{{id=138| K = M([ 25-i for i in range(26) ]); K /// ZYXWVUTSRQPONMLKJIHGFEDCBA }}} {{{id=142| e = E(K) m = M("THECATINTHEHAT") secret = e(m); secret /// GSVXZGRMGSVSZG }}} {{{id=145| e.inverse()(secret) /// THECATINTHEHAT }}} {{{id=136| /// }}}Small Scale Variants of the AES (SR) Polynomial System Generator. Used to experiment with algebraic attacks on block ciphers.
{{{id=135| sr = mq.SR(1, 1, 1, 4) sr /// SR(1,1,1,4) }}} {{{id=141| print sr.R.repr_long() /// Polynomial Ring Base Ring : Finite Field in a of size 2^4 Size : 20 Variables Block 0 : Ordering : degrevlex Names : k100, k101, k102, k103, x100, x101, x102, x103, w100, w101, w102, w103, s000, s001, s002, s003, k000, k001, k002, k003 }}} {{{id=19| /// }}} {{{id=146| /// }}} {{{id=140| /// }}}