• Authors: Christian Kell
• BDHCP
  CoCoA Version 4.7.4

Description

The folder BDHCP contains the CoCoA implementations to the linear algebra attacks on a braid group-based Diffie-Hellman conjugacy problem (BDHCP), which we presented in our PhD thesis "A Structure-based Attack on the Linearized Braid Group-based Diffie-Hellman Conjugacy Problem in Combination with an Attack using Polynomial Interpolation and the Chinese Remainder Theorem". The thesis was submitted on November 14th, 2018 at the University of Passau, Germany. The original attack, which we improved, was presented in 2003 by Cheon and Jun (see: Jung Hee Cheon and Byungheup Jun. A polynomial time algorithm for the braid diffie-hellman conjugacy problem. In Annual International Cryptology Conference, pages 212 - 225, Springer, 2003).

To get the code running: 1. Download ApCoCoA from http://apcocoa.org/. 2. Open ApCoCoA and import the coc files and subfolders in the folder BDHCP to your apcocoa_projects folder. 3. Open the Start.coc file in the subfolder BDHCP-Algorithm and follow the description there to adapt the import commands according to your file system. 4. Have fun!

(Bachelorarbeit)

• Author: Lukas Ditschinger
• Misere Spiele am Beispiel von Chomp

(Schriftliche Hausarbeit zur Erlangung des ersten Staatsexamens)

• Author: Lara Schädel

(Schriftliche Hausarbeit zur Erlangung des ersten Staatsexamens)

• Author: Melanie Schubert
• Theorie und Praxis strategischer Spiele

• Author: Carsten Liesen

• (PolRad.pdf)(program files)
  CoCoA Version: 4.6

Description

• Three Methods for computing the radical of a polynomial ideal are implemented and compared:

  1. The method of Kemper uses a reduction to the 0-dimensional case via localization in a maximal set of independent indeterminates. Then an algorithm for the computation of the separable part of a polynomial is used to compute the radical of a 0-dimensional ideal defined over a (possibly non-perfect) function field.
  2. The method of Matsumoto works for ground fields of positive characteristic and is based on a clever use of the Frobenius automorphism.
  3. The method of Krick-Logar uses a splitting element to reduce the task to two lower-dimenisonal ideals I:h and I+(h). Since it creates many redundant irreducible components, only an optimization by Laplagne is considered here. It employs a saturation computation to avoid redundant irreducible components.
  The implementation uses CoCoAL and is not very efficient. Thus the three methods can be compared only in a "top-level" way.

(Schriftliche Hausarbeit zur Erlangung des ersten Staatsexamens)

• Author: Christina Breitkopf
• Unwahrscheinliche Wahrscheinlichkeiten

(Fundamental Classes of Zero-Dimensional Schemes)

• Author: Guntram Hainke

• FkndS.pdf(program files)
  CoCoA Version: 4.3

Description

Given a set of points X in a projective space, many of its geometric invariants (Hilbert function, socle degrees, separator degrees) are traditionally computed from its homogeneous coordinate ring R. In the paper [G. de Dominicis, M. Kreuzer, Kähler differentials for points in P^n, J. Pure Appl. Alg. 141 (1999), 153-173] the module of Kähler differentials of R was used in addition. The goal of this project was to construct the fundamental map of X explicitly. The fundamental map is a homomorphism from the module of Kähler differentials to the canonical module of X. It is an important invariant of X. Its cokernel is the Jacobian module of X, another important invariant.

The attached CoCoA files provide many programs for computing these objects and maps explicitly.

(Computing Syzygies over Non-Commutative Polynomial Rings)

• Author: Holger Bluhm

• ncsyz.pdf

Description

The topic of this thesis is the computation of two-sided syzygies of elements of certain non-commutative rings. Two-sided syzygies of ring elements f_1,...,f_s are elements of the form in a free two-sided module for which we have . The approach taken is to translate everything to syzygies of elements of a free two-sided module over the non-commutative polynomial ring (i.e. the free associative algebra) and to adapt the component elimination technique to this setting. Then the computation of syzygies over residue class rings is achieved by syzygy projection.

(Multigraded Hilbert-series and Magic Squares)

• Author: Eva Ludwig
  
  
• (magic_squares.coc)
  CoCoA Version: 4.3

Description

Given a certain kind of magic squares (traditional, associated, supermagic, pandiagonal, etc.) there are several methods one can explore to determine the number of such squares (possibly given their size or their magic sum):

1. Find the appropriate multigraded Hilbert series and determine its coefficient at the desired term. To this end, one may try to use ``truncated multiplications'' for the geometric series corresponding to the denominator polynomials.
2. Find the appropriate Hilbert basis. Then count all terms of the desired degree in a polynomial ring weighted by the magic sums of the squares corresponding to the Hilbert basis elements.
3. Represent the solution squares as a finite point set, determine its vanishing ideal and the Hilbert function of that ideal.

Some of these approaches are implemented in the given CoCoA file.

(Optimization of the Buchberger Algorithm in the Homogeneous Case)

• Author: Jens Schmidbauer
  
  
• (diploma thesis), (program files)
  Windows Program, Version 2

Description

There are two basic strategies for optimizing the performance of the Buchberger algorithm for computing a Gröbner basis of a homogeneous ideal: minimalization of the number of critical paris which have to be treated, and optimization of the reduction process for the remaining pairs.

The first optimization can be achieved using the results of [M. Caboara, M. Kreuzer, and L. Robbiano, Efficiently computing minimal sets of critical pairs, J. Symb. Comput. (to appear)] . For the second optimization, J. Schmidbauer examined in his diploma thesis various methods based on simultaneous reductions, e.g. the ones used by J.C. Faugere in his algorithm F4.

The text of the thesis and the program files (including source code and instructions) are contained in the following two files.

(Algebraic Problems in the Theory of Queuing Systems With Control)

• Author: Arndt Wills

• The files of this thesis are available in dvi-format , pdf-format , and ps-format . The file wills.zip   contains the source code of the CoCoA programs as well as the solutions for systems up to s=10. (Attention: This file is 18 MB long!)
  CoCoA Version: 4.1

Description

Queuing system with control play an important role in the production of microchips and telecommunication systems. A particularly common case has been described by H. Gold (Infineon Technologies, Regensburg) in [A Markovian single server with upstream job and downstream demand arrival system, Queuing Systems 30 (1998), 435-455]. Following his suggestions, we studied the algebraic aspects of the resulting system of equations and tried to solve it using cmputer algebra methods. The symbolic solutions allow us to examine the dependence of the numerical solutions on variations of the parameters, such as those occurring through break-downs, vacation periods, reschedulings etc.

(= Algorithms For 0-dimensional Schemes)

• Author: Thomas Eisenmann
  
  
• A number of files provide the results of these computations for some classical codes. A zipped version of the whole package (including instructions) is contained in the following file: eisenmann.zip
  CoCoA Version: 4.1

Description

In [M. Kreuzer, Algorithms for checking uniformity conditions and applications in coding theory], a number of algorithms were described. In his diploma thesis, T. Eisenmann implemented and optimized these algorithms. They are useful for checking the uniformity of sets of points in projective spaces. Translated into the language of coding theory, they yield ways to compute the minimal distance of certain codes in special cases.

(= Effective Computation of Hilbert-Kunz Functions)

• Author: Volker Augustin

• The necessary CoCoA packages and setup files are contained in the following two zip-archives.

  • (CoCoA packages)
  • (setup files)
  CoCoA Version: 4.1

Description

In characteristic p, the Hilbert-Kunz function of a 1-dimensional standard graded algebra has the same shape as described by P. Monski (in Math. Ann. 263 (1983), 43-49) for the local case. Using a variety of methods from computer algebra, the constants and the periodic function in this description can be computed effectively. The algorithm performing those calculations is contained in [M. Kreuzer, Computing Hilbert-Kunz functions of 1-dimensional graded rings] and has been implemented as part of V. Augustins diploma thesis.

(= Algorithmic Linear Algebra for Polynomial Matrices)

• Author: Bettina Krammer

• All CoCoA files are contained in alapoly.zip. A manual explaining these functions is available in dvi-format alapoly-manual.dvi   or in text format alapoly-manual.txt.
  CoCoA Version: 4.1

Description

This project aims to provide efficient implementations of the standard operations in Linear Algebra for the case of polynomial matrices. The following algorithms were implemented by Bettina Krammer in a number of different ways:

1. Bareiss' Algorithm
2. Malashonok's Algorithm
3. The algorithms of Sasaki and Murao
4. A new algorithm for computing ideals of minors

Her thesis "Algorithmische lineare Algebra für Polynommatrizen" has appeared electronically in Regensburger Math. Schriften, Volume 32   and contains explicit descriptions of these algorithms as well as extensive tests of their efficiency in various situations.

• Author: Robert Forkel

• <residues.coc>   (File Version: 1.0, Date: 1/2000)
  <residue-examples.coc>    (File Version: 1.0, Date: 1/2000)
  CoCoA 3.7

Description

The file residues.coc   contains CoCoA programs for computing residues on algebraic varieties. They are based on the diploma thesis "Effektive Berechnung von Residuenabbildungen" and have been implemented by Robert Forkel.

There is also a file residue-examples.coc which provides some examples for the usage of the functions in residues.coc.

(Macaulay "Classic" for CoCoA)

• Author: Manfred Schulz

• <macaulay.pkg>   (File Version: 6.0, Date: 7/98)
  <check.pkg>          (File Version: 6.0, Date: 7/98)
  CoCoA 3.4

Description

The following files are part of the project Macaulay.pkg. The purpose of this project was to make all functions and scripts of Macaulay "Classic" available for CoCoA users while keeping to the original syntax and functionality as much as possible.

Special thanks go to Dave Bayer, David Eisenbud and Mike Stillman for allowing us to transfer their work into the CoCoA world.

To load the package, type

<< 'macaulay.pkg'; 

inside CoCoA, or put this command inside your file userinit.coc. The package defines an alias 'MC'.To find out which functions are available, you can then type 

MC.Help_Macaulay();

inside CoCoA. You get a list of all implemented scripts. Each has its own help function, e.g. 

MC.Help_Flatten();

There is also a file called check.pkg. It contains functions to check all the macros of the package macaulay.pkg. It also provides examples for each macro. To load the package into CoCoA, type

<< 'check.pkg';

inside CoCoA. This package defines the Alias 'MCC' for itself. You can then check a macro by typing for instance

MCC.Check('DualVariety');

where the name of the macro has to be put in single quotes.

• Authors: Gabriel de Dominicis and Martin Kreuzer
  
  
• CoCoA Version: CoCoA 3.02

Description

The file points.coc contains some functions for computing with reduced zerodimensional schemes, in particular functions mentioned in the paper Kähler differentials for points in P^n

( = Computation Of Points)

• Author: Stefan Beck

Description

The main part of this program is an implementation of the algorithm described in the paper "How to compute the canonical module of a set of points'' by Stefan Beck and Martin Kreuzer. There are binaries for two operating systems:

• cop_linux.tgz   for x86 computers equipped with the Linux operating system

• cop_dos.zip      for x86 computers using the DOS/Windows operating systems

In both cases, you will find the following files (after decompression).

• cop_Fp, cop_Fp8, cop_Q, cop_QN (resp. *.exe) Binaries for various base fields (Fp = finite field, Fp8 = finite field with <256 elements, Q = rational numbers, QN = cyclotomic field)

• install.doc   Some installation instructions for DOS

• cop.doc  A short manual explaining the available commands and their syntax

• demo.doc, demo1, demo 2a, demo2b, demo3  A demo COP session and its data files

Finally, if you want to see how it's all done, you can have a look at the C++ source code for Linux and DOS. (The source code is getting pretty outdated. If you want do compile it yourself, you'll have to perform some adjustments.)

( = LINear SYZygies)

• Author: Mischa Lusteck

Description

There are several programs here, all of them implementing algorithms from the paper ``How to compute linear resolutions'' (in preparation) by Mischa Lusteck and Martin Kreuzer . To get some idea what they do, you can have a look at the abstract of that paper.

At the moment, we can offer you the following binaries:

• linsyz (for linux) resp. linsyz.exe (for DOS/Windows)   This program computes the ranks of the modules in the linear part of the resolution, if one is given the first matrix of linear forms. The syntax is
             linsyz <char> <filename> <steps>
  where <char> is a prime number (the number of elements of the base field), <filename> is the name of a file containing the matrix of linear forms in CoCoA format (the variables should be x[1],x[2],...), and <steps> is the number of steps of the resolution to be computed.
  
  

• torsyz (for linux) resp. torsyz.exe (for DOS/Windows). This program computes the rank of the i-th module in the linear part of the resolution, if one is given the first matrix of linear forms. It uses the second method described in the abstract. The syntax is
             torsyz <char> <filename> <step>
  where <char> is a prime number (the number of elements of the base field), <filename> is the name of a file containing the matrix of linear forms in CoCoA format (the variables should be x[1], x[2], ...), and <step> is the number of the step of the resolution whose rank you desire to compute.
  
  

• cop2coc (for linux)    This program allows you to transform a matrix which is the output of a COP command (i.e. which is in the Macaulay format) into the CoCoA format required by linsyz and torsyz. The syntax is
             cop2coc <inputfile> <outputfile>
  

Since this is an unfinished project, we cannot release the source codes of the above programs.

• Description: Many years ago, Nolan Wallach succeeded in compiling an executable file of Macaulay (``Macaulay Classic'') for the x86 architecture. Later, M. Kreuzer adjusted the script files to the DOS file name conventions an put together a package with documentation and test suites. This package enjoys no support whatsoever, and it is not officially distributed by the original authors Dave Bayer and Mike Stillman. Nevertheless, if you are interested, just download macaulay.zip
  unzip it in a suitable directory (e.g. in c:\macaulay) resp. its subdirectories (i.e. use something like pkunzip -d macaulay.zip), and have a look at the various ASCII files ending with *.doc.