Oracle-supported drawing of the Gröbner escalier

Autori

  • Maria Emilia Alonso Universidad Complutense de Madrid
  • Maria Grazia Marinari Università degli Studi di Genova
  • Teo Mora Università degli Studi di Genova

DOI:

https://doi.org/10.1478/AAPP.982A3

Abstract

The aim of this note is to discuss the following quite queer problem: to compute the Gröbner basis of an ideal I w.r.t. a term-ordering ≺ without knowing neither the ideal nor the term-ordering but only a degree bound of the required Gröbner basis, being allowed to pose a finite number of queries to an oracle which, given a term τ ∈ T, returns its canonical form Can(τ, I, ≺) w.r.t. the unknown ideal I and term-ordering ≺. This problem was suggested to us by the desire to definitely dispose of a very weak paper  wrongly claiming a cryptographic  application of (non commutative) Gröbner bases. The commutative reformulation is instead a non-obvious  challenge and we consider it an helpful tool for understanding and visually describe the structure of the Gröbner escalier of an ideal; moreover it allows to describe (and compute) the corner set,  an helpful tool for computing Macaulay decomposition of a (non-necessarily 0-dimensional) algebra.

Biografie autore

  • Maria Emilia Alonso, Universidad Complutense de Madrid
    Departamento de Álgebra, Geometría y Topología, Facultad de Ciencias Matemáticas
  • Maria Grazia Marinari, Università degli Studi di Genova
    Dipartimento di Matematica
  • Teo Mora, Università degli Studi di Genova
    Dipartimento di Matematica

Dowloads

Pubblicato

2020-10-28

Fascicolo

V. 98 N. 2 (2020)

Sezione

Articoli

Licenza

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

Authors who publish with this journal agree to the following terms:
  • Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
  • Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
  • Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).