Opened 17 months ago

Closed 6 months ago

Last modified 5 months ago

#25977 closed enhancement (fixed)

A Goppa code class

Reported by: fion Owned by:
Priority: major Milestone: sage-8.9
Component: coding theory Keywords: coding theory, gsoc-2018, gsoc19
Cc: dimpase, asante, klee Merged in:
Authors: Filip Ion, Marketa Slukova Reviewers: Dima Pasechnik
Report Upstream: N/A Work issues:
Branch: 23363e7 (Commits) Commit:
Dependencies: Stopgaps:

Description

This ticket presents a first implementation for Goppa codes. It contains a class goppa.py that can construct the parity matrix from a generating polynomial and a defining set.

Change History (36)

comment:1 Changed 17 months ago by git

  • Commit set to 6cfcd339a3e7cd1c3332745fb7d58ce2cfa02d9e

Branch pushed to git repo; I updated commit sha1. New commits:

6cfcd33-Goppa codes

comment:2 Changed 17 months ago by dimpase

  • Cc dimpase added; dimpase@… removed

comment:3 Changed 17 months ago by dimpase

  • Branch changed from u/fion/goppa-codes to public/coding/goppa
  • Commit changed from 6cfcd339a3e7cd1c3332745fb7d58ce2cfa02d9e to 7c0d0962266532db1e3f7ad5831206c965353ff2

comment:4 Changed 17 months ago by dimpase

Rebased over the latest Sage dev version 8.3.rc3

comment:5 Changed 17 months ago by asante

  • Cc asante added

comment:6 Changed 9 months ago by dimpase

  • Cc klee added
  • Milestone changed from sage-8.4 to sage-8.7

any reviewers for this?

comment:7 Changed 9 months ago by klee

What is the author's full name?

comment:8 Changed 9 months ago by dimpase

  • Authors changed from fion to Filip Ion

comment:9 Changed 9 months ago by dimpase

  • Keywords coding theory gsoc-2018 added

comment:10 Changed 9 months ago by embray

  • Milestone changed from sage-8.7 to sage-8.8

Ticket retargeted after milestone closed (if you don't believe this ticket is appropriate for the Sage 8.8 release please retarget manually)

comment:11 Changed 6 months ago by gh-emes4

  • Branch changed from public/coding/goppa to u/gh-emes4/coding/goppa
  • Commit 7c0d0962266532db1e3f7ad5831206c965353ff2 deleted

comment:12 Changed 6 months ago by git

  • Commit set to b507400b1bb35996dc14eb9a6b537b4f5885c3f0

Branch pushed to git repo; I updated commit sha1. New commits:

3d6e17ctesting building branches
90f3b50cherry picked commit with goppa code changes
91b182bchanged the input to the code to be only generating polynomial and defining set. added an internal function which calculates the parit check matrix using Vandermonde matrix.
8608330bugfixed all errors from previous commit
a775d5cremoved a test file
bdb1c1eMerge branch 'develop' of git://trac.sagemath.org/sage into goppa
b507400added a test case for product_code. edited Goppa code documentation.

comment:13 follow-ups: Changed 6 months ago by dimpase

  • Reviewers set to Dima Pasechnik
  • Status changed from new to needs_review

first things first

  • add yourself to the list of authors
  • make sure the only lines that are longer than 80 characters are input/output of doctests, but not elsewhere in the documentation

comment:14 Changed 6 months ago by git

  • Commit changed from b507400b1bb35996dc14eb9a6b537b4f5885c3f0 to 2c4b662aaee969d8422247d74a89bcd272843432

Branch pushed to git repo; I updated commit sha1. New commits:

2c4b662fixed documentation line length to 80 characters

comment:15 in reply to: ↑ 13 Changed 6 months ago by gh-emes4

  • Authors changed from Filip Ion to Filip Ion, Marketa Slukova

Replying to dimpase:

first things first

  • add yourself to the list of authors
  • make sure the only lines that are longer than 80 characters are input/output of doctests, but not elsewhere in the documentation

comment:16 in reply to: ↑ 13 Changed 6 months ago by gh-emes4

Replying to dimpase:

first things first

  • add yourself to the list of authors
  • make sure the only lines that are longer than 80 characters are input/output of doctests, but not elsewhere in the documentation

Done. Fixed the line length in a new commit.

comment:17 Changed 6 months ago by dimpase

oops, src/sage/coding/goppa.py is in MSDOS format. This makes diffing painful, so let's keep it in this format for review, and once done, we'll run dos2unix on it...

Last edited 6 months ago by dimpase (previous) (diff)

comment:18 follow-up: Changed 6 months ago by dimpase

  • Branch changed from u/gh-emes4/coding/goppa to public/coding/goppa
  • Commit changed from 2c4b662aaee969d8422247d74a89bcd272843432 to 5bb4bee9c923ae5bd945b9c1d8f30950062f9870
  • Status changed from needs_review to needs_work

OK, so let's work on the "public" branch, so that we both can push into the same place.

I've edited a part of the goppa.py file, in particular using

stuff like `u` - for maths (LaTeX)

stuff like ``self`` for Python variables etc

Please fix the rest of it, as well as things marked by ???.

Then, for functions and classes the 1st line of the multilibe doctring has a special meaning, it should be short, and followed by an empty line (for indexing).

I probably fixed all of the latter already.

To see my chnages, check out the branch and do git diff HEAD^ -w (-w is needed to ignore whitespace changes, as I converted the file to the Unix format...)

As well, please try building Sage docs with these changes - it's important that all the spaces are at the right places, as rst is a tricky forrmat...


New commits:

5bb4beesome formatting and English fixes

comment:19 Changed 6 months ago by embray

  • Milestone changed from sage-8.8 to sage-8.9

Tickets still needing working or clarification should be moved to the next release milestone at the soonest (please feel free to revert if you think the ticket is close to being resolved).

comment:20 Changed 6 months ago by git

  • Commit changed from 5bb4bee9c923ae5bd945b9c1d8f30950062f9870 to e5f55d8e2a29de82da0bb563a93d0b27a88bd4e9

Branch pushed to git repo; I updated commit sha1. New commits:

4c19c93Fixed formatting mistakes. Added Goppa code and encoder to catalogues.
e5f55d8Added Goppa code to documentation

comment:21 in reply to: ↑ 18 Changed 6 months ago by gh-emes4

Replying to dimpase: Fixed everything in the latest commit.

comment:22 Changed 6 months ago by gh-emes4

  • Status changed from needs_work to needs_review

comment:23 Changed 6 months ago by dimpase

Please inspect the results of docbuild in the browser, by opening file:///<SAGEROOT>/share/doc/sage/html/en/reference/coding/sage/coding/goppa.html (where you need to replace <SAGEROOT> by the full path to your Sage install)

Things inside TeX markers should be proper TeX maths, e.g. F_{p^m} rather than F_p^m. I've started on doing needed changes:

  • src/sage/coding/goppa.py

    diff --git a/src/sage/coding/goppa.py b/src/sage/coding/goppa.py
    index 10f0d8e1d3..bbb45269e4 100755
    a b class GoppaCode(AbstractLinearCode): 
    1919    Implementation of Goppa codes
    2020
    2121    Goppa codes are a generalization of narrow-sense BCH codes.
    22     These codes are defined by a generating polynomial `g over a finite field
    23     `F_p^m`, and a defining set `L` of elements from `F_p^m`, which are not roots
     22    These codes are defined by a generating polynomial `g` over a finite field
     23    `F_{p^m}`, and a defining set `L` of elements from `F_{p^m}`, which are not roots
    2424    of `g`. The number of defining elements determines the length of the code.
    2525
    26     In binary cases, the minimum distance is `2*t + 1`, where `t` is the degree
     26    In binary cases, the minimum distance is `2t + 1`, where `t` is the degree
    2727    of `g`.
    2828
    2929    INPUTS:
    3030
    3131    - ``generating_pol`` -- a monic polynomial with coefficients in a finite
    32       field `F_p^m`, the code is defined over `F_p`, `p` must be a prime number
     32      field `F_{p^m}`, the code is defined over `F_p`, `p` must be a prime number
    3333
    34     - ``defining_set`` -- a set of elements of `F_p^m` that are not roots
     34    - ``defining_set`` -- a set of elements of `F_{p^m}` that are not roots
    3535      of `g`, its cardinality is the length of the code
    3636
    3737    EXAMPLES::

Please do this for the whole file.

comment:24 Changed 6 months ago by dimpase

I'll push the commit for the latter, just a moment.

comment:25 Changed 6 months ago by git

  • Commit changed from e5f55d8e2a29de82da0bb563a93d0b27a88bd4e9 to c1e03bfbaf54285356a9136eb2d8ba15a4679656

Branch pushed to git repo; I updated commit sha1. New commits:

c1e03bf1st part of doc changes

comment:26 Changed 6 months ago by git

  • Commit changed from c1e03bfbaf54285356a9136eb2d8ba15a4679656 to 9a4304e6196aa503318916f7d5eeb1b18db25a4d

Branch pushed to git repo; I updated commit sha1. New commits:

f429b05fixed tex formatting in docs
9a4304efixed list in parity check matrix documentation

comment:27 Changed 6 months ago by gh-emes4

I fixed all the TeX formatting. Also noticed that there was a badly formatted list in the parity check matrix documentation bit and fixed that too.

comment:28 Changed 6 months ago by git

  • Commit changed from 9a4304e6196aa503318916f7d5eeb1b18db25a4d to fd9740c7ee577a8cb490dafb3fdcefbb3f650371

Branch pushed to git repo; I updated commit sha1. New commits:

fd9740cwords must be separated from inline markup in rst

comment:29 Changed 6 months ago by git

  • Commit changed from fd9740c7ee577a8cb490dafb3fdcefbb3f650371 to 65cfd1f6d006d58d67a570d00a9bf79457355233

Branch pushed to git repo; I updated commit sha1. New commits:

65cfd1fUTF is needed to allow ` \times `, it appears

comment:30 Changed 6 months ago by git

  • Commit changed from 65cfd1f6d006d58d67a570d00a9bf79457355233 to 4500f78a84b17a25376fd78240aa7632d01213d0

Branch pushed to git repo; I updated commit sha1. New commits:

4500f78for proper \times one needs r""" comments, duh...

comment:31 Changed 6 months ago by git

  • Commit changed from 4500f78a84b17a25376fd78240aa7632d01213d0 to 23363e760db75569ee2bd44ab5ac3864d8fde89a

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

bf85275testing building branches
baa3630cherry picked commit with goppa code changes
a116a1fchanged the input to the code to be only generating polynomial and defining set. added an internal function which calculates the parit check matrix using Vandermonde matrix.
6a3f4e1bugfixed all errors from previous commit
67ee21adoctests and tests improvements
0d16848Fixed formatting mistakes. Added Goppa code and encoder to catalogues.
7d8a134docs for Goppa code code
23363e7for proper \times one needs r""" comments, duh...

comment:32 Changed 6 months ago by dimpase

some commit squashing...

comment:33 Changed 6 months ago by dimpase

  • Keywords gsoc-2019 added
  • Status changed from needs_review to positive_review

comment:34 Changed 6 months ago by dimpase

  • Keywords gsoc19 added; gsoc-2019 removed

comment:35 Changed 6 months ago by vbraun

  • Branch changed from public/coding/goppa to 23363e760db75569ee2bd44ab5ac3864d8fde89a
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:36 Changed 5 months ago by klee

  • Commit 23363e760db75569ee2bd44ab5ac3864d8fde89a deleted

There are some cleanups in #27634 for goppa.py

Note: See TracTickets for help on using tickets.