AG codes and decoders

[kwankyu]

We add AG codes and unique decoders for AG codes.

In Attachments below, there are Jupyter notebooks demonstrating the new features provided by this ticket. These were presented in 2019 SIAM Conference on Algebraic Geometry.

---

The author was supported by NRF of Korea 2018, 2019, 2020

Component: coding theory

Author: Kwankyu Lee

Branch/Commit: 7097dc7

Reviewer: Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/27957

[kwankyu]

Author: Kwankyu Lee

[kwankyu]

Branch: u/klee/27957

[sagetrac-git]

Commit: 1295929

[sagetrac-git]

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

1295929

Add AG codes and decoders

[kwankyu]

Dependencies: #27873

[kwankyu]

Changed dependencies from #27873 to #27873, #27634

[sagetrac-git]

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

965f050	Merge branch 'curves-2-trac27954' into curves-3-trac27955
42ad3b9	Merge branch 'curves-3-trac27955' into curves-4-trac27956
9fa25f4	Merge branch 'curves-4-trac27956' into ag-codes-base
04d0cb9	fix
94ca618	fix
25139ce	pyflakes fix
4fb3475	Merge branch 'curves-2-trac27954' into curves-3-trac27955
f102381	Merge branch 'curves-3-trac27955' into curves-4-trac27956
92cefd2	Merge branch 'curves-4-trac27956' into ag-codes-base
6285d99	Add AG codes and decoders

[sagetrac-git]

Changed commit from 1295929 to 6285d99

[sagetrac-git]

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

3dc2b79

Add AG codes and decoders

[sagetrac-git]

Changed commit from 6285d99 to 3dc2b79

[embray]

comment:10

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).

[sagetrac-git]

Changed commit from 3dc2b79 to 2057fcd

[sagetrac-git]

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

2057fcd

Add AG codes and decoders

[sagetrac-git]

Changed commit from 2057fcd to bd43bff

[sagetrac-git]

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

bd43bff

Add AG codes and decoders

[kwankyu]

comment:64

Replying to @tscrim:

I think it is good. Although I am just a little nervous about the pickling solution. I think it is a good solution, but I am not entirely sure. I think we should ask on sage-devel about it.

As far as I understand, an object is constructed from the pickled data and uses the current code. I think it is possible in principle that a change in a different part of Sage may affect the constructor of the object and hence a newly constructed object may behave differently from an unpickled object. However, in our case, the decoder's data is all of basic types such as finite field elements, polynomials, matrices , vectors, etc. Hence it is unlikely that the data of a newly constructed object is different from an unpickled data. Moreover even if it happens, it would be detected everywhere in Sage.

Do you still want to discuss this matter in sage-devel?

[tscrim]

comment:65

I think we should because what if the pickles get replaced that has something evil included (say, some extra method that is monkey-patched into __init__ that deletes everything on the system). We also haven't done anything like this in Sage (at least since we removed the pickle jar). So I just want to be a bit cautious here before proceeding.

[kwankyu]

comment:66

Replying to @tscrim:

I think we should

Okay.

what if the pickles get replaced that has something evil included.

The pickles would be part of the Sage lib. Why pickles are more vulnerable than other code? Do you imagine that some evil author and reviewer cooperate to slip in the evil code passing the release manager's eyes?

say, some extra method that is monkey-patched into __init__ that deletes everything on the system

Is this possible with a pickle? As far as I know, a pickle does not contain code.

We also haven't done anything like this in Sage (at least since we removed the pickle jar). So I just want to be a bit cautious here before proceeding.

I agree. I also wondered if there should be a central place to hold the pickles for this doctesting purpose. Note that I added .../coding/tests directory for this purpose.

[tscrim]

comment:67

Replying to @kwankyu:

Replying to @tscrim:

I think we should

Okay.

what if the pickles get replaced that has something evil included.

The pickles would be part of the Sage lib. Why pickles are more vulnerable than other code? Do you imagine that some evil author and reviewer cooperate to slip in the evil code passing the release manager's eyes?

You end up reading a file on the system and (blindly) executing it in the doctest.

say, some extra method that is monkey-patched into __init__ that deletes everything on the system

Is this possible with a pickle? As far as I know, a pickle does not contain code.

A pickle can (and IIRC usually) contain an objects __dict__, which can contain functions that can be bound to the object I believe. I am not really an expert on this, so it is possible I am just being paranoid (or there are other more likely security breaches to occur).

We also haven't done anything like this in Sage (at least since we removed the pickle jar). So I just want to be a bit cautious here before proceeding.

I agree. I also wondered if there should be a central place to hold the pickles for this doctesting purpose. Note that I added .../coding/tests directory for this purpose.

I saw that and thought that was good. The only place that was natural to me is in the $SAGE_SRC/tests folder (possibly as a coding subfolder).

[fchapoton]

comment:68

too many colons here:

+    TESTS::
+
+    We save the decoder for later tests::

[fchapoton]

comment:69

I guess Apery should be "Apéry"

[dimpase]

comment:70

Can these pickles be replaced by text data? I really struggle to imagine a smallish Sage object that cannot be quickly built from text data or json.

[dimpase]

comment:71

in any event, code to build these .sobj or otherwise pickled objects should be easy to run (I don't know how to run tests which are tagged # not tested).

[kwankyu]

comment:72

Replying to @dimpase:

in any event, code to build these .sobj or otherwise pickled objects should be easy to run (I don't know how to run tests which are tagged # not tested).

Obviously you run the code in the example just above the test tagged with # not tested to construct the object to save.

Do I misunderstand you?

[kwankyu]

comment:73

Replying to @dimpase:

Can these pickles be replaced by text data? I really struggle to imagine a smallish Sage object that cannot be quickly built from text data or json.

It takes no time, relatively, to load and save the pickles. To construct an object(in our case, decoder) to save takes time.

Do you mean that dumping an object to a string and saving the string somewhere is better than a pickle in binary format? Would you explain how and in what respect it is better?

[kwankyu]

comment:74

Replying to @fchapoton:

I guess Apery should be "Apéry"

Right. I didn't try to input an accented character on my keyboard. I will.

[kwankyu]

comment:75

json is recommended. I have no experience with serializing objects in json. Is it practically doable with any Sage object?

[sagetrac-git]

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

30d81a7	Merge branch 'develop' into ag-codes-trac27957
e843edc	Fixes for some typos

[sagetrac-git]

Changed commit from e333ffe to e843edc

[sagetrac-git]

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

2b03e24

Abandon using pickle jar for doctesting

[sagetrac-git]

Changed commit from e843edc to 2b03e24

[kwankyu]

comment:78

As a few people expressed concerns using pickles for doctesting and there is no alternative practical way to store sage objects, I decided to abandon saved objects for speed up doctesting.

Now most doctests are tagged # long time except the class level examples.

[sagetrac-git]

Changed commit from 2b03e24 to 7097dc7

[sagetrac-git]

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

7097dc7

More refined "# long time" marked tests.

[tscrim]

comment:80

I feel it is better to mark any long test as long rather than separate out the class-level tests. This also led to a test that took 8s to run on my machine not marked as long. I also removed the long marked things that weren't needed for me as per --warn-long.

Something that we could consider doing is having a hidden @cached_function that just creates all of the necessary objects and returns them as a tuple. Since testing in Sage does not reset the session after each block, the result is cached as we only need to pay the penalty once when running the file. We would only use this in the hidden attributes; especially for the ones that have trivial output such as _latex_. Although perhaps there is a more trivial example that could be done for those?

[kwankyu]

comment:81

Replying to @tscrim:

I feel it is better to mark any long test as long rather than separate out the class-level tests. This also led to a test that took 8s to run on my machine not marked as long. I also removed the long marked things that weren't needed for me as per --warn-long.

Okay.

Something that we could consider doing is having a hidden @cached_function that just creates all of the necessary objects and returns them as a tuple. Since testing in Sage does not reset the session after each block, the result is cached as we only need to pay the penalty once when running the file. We would only use this in the hidden attributes; especially for the ones that have trivial output such as _latex_. Although perhaps there is a more trivial example that could be done for those?

This sounds not much different from what I did originally. Moreover I don't want to clutter the code only for testing things. I think we did enough for this ticket regarding doctesting.

[tscrim]

comment:82

Replying to @kwankyu:

Replying to @tscrim:

Something that we could consider doing is having a hidden @cached_function that just creates all of the necessary objects and returns them as a tuple. Since testing in Sage does not reset the session after each block, the result is cached as we only need to pay the penalty once when running the file. We would only use this in the hidden attributes; especially for the ones that have trivial output such as _latex_. Although perhaps there is a more trivial example that could be done for those?

This sounds not much different from what I did originally. Moreover I don't want to clutter the code only for testing things. I think we did enough for this ticket regarding doctesting.

The difference would be that it is created as part of the Sage session that is easily modified. However, I agree that the current state is sufficient (despite lacking a good solution). So we can set this to a positive review once the patchbot comes back green.

[kwankyu]

comment:83

Replying to @tscrim:

The difference would be that it is created as part of the Sage session that is easily modified.

I now see your point. It is a clever idea.

However, I agree that the current state is sufficient (despite lacking a good solution).

I do too.

So we can set this to a positive review once the patchbot comes back green.

Okay. Thank you.

[tscrim]

comment:84

Replying to @kwankyu:

Replying to @tscrim:

The difference would be that it is created as part of the Sage session that is easily modified.

I now see your point. It is a clever idea.

However, I agree that the current state is sufficient (despite lacking a good solution).

I do too.

So we can set this to a positive review once the patchbot comes back green.

Okay. Thank you.

Green bot. I am guessing you don't want to switch, correct?

[kwankyu]

comment:85

Replying to @tscrim:

Replying to @kwankyu:

Replying to @tscrim:

The difference would be that it is created as part of the Sage session that is easily modified.

I now see your point. It is a clever idea.

However, I agree that the current state is sufficient (despite lacking a good solution).

I do too.

So we can set this to a positive review once the patchbot comes back green.

Okay. Thank you.

Green bot. I am guessing you don't want to switch, correct?

Correct. No.

[vbraun]

Changed branch from public/coding/ag-codes-27957 to 7097dc7