Sage: Ticket #8335: Finite field lattices via Conway polynomials
https://trac.sagemath.org/ticket/8335
<p>
Implements coercion within lattices of finite fields lying above the same prime when implemented with Conway polynomials.
</p>
<pre class="wiki">sage: k = GF(9, conway=True, prefix='z')
sage: l = GF(27, conway=True, prefix='z')
sage: x = k.gen() + l.gen(); x
z6^5 + 2*z6^4 + 2*z6^3 + z6^2 + 2*z6 + 1
sage: x.parent()
Finite Field in z6 of size 3^6
</pre><p>
When using the <code>conway</code> and <code>prefix</code> parameters, one does not need to specify an explicit variable name; if no variable name is given, it is constructed from the <code>prefix</code> and the degree (as in the above code snippet).
</p>
<p>
In the future, the functionality of this ticket will be incorporated into that for algebraic closures of finite fields. It will then be possible to construct compatible systems of finite fields outside the range of the Conway polynomial database using the pseudo-Conway polynomials from <a class="closed ticket" href="https://trac.sagemath.org/ticket/14958" title="enhancement: Implement pseudo-Conway polynomials (closed: fixed)">#14958</a>: polynomials that satisfy all of the algebraic constraints on Conway polynomials without the lexicographic constraint that imposes uniqueness.
</p>
<p>
Apply:
</p>
<ul><li><a class="attachment" href="https://trac.sagemath.org/attachment/ticket/8335/trac_8335-finite_field_coerce-5.11.b3-14888.patch" title="Attachment 'trac_8335-finite_field_coerce-5.11.b3-14888.patch' in Ticket #8335">trac_8335-finite_field_coerce-5.11.b3-14888.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/8335/trac_8335-finite_field_coerce-5.11.b3-14888.patch" title="Download"></a>
</li><li><a class="attachment" href="https://trac.sagemath.org/attachment/ticket/8335/trac_8335-no_pseudo.patch" title="Attachment 'trac_8335-no_pseudo.patch' in Ticket #8335">trac_8335-no_pseudo.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/8335/trac_8335-no_pseudo.patch" title="Download"></a>
</li></ul>en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/8335
Trac 1.1.6roedTue, 23 Feb 2010 17:33:25 GMTstatus, type changed
https://trac.sagemath.org/ticket/8335#comment:1
https://trac.sagemath.org/ticket/8335#comment:1
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>type</strong>
changed from <em>defect</em> to <em>enhancement</em>
</li>
</ul>
TicketroedTue, 23 Feb 2010 17:37:08 GMT
https://trac.sagemath.org/ticket/8335#comment:2
https://trac.sagemath.org/ticket/8335#comment:2
<p>
Part of a series:
</p>
<pre class="wiki">8218 -> 8332 -> 7880 -> 7883 -> 8333 -> 8334 -> 8335
</pre><p>
I tried to make each of these mostly self contained, with doctests passing after every ticket, but I didn't entirely succeed. If you're reviewing one of these tickets, applying later tickets will hopefully fix doctest failures that you're seeing.
</p>
TicketroedTue, 23 Feb 2010 17:42:07 GMTdescription changed
https://trac.sagemath.org/ticket/8335#comment:3
https://trac.sagemath.org/ticket/8335#comment:3
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/8335?action=diff&version=3">diff</a>)
</li>
</ul>
TicketroedTue, 23 Feb 2010 17:50:46 GMTattachment set
https://trac.sagemath.org/ticket/8335
https://trac.sagemath.org/ticket/8335
<ul>
<li><strong>attachment</strong>
set to <em>finite_field_coerce_ALL.patch</em>
</li>
</ul>
<p>
Includes everything in 8218, 8332, 7880, 7883, 8333, 8334 and 8335 except the 8218 bundle, which you must apply first.
</p>
TicketroedTue, 23 Feb 2010 17:51:54 GMT
https://trac.sagemath.org/ticket/8335#comment:4
https://trac.sagemath.org/ticket/8335#comment:4
<p>
For convenience, I added a giant patch which includes all the changes except the bundle at 8218 (which we want to leave as a bundle in order to preserve file history).
</p>
TicketcremonaSat, 03 Apr 2010 13:16:59 GMTdescription changed
https://trac.sagemath.org/ticket/8335#comment:5
https://trac.sagemath.org/ticket/8335#comment:5
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/8335?action=diff&version=5">diff</a>)
</li>
</ul>
TicketdavidloefflerTue, 20 Apr 2010 10:31:13 GMTstatus changed
https://trac.sagemath.org/ticket/8335#comment:6
https://trac.sagemath.org/ticket/8335#comment:6
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
This doesn't apply cleanly: the patch <code>8335_pseudo_conway.patch</code> seems to conflict with something. FWIW, I am using 4.4.alpha0 with qseries
</p>
<pre class="wiki">trac_8446.patch
trac_8446_microfix.patch
trac_8722.patch
7883_ideals.patch
8333_parent_init.patch
8333_finite_fields_to_new_coercion.patch
7585_9_1_frac_and_coerce_updates.patch
8334_residue_fields-rebased_for_8446.patch
7585_12_1_fixes.patch
8335_pseudo_conway.patch
</pre>
TicketroedTue, 21 Jun 2011 13:51:50 GMTattachment set
https://trac.sagemath.org/ticket/8335
https://trac.sagemath.org/ticket/8335
<ul>
<li><strong>attachment</strong>
set to <em>8335_pseudo_conway.patch</em>
</li>
</ul>
<p>
Apply first
</p>
TicketroedTue, 21 Jun 2011 21:43:48 GMTstatus changed
https://trac.sagemath.org/ticket/8335#comment:7
https://trac.sagemath.org/ticket/8335#comment:7
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
TicketroedWed, 22 Jun 2011 07:51:14 GMT
https://trac.sagemath.org/ticket/8335#comment:8
https://trac.sagemath.org/ticket/8335#comment:8
<p>
To work against 4.7, apply 8335_pseudo_conway.patch then 8335_finite_field_coerce_vs_47.patch.
</p>
TicketroedWed, 22 Jun 2011 08:53:25 GMTattachment set
https://trac.sagemath.org/ticket/8335
https://trac.sagemath.org/ticket/8335
<ul>
<li><strong>attachment</strong>
set to <em>8335_finite_field_coerce.patch</em>
</li>
</ul>
<p>
Apply second
</p>
TicketroedWed, 22 Jun 2011 08:53:42 GMTattachment set
https://trac.sagemath.org/ticket/8335
https://trac.sagemath.org/ticket/8335
<ul>
<li><strong>attachment</strong>
set to <em>8335_finite_field_coerce_vs_47.patch</em>
</li>
</ul>
<p>
Against 4.7 for patchbot
</p>
TicketroedWed, 22 Jun 2011 08:54:14 GMT
https://trac.sagemath.org/ticket/8335#comment:9
https://trac.sagemath.org/ticket/8335#comment:9
<p>
To work against 4.7, apply 8335_pseudo_conway.patch then 8335_finite_field_coerce_vs_47.patch.
</p>
TicketroedWed, 22 Jun 2011 08:56:02 GMT
https://trac.sagemath.org/ticket/8335#comment:10
https://trac.sagemath.org/ticket/8335#comment:10
<p>
Apply 8335_pseudo_conway.patch, 8335_finite_field_coerce_vs_47.patch
</p>
TicketdefeoWed, 13 Jul 2011 07:04:11 GMTstatus changed; cc set
https://trac.sagemath.org/ticket/8335#comment:11
https://trac.sagemath.org/ticket/8335#comment:11
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
<li><strong>cc</strong>
<em>defeo</em> added
</li>
</ul>
<p>
I still get the following failures on 4.7.1.alpha4 with 8335_pseudo_conway.patch and 8335_finite_field_coerce_vs_47.patch applied:
</p>
<pre class="wiki"> sage -t -long devel/sage/sage/matrix/matrix2.pyx # 2 doctests failed
sage -t -long devel/sage/sage/rings/finite_rings/constructor.py # 1 doctests failed
</pre>
TicketdefeoWed, 13 Jul 2011 18:20:57 GMT
https://trac.sagemath.org/ticket/8335#comment:12
https://trac.sagemath.org/ticket/8335#comment:12
<p>
I also get 7 warnings when building the docs. These all seem to be missing blank lines and unmatched backquoutes in <code>sage/rings/finite_rings/constructor.py</code>
</p>
TicketrbeezerMon, 09 Apr 2012 03:24:44 GMTcc changed
https://trac.sagemath.org/ticket/8335#comment:13
https://trac.sagemath.org/ticket/8335#comment:13
<ul>
<li><strong>cc</strong>
<em>rbeezer</em> added
</li>
</ul>
TicketjpfloriFri, 08 Feb 2013 14:30:26 GMTattachment set
https://trac.sagemath.org/ticket/8335
https://trac.sagemath.org/ticket/8335
<ul>
<li><strong>attachment</strong>
set to <em>trac_8335-pseudo_conway-5.7.b3.patch</em>
</li>
</ul>
<p>
Patch for PCP; rebased on top of 5.7.beta3.
</p>
TicketjpfloriFri, 08 Feb 2013 14:30:46 GMTattachment set
https://trac.sagemath.org/ticket/8335
https://trac.sagemath.org/ticket/8335
<ul>
<li><strong>attachment</strong>
set to <em>trac_8335-finite_field_coerce-5.7.b3.patch</em>
</li>
</ul>
<p>
Patch for coercion; rebased on top of 5.7.beta3.
</p>
TicketjpfloriFri, 08 Feb 2013 14:31:06 GMTattachment set
https://trac.sagemath.org/ticket/8335
https://trac.sagemath.org/ticket/8335
<ul>
<li><strong>attachment</strong>
set to <em>trac_8335-doc-5.7.beta3.patch</em>
</li>
</ul>
<p>
Patch for doc fixes; rebased on top of 5.7.beta3.
</p>
TicketjpfloriFri, 08 Feb 2013 14:40:16 GMTstatus, description, milestone changed
https://trac.sagemath.org/ticket/8335#comment:14
https://trac.sagemath.org/ticket/8335#comment:14
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_info</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/8335?action=diff&version=14">diff</a>)
</li>
<li><strong>milestone</strong>
changed from <em>sage-5.7</em> to <em>sage-5.8</em>
</li>
</ul>
<p>
These patches were quite old and things have moved around since they were written.
As a consequence, part of the old patches now apply to different files, that is the case of the NTL GF2E implementation which has been split in a Python and a Cython file.
</p>
<p>
Some pseudo Conway polys changed so that two doctests now fail (not corrected in the patches cause I did not take the time to think about it, feel free to do it).
As these pseudo Conway polynomials are not unique, I'm not sure if the procedure to generate them is deterministic or to which point randomness comes into play and if the failing doctests are just due to some routine called during the generation which may give a different result since the patches were originally written.
</p>
<p>
Not really sure how to cast restriction on the is_square and squarefree_decomposition methods, nor what I've changed makes sense, I've come up with this quickly, feel free to correct it.
The basic problem was that now Sage supports function fields where we have no p-th roots and that raised an <a class="missing wiki">AttributeError?</a> when calling is_square which called squarefree_decomposition in some doctests.
</p>
<p>
The doc now builds ok and looks nice (although I did not have LaTeX on my computer), but may need some revamping.
Nonetheless it would be great to get this in quickly.
</p>
TicketjpfloriFri, 08 Feb 2013 14:59:55 GMT
https://trac.sagemath.org/ticket/8335#comment:15
https://trac.sagemath.org/ticket/8335#comment:15
<p>
I've just launche "make ptestlong" (only tested the ring dir before) and saw some errors on screen, will report later.
</p>
TicketjpfloriSat, 09 Feb 2013 13:57:17 GMTattachment set
https://trac.sagemath.org/ticket/8335
https://trac.sagemath.org/ticket/8335
<ul>
<li><strong>attachment</strong>
set to <em>trac_8335-doc-5.7.b3.patch</em>
</li>
</ul>
<p>
Fixes
</p>
TicketjpfloriSat, 09 Feb 2013 13:59:21 GMT
https://trac.sagemath.org/ticket/8335#comment:16
https://trac.sagemath.org/ticket/8335#comment:16
<p>
There were problem doing coercion because Sage now tried to define algebraic extension of Integers(1) and failed on <a class="missing wiki">ArithmeticError?</a> when trying 0<sup>0, or depth of recursion if that was changed to return 1.
</sup></p>
<p>
I've added an extension method to the IntegerModring_generic class to handle separatly this ring.
</p>
<p>
Did not check everything is fine though.
</p>
TicketjpfloriSat, 09 Feb 2013 13:59:36 GMTdescription changed
https://trac.sagemath.org/ticket/8335#comment:17
https://trac.sagemath.org/ticket/8335#comment:17
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/8335?action=diff&version=17">diff</a>)
</li>
</ul>
TickethdsThu, 14 Feb 2013 09:53:21 GMTcc changed
https://trac.sagemath.org/ticket/8335#comment:18
https://trac.sagemath.org/ticket/8335#comment:18
<ul>
<li><strong>cc</strong>
<em>hds</em> added
</li>
</ul>
<p>
I went looking through some papers by Heath and Loehr and it appears that the output of an algorithm to compute a pseudo-conway polynomial will most likely not be deterministic unless <code>f.any_root()</code> is deterministic for polynomials in finite fields (something I'm not entirely sure about).
</p>
<p>
In this case, I'm not sure what to do about the tests, but I agree that it would be nice to move this patch along - but I'm not qualified to review it.
</p>
TicketjpfloriThu, 14 Feb 2013 09:56:15 GMT
https://trac.sagemath.org/ticket/8335#comment:19
https://trac.sagemath.org/ticket/8335#comment:19
<p>
We have some Sage meeting near Paris in France today, with a tutorial about ... finite fields.
We'll try to polish this one up there.
</p>
TicketroedThu, 14 Feb 2013 10:45:41 GMT
https://trac.sagemath.org/ticket/8335#comment:20
https://trac.sagemath.org/ticket/8335#comment:20
<p>
Fantastic! I've been meaning to get back to this but have been busy with other things. Let me know what comes up and I can review your changes if necessary.
</p>
TicketjpfloriThu, 14 Feb 2013 16:08:26 GMT
https://trac.sagemath.org/ticket/8335#comment:21
https://trac.sagemath.org/ticket/8335#comment:21
<p>
That got broken again in 5.7.b4 by <a class="closed ticket" href="https://trac.sagemath.org/ticket/13064" title="defect: The documentation should search methods in classes (closed: fixed)">#13064</a>.
</p>
TicketjpfloriThu, 14 Feb 2013 16:22:35 GMT
https://trac.sagemath.org/ticket/8335#comment:22
https://trac.sagemath.org/ticket/8335#comment:22
<p>
Rebased on top of 5.7.b4.
</p>
TicketjpfloriThu, 14 Feb 2013 18:53:52 GMT
https://trac.sagemath.org/ticket/8335#comment:23
https://trac.sagemath.org/ticket/8335#comment:23
<p>
With the last set of patches, it passes make ptestlong except:
</p>
<ul><li>one test in finite_rings/constructor.py because of a warning about Cunningham table, this does not seem harmful, so we should just change the test.
</li><li>two tests in matrix2.py which is more worrying, although I did not really looked at it, because some "is in prime field?" fails.
</li></ul>
TicketjpfloriMon, 18 Feb 2013 16:21:36 GMT
https://trac.sagemath.org/ticket/8335#comment:24
https://trac.sagemath.org/ticket/8335#comment:24
<p>
I've fixed some additional stuff and have new two concerns (in addition to the matrix2 stuff I've not dealt with):
</p>
<ul><li>the cunningham tables did not get standard so we cannot really use them (or we'll get that warning which will make one doctest fail), not sure we can trigger their use iff they are installed to avoid this spurious warning
</li><li>as of now, if no name is provided when an extension field is trigerred and modulus is 'default' then it becomes 'conway' and that will potentially need the factorization (or the prime factors) of (p<sup>n - 1), which might not be a good idea, so i'd prefer to just look to raise an error as before, or at least trigger a warning.
</sup></li></ul>
TicketjpfloriMon, 18 Feb 2013 16:34:51 GMT
https://trac.sagemath.org/ticket/8335#comment:25
https://trac.sagemath.org/ticket/8335#comment:25
<p>
The problem with matrix2.pyx is with multiplying a matrix with coefficients living in Q with a matrix with elements in an extension field.
It seems the coercion model tries to put the second one in the prime subfield and fails with the "not in prime field" <a class="missing wiki">TypeError?</a>.
</p>
TicketjpfloriMon, 18 Feb 2013 16:50:06 GMT
https://trac.sagemath.org/ticket/8335#comment:26
https://trac.sagemath.org/ticket/8335#comment:26
<p>
This is caused by the "fix" I proposed before to return <a class="missing wiki">IntegerMod?</a>(1) for algebraic extension of <a class="missing wiki">IntegerMod?</a>(1), because now I feel a common parent is chosen as <a class="missing wiki">IntegerMod?</a>(1), but this is a prime field and the element from the extension field "cannot" be cast there.
</p>
<p>
A proper solution could be to investigate the infinite loop we get when the <a class="missing wiki">ArithmeticError?</a> is replaced with returning a unit when computing 0<sup>0.
Another solution might be to forbid extension of <a class="missing wiki">IntegerMod?</a>(1) so that we don't get crappy common parents.
</sup></p>
TicketjpfloriTue, 19 Feb 2013 18:05:58 GMT
https://trac.sagemath.org/ticket/8335#comment:27
https://trac.sagemath.org/ticket/8335#comment:27
<p>
I think I got the infinite loop.
</p>
<p>
During the initialization of the quotient ring, when trying to create the "one" element from the quotient ring of integer mod 1 quotiented by something, it tries to compute a remainder in polynomial_quotient_ring_element.py: "polynomial %= f" around line 137 but the mod operation is not defined for the Polynomial_ring_dense class, so this raises an <a class="missing wiki">AttributeError?</a> and falls back to the fallback implementation which tries to compute 0<sup>0 which now tries to create 1 which is looked up for at the position 1 of a table of precomputed value of length the modulus+1 = 1 which is surely non sense, fails to create a IntegerrMod_int and raises a <a class="missing wiki">TypeError?</a> which gets caught in polynomial_quotient_ring.py around line 430 and loops...
</sup></p>
TicketjpfloriTue, 19 Feb 2013 18:16:43 GMT
https://trac.sagemath.org/ticket/8335#comment:28
https://trac.sagemath.org/ticket/8335#comment:28
<p>
And of course if we return 0 (== 1) for 0<sup>0, then the generic quo_rem loops forever as we are computing 0 % 0 and the degree will never fall...
</sup></p>
TicketjpfloriWed, 20 Feb 2013 10:39:45 GMTdependencies set
https://trac.sagemath.org/ticket/8335#comment:29
https://trac.sagemath.org/ticket/8335#comment:29
<ul>
<li><strong>dependencies</strong>
set to <em>#13894</em>
</li>
</ul>
TicketjpfloriWed, 20 Feb 2013 16:08:47 GMT
https://trac.sagemath.org/ticket/8335#comment:30
https://trac.sagemath.org/ticket/8335#comment:30
<p>
Forget my rant about something becoming conway and having potential performance issues.
It only occurs if we have the conway polynomial precomputed, so no worries.
</p>
<p>
I've removed the code calling factor_cunningham unconditionally (or rather, not through an option as in finite_rings/element_base.pyx).
At some point this should get automatically triggered when cunningham tables are included (<a class="needs_work ticket" href="https://trac.sagemath.org/ticket/7240" title="enhancement: factorization of Cunningham numbers - applications (needs_work)">#7240</a>, <a class="needs_work ticket" href="https://trac.sagemath.org/ticket/12133" title="enhancement: New spkg for extended tables of prime factors (needs_work)">#12133</a>) and integer factorization is improved (<a class="needs_work ticket" href="https://trac.sagemath.org/ticket/12125" title="enhancement: Integer factoring improvements (needs_work)">#12125</a>, <a class="closed ticket" href="https://trac.sagemath.org/ticket/12117" title="enhancement: Bugfixes and improvements to Aurifeuillian factorization (closed: fixed)">#12117</a>), so calling factor_cunningham directly won't be that useful anyway.
</p>
TicketjpfloriThu, 21 Feb 2013 10:11:58 GMT
https://trac.sagemath.org/ticket/8335#comment:31
https://trac.sagemath.org/ticket/8335#comment:31
<p>
The doctests which changed were surely not caused by different randomness but because some checks in compute_pseudo_conway_polynomial were wrong, e.g. the results for next_prime(10000)<strong>11 was x<sup>11 + x + 7 whose root is not of order p</sup>11-1 but p<sup>11-1/2
</sup></strong></p>
TicketjpfloriThu, 21 Feb 2013 21:22:02 GMTattachment set
https://trac.sagemath.org/ticket/8335
https://trac.sagemath.org/ticket/8335
<ul>
<li><strong>attachment</strong>
set to <em>trac_8335-finite_field_coerce-5.7.b4.patch</em>
</li>
</ul>
TicketjpfloriThu, 21 Feb 2013 21:22:47 GMTdescription changed; work_issues set
https://trac.sagemath.org/ticket/8335#comment:32
https://trac.sagemath.org/ticket/8335#comment:32
<ul>
<li><strong>work_issues</strong>
set to <em>coercion madness</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/8335?action=diff&version=32">diff</a>)
</li>
</ul>
TicketjpfloriThu, 21 Feb 2013 21:25:06 GMTattachment set
https://trac.sagemath.org/ticket/8335
https://trac.sagemath.org/ticket/8335
<ul>
<li><strong>attachment</strong>
set to <em>trac_8335-pseudo_conway-5.7.b4.patch</em>
</li>
</ul>
TicketjpfloriThu, 21 Feb 2013 22:44:18 GMTattachment set
https://trac.sagemath.org/ticket/8335
https://trac.sagemath.org/ticket/8335
<ul>
<li><strong>attachment</strong>
set to <em>trac_8335-doc-5.7.b4.patch</em>
</li>
</ul>
TicketjpfloriFri, 22 Feb 2013 10:50:32 GMTattachment set
https://trac.sagemath.org/ticket/8335
https://trac.sagemath.org/ticket/8335
<ul>
<li><strong>attachment</strong>
set to <em>trac_8335-pseudo_conway-5.8.b0.patch</em>
</li>
</ul>
TicketjpfloriFri, 22 Feb 2013 10:50:47 GMTattachment set
https://trac.sagemath.org/ticket/8335
https://trac.sagemath.org/ticket/8335
<ul>
<li><strong>attachment</strong>
set to <em>trac_8335-finite_field_coerce-5.8.b0.patch</em>
</li>
</ul>
TicketjpfloriFri, 22 Feb 2013 10:54:33 GMTstatus, description changed; work_issues deleted
https://trac.sagemath.org/ticket/8335#comment:33
https://trac.sagemath.org/ticket/8335#comment:33
<ul>
<li><strong>status</strong>
changed from <em>needs_info</em> to <em>needs_review</em>
</li>
<li><strong>work_issues</strong>
<em>coercion madness</em> deleted
</li>
<li><strong>description</strong>
modified (<a href="/ticket/8335?action=diff&version=33">diff</a>)
</li>
</ul>
<p>
The patches should be quite ok now.
This needs 5.8.beta0, or at least > 5.7.beta4.
I've made quite a bit of changes to all the coercion stuff, so that definitely needs review.
With a minimal set of changes to sources files you can now create algebraic extensions of the Integers(1) and let it be considered as a quotient of a univariate poly ring, etc. and everything that came up when I was trying to rebase the patches.
In particular, now the modulus var of an <a class="missing wiki">AlgebraicExtensionFunctor?</a> is always a polynomial, but I've added an additional optional field named conway to encode the fact we're dealing with pseudo-conway extensions of ff.
</p>
<p>
Please test, rant, whatever!
</p>
TicketjpfloriFri, 22 Feb 2013 12:04:28 GMT
https://trac.sagemath.org/ticket/8335#comment:34
https://trac.sagemath.org/ticket/8335#comment:34
<p>
This passes "make ptestlong" on a usual x86_64 ubuntu 12.04.1.
</p>
TicketroedFri, 22 Feb 2013 12:05:52 GMT
https://trac.sagemath.org/ticket/8335#comment:35
https://trac.sagemath.org/ticket/8335#comment:35
<p>
Awesome! I will take a look this weekend.
</p>
TicketjpfloriFri, 22 Feb 2013 12:36:46 GMTattachment set
https://trac.sagemath.org/ticket/8335
https://trac.sagemath.org/ticket/8335
<ul>
<li><strong>attachment</strong>
set to <em>trac_8335-fixes-5.8.b0.2.patch</em>
</li>
</ul>
TicketjpfloriFri, 22 Feb 2013 12:37:14 GMT
https://trac.sagemath.org/ticket/8335#comment:36
https://trac.sagemath.org/ticket/8335#comment:36
<p>
Previous version was not qrefreshed...
</p>
TicketjpfloriFri, 22 Feb 2013 13:32:33 GMTattachment set
https://trac.sagemath.org/ticket/8335
https://trac.sagemath.org/ticket/8335
<ul>
<li><strong>attachment</strong>
set to <em>trac_8335-fixes-5.8.b0.patch</em>
</li>
</ul>
TicketjpfloriFri, 22 Feb 2013 13:32:51 GMT
https://trac.sagemath.org/ticket/8335#comment:37
https://trac.sagemath.org/ticket/8335#comment:37
<p>
Should really be ok now... sorry for the noise.
</p>
TicketSimonKingFri, 22 Feb 2013 17:21:31 GMTcc changed
https://trac.sagemath.org/ticket/8335#comment:38
https://trac.sagemath.org/ticket/8335#comment:38
<ul>
<li><strong>cc</strong>
<em>SimonKing</em> added
</li>
</ul>
TicketdefeoMon, 25 Feb 2013 18:27:29 GMT
https://trac.sagemath.org/ticket/8335#comment:39
https://trac.sagemath.org/ticket/8335#comment:39
<p>
Got the following failures
</p>
<pre class="wiki">sage -t -long devel/sage/sage/coding/code_constructions.py # 90 doctests failed
sage -t -long devel/sage/doc/en/thematic_tutorials/group_theory.rst # 1 doctests failed
sage -t -long devel/sage/sage/modular/arithgroup/arithgroup_perm.py # 1 doctests failed
sage -t -long devel/sage/sage/groups/matrix_gps/matrix_group.py # 1 doctests failed
sage -t -long devel/sage/sage/homology/examples.py # 7 doctests failed
</pre><p>
They seem unrelated, though, and disapperead upon second testing. I'll dig the code and try to give a review in the next weeks.
</p>
TicketsaraedumMon, 18 Mar 2013 06:54:20 GMTdescription changed
https://trac.sagemath.org/ticket/8335#comment:40
https://trac.sagemath.org/ticket/8335#comment:40
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/8335?action=diff&version=40">diff</a>)
</li>
</ul>
<p>
Apply trac_8335-pseudo_conway-5.8.b0.patch trac_8335-finite_field_coerce-5.8.b0.patch trac_8335-fixes-5.8.b0.patch
</p>
TicketzimmermaTue, 19 Mar 2013 13:12:29 GMTcc changed
https://trac.sagemath.org/ticket/8335#comment:41
https://trac.sagemath.org/ticket/8335#comment:41
<ul>
<li><strong>cc</strong>
<em>zimmerma</em> added
</li>
</ul>
TicketjpfloriMon, 13 May 2013 14:39:02 GMT
https://trac.sagemath.org/ticket/8335#comment:42
https://trac.sagemath.org/ticket/8335#comment:42
<p>
Did anyone actually had the time to look at this?
It would have been great to have that in Sage during the FLINT workshop last week to check some results using Sage rather than Magma.
</p>
<p>
I'm ok with what David initially did modulo what had to be fixed and that I hopefully fixed.
So what's left to do is to review the rebasing and changes I introduced.
Note that I did not check that the patches still cleanly apply, that may be an issue now.
</p>
TicketsaraedumMon, 13 May 2013 16:41:43 GMTreviewer set
https://trac.sagemath.org/ticket/8335#comment:43
https://trac.sagemath.org/ticket/8335#comment:43
<ul>
<li><strong>reviewer</strong>
set to <em>Jean-Pierre Flori</em>
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/8335#comment:42" title="Comment 42">jpflori</a>:
</p>
<blockquote class="citation">
<p>
Did anyone actually had the time to look at this?
</p>
</blockquote>
<p>
I started to look at it a while ago…
</p>
<blockquote class="citation">
<p>
So what's left to do is to review the rebasing and changes I introduced.
</p>
</blockquote>
<p>
That's good to know. I don't want to make any promises about reviewing this but I would certainly like to see this in sage. In any case, I won't review this in the next three weeks.
</p>
TicketjpfloriWed, 15 May 2013 14:48:33 GMT
https://trac.sagemath.org/ticket/8335#comment:44
https://trac.sagemath.org/ticket/8335#comment:44
<p>
Apart from fuzz 2, it still applies cleanly to 5.10.beta3 and all tests passes.
Not sure what the patchbot complains about, missing docstrings?
</p>
TicketjpfloriWed, 15 May 2013 14:49:45 GMTdescription, author changed
https://trac.sagemath.org/ticket/8335#comment:45
https://trac.sagemath.org/ticket/8335#comment:45
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/8335?action=diff&version=45">diff</a>)
</li>
<li><strong>author</strong>
changed from <em>David Roe</em> to <em>David Roe, Jean-Pierre Flori</em>
</li>
</ul>
TicketjpfloriWed, 15 May 2013 14:50:20 GMTattachment set
https://trac.sagemath.org/ticket/8335
https://trac.sagemath.org/ticket/8335
<ul>
<li><strong>attachment</strong>
set to <em>trac_8335-pseudo_conway-5.10.b3.patch</em>
</li>
</ul>
TicketsaraedumThu, 16 May 2013 13:13:47 GMT
https://trac.sagemath.org/ticket/8335#comment:46
https://trac.sagemath.org/ticket/8335#comment:46
<blockquote>
<p>
Apply trac_8335-pseudo_conway-5.8.b0.patch trac_8335-finite_field_coerce-5.8.b0.patch trac_8335-fixes-5.10.b3.patch
</p>
</blockquote>
TicketsaraedumThu, 16 May 2013 13:15:05 GMT
https://trac.sagemath.org/ticket/8335#comment:47
https://trac.sagemath.org/ticket/8335#comment:47
<p>
apply trac_8335-pseudo_conway-5.10.b3.patch trac_8335-finite_field_coerce-5.8.b0.patch trac_8335-fixes-5.8.b0.patch
</p>
TicketjpfloriTue, 04 Jun 2013 09:09:14 GMT
https://trac.sagemath.org/ticket/8335#comment:48
https://trac.sagemath.org/ticket/8335#comment:48
<p>
This definitely lacks "going down", e.g. taking the trace from a finite field to a subfield and being able to recognize that as an element of the subfield.
But let's keep that for another ticket.
</p>
TicketdefeoMon, 17 Jun 2013 16:45:48 GMTstatus, reviewer changed; keywords set
https://trac.sagemath.org/ticket/8335#comment:49
https://trac.sagemath.org/ticket/8335#comment:49
<ul>
<li><strong>keywords</strong>
<em>days49</em> added
</li>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_info</em>
</li>
<li><strong>reviewer</strong>
changed from <em>Jean-Pierre Flori</em> to <em>Jean-Pierre Flori, Luca De Feo</em>
</li>
</ul>
<p>
Hi,
</p>
<p>
The doc in <code>constructor.py</code> says
</p>
<pre class="wiki"> - ``modulus`` - blabla
- 'default': a Conway polynomial is used if in the database. Otherwise
a sparse polynomial is used for binary fields and a
random polynomial is used for other characteristics.
</pre><p>
but I got the impression that the default is to use pseudo-conway. By the way, is it reasonable to use pseudo-conway as default ? It is utterly slow !
</p>
<pre class="wiki">sage: %time k = GF(next_prime(100000)^2)
CPU times: user 16.41 s, sys: 0.05 s, total: 16.45 s
Wall time: 16.18 s
sage: %time l = GF(next_prime(100000)^3)
CPU times: user 60.19 s, sys: 0.07 s, total: 60.26 s
Wall time: 59.97 s
sage: %time (k.gen() + l.gen()).parent()
CPU times: user 0.08 s, sys: 0.00 s, total: 0.09 s
Wall time: 0.07 s
Finite Field in z6 of size 100003^6
</pre><p>
Compare this with Magma
</p>
<pre class="wiki">> time k := GF(NextPrime(100000)^2);
Time: 0.000
> time l := GF(NextPrime(100000)^3);
Time: 0.000
> time CommonOverfield(l, k);
Time: 0.030
</pre><p>
Wouldn't it be better to keep using <code></code>random<code></code> as default, and give error messages suggesting to use <code></code>conway<code></code> when the user tries to add/multiply/whatever two elements in different fields?
</p>
<p>
On another note, I get the following messages (I suppressed them from the output above for readability).
</p>
<pre class="wiki">sage: k = GF(next_prime(10000)^11)
*** Warning: Mod(a,b)^n with n >> b : wasteful.
*** Warning: Mod(a,b)^n with n >> b : wasteful.
*** Warning: Mod(a,b)^n with n >> b : wasteful.
*** Warning: Mod(a,b)^n with n >> b : wasteful.
*** Warning: Mod(a,b)^n with n >> b : wasteful.
*** Warning: Mod(a,b)^n with n >> b : wasteful.
*** Warning: Mod(a,b)^n with n >> b : wasteful.
*** Warning: Mod(a,b)^n with n >> b : wasteful.
*** Warning: Mod(a,b)^n with n >> b : wasteful.
*** Warning: Mod(a,b)^n with n >> b : wasteful.
*** Warning: Mod(a,b)^n with n >> b : wasteful.
*** Warning: Mod(a,b)^n with n >> b : wasteful.
*** Warning: Mod(a,b)^n with n >> b : wasteful.
*** Warning: Mod(a,b)^n with n >> b : wasteful.
</pre><p>
Any ideas on these?
</p>
TicketjpfloriMon, 17 Jun 2013 16:53:53 GMT
https://trac.sagemath.org/ticket/8335#comment:50
https://trac.sagemath.org/ticket/8335#comment:50
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/8335#comment:49" title="Comment 49">defeo</a>:
</p>
<blockquote class="citation">
<p>
Hi,
</p>
<p>
The doc in <code>constructor.py</code> says
</p>
<pre class="wiki"> - ``modulus`` - blabla
- 'default': a Conway polynomial is used if in the database. Otherwise
a sparse polynomial is used for binary fields and a
random polynomial is used for other characteristics.
</pre><p>
but I got the impression that the default is to use pseudo-conway. By the way, is it reasonable to use pseudo-conway as default ? It is utterly slow !
</p>
</blockquote>
<p>
It is and is expected to be.
</p>
<blockquote class="citation">
<pre class="wiki">sage: %time k = GF(next_prime(100000)^2)
CPU times: user 16.41 s, sys: 0.05 s, total: 16.45 s
Wall time: 16.18 s
sage: %time l = GF(next_prime(100000)^3)
CPU times: user 60.19 s, sys: 0.07 s, total: 60.26 s
Wall time: 59.97 s
sage: %time (k.gen() + l.gen()).parent()
CPU times: user 0.08 s, sys: 0.00 s, total: 0.09 s
Wall time: 0.07 s
Finite Field in z6 of size 100003^6
</pre><p>
Compare this with Magma
</p>
<pre class="wiki">> time k := GF(NextPrime(100000)^2);
Time: 0.000
> time l := GF(NextPrime(100000)^3);
Time: 0.000
> time CommonOverfield(l, k);
Time: 0.030
</pre></blockquote>
<p>
I think the rationale is that Sage did not support finite fields with unnamed generator before this patch.
So IIRC you could simply not do the above.
If you do something which used to work like
</p>
<pre class="wiki">K.<a> = GF(182918291829182918291892819)
</pre><p>
(assuming the random typing is some prime power)
I think it still picks up a random modulus as before (and is fast enough).
</p>
<p>
I agree it's kind of a bad thing to provide a new (but still natural, especially for Magma's users) way to create finite fields which is horribly slow.
So we might want to fix this.
</p>
<p>
Also note that this ticket only provides lattices for finite fields created with pseudo-conway polynomials.
The goal is not to provide (compatible) embeddings for all finite fields (as Magma is capable of).
</p>
<blockquote class="citation">
<p>
Wouldn't it be better to keep using <code></code>random<code></code> as default, and give error messages suggesting to use <code></code>conway<code></code> when the user tries to add/multiply/whatever two elements in different fields?
</p>
<p>
On another note, I get the following messages (I suppressed them from the output above for readability).
</p>
<pre class="wiki">sage: k = GF(next_prime(10000)^11)
*** Warning: Mod(a,b)^n with n >> b : wasteful.
*** Warning: Mod(a,b)^n with n >> b : wasteful.
*** Warning: Mod(a,b)^n with n >> b : wasteful.
*** Warning: Mod(a,b)^n with n >> b : wasteful.
*** Warning: Mod(a,b)^n with n >> b : wasteful.
*** Warning: Mod(a,b)^n with n >> b : wasteful.
*** Warning: Mod(a,b)^n with n >> b : wasteful.
*** Warning: Mod(a,b)^n with n >> b : wasteful.
*** Warning: Mod(a,b)^n with n >> b : wasteful.
*** Warning: Mod(a,b)^n with n >> b : wasteful.
*** Warning: Mod(a,b)^n with n >> b : wasteful.
*** Warning: Mod(a,b)^n with n >> b : wasteful.
*** Warning: Mod(a,b)^n with n >> b : wasteful.
*** Warning: Mod(a,b)^n with n >> b : wasteful.
</pre><p>
Any ideas on these?
</p>
</blockquote>
<p>
No idea, I'll check tomorrow.
</p>
TicketjpfloriTue, 18 Jun 2013 14:24:00 GMTattachment set
https://trac.sagemath.org/ticket/8335
https://trac.sagemath.org/ticket/8335
<ul>
<li><strong>attachment</strong>
set to <em>trac_8335-fixes-5.11.b1.2.patch</em>
</li>
</ul>
TicketjpfloriTue, 18 Jun 2013 14:32:09 GMTstatus, description changed
https://trac.sagemath.org/ticket/8335#comment:51
https://trac.sagemath.org/ticket/8335#comment:51
<ul>
<li><strong>status</strong>
changed from <em>needs_info</em> to <em>needs_review</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/8335?action=diff&version=51">diff</a>)
</li>
</ul>
<p>
There was some actual bug in the code which triggered the computation of the pseudo-Conway polynomials tree twice in the case where the extension degree was prime.
First the way it should, and then using the same arguments as in the case where this degree is not prime which at some point triggered the computation of the power of modular integer with a small modulus and a huge exponent and PARI rants when you do that;
just try
</p>
<pre class="wiki">Mod(3,5)._pari_()**28172187218728127182718271821982918291829182918291
</pre><p>
So the newly uploaded patch makes it so we only build the tree once as we always should have, and at least in Luca's example it prevents PARI rants to get on the screen.
</p>
TicketjpfloriTue, 18 Jun 2013 14:38:33 GMTstatus changed; work_issues set
https://trac.sagemath.org/ticket/8335#comment:52
https://trac.sagemath.org/ticket/8335#comment:52
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
<li><strong>work_issues</strong>
set to <em>pari_warn, assetion error</em>
</li>
</ul>
<p>
If you try
</p>
<pre class="wiki">GF(next_prime(10000)^12
</pre><p>
which is a non-prime extension you still get PARI's rants on-screen.
</p>
<p>
More worrying is that
</p>
<pre class="wiki">GF(next_prime(10000)^14)
</pre><p>
fails with an <a class="missing wiki">AssertionError?</a>.
</p>
TicketjpfloriTue, 18 Jun 2013 15:12:38 GMT
https://trac.sagemath.org/ticket/8335#comment:53
https://trac.sagemath.org/ticket/8335#comment:53
<p>
All these troubles seem to come from the _find_pow_of_frobenius function (the algo used inside and arguments passed to it).
</p>
TicketjpfloriTue, 18 Jun 2013 15:44:05 GMT
https://trac.sagemath.org/ticket/8335#comment:54
https://trac.sagemath.org/ticket/8335#comment:54
<p>
New patch which pushouts elements of two extension fields of same characteristic into the extension field with degree the lcm rather than the product as the old code used to do.
</p>
TicketjpfloriWed, 19 Jun 2013 12:24:25 GMT
https://trac.sagemath.org/ticket/8335#comment:55
https://trac.sagemath.org/ticket/8335#comment:55
<p>
Thanks to Luca I had a look at the math part of the algorithms implemented and am not sure about all of it.
In particular, after a quick look, it seems to me that all the _frobenius_shift part is useless and all that should be implemented is the algorithm form HL99 without the last loop checking that the polynomial is indeed minimal for some order (e.g. the one used for conway polynomials).
</p>
TicketjpfloriWed, 19 Jun 2013 20:58:12 GMT
https://trac.sagemath.org/ticket/8335#comment:56
https://trac.sagemath.org/ticket/8335#comment:56
<p>
I think I missed something in the algo so the above message is surely wrong, I need some more time...
</p>
TicketjpfloriThu, 20 Jun 2013 11:49:57 GMT
https://trac.sagemath.org/ticket/8335#comment:57
https://trac.sagemath.org/ticket/8335#comment:57
<p>
I had another look at the proofs in the paper and the _frobenius_shift stuff definitely seems to make sense (on top of the fact that without it everything is broken :)), due to the fact we use actual concrete representations of the fields whereas the algorithm is somehow more abstract.
</p>
<p>
So now we're back with the problems from <a class="ext-link" href="http://trac.sagemath.org/sage_trac/ticket/8335#comment:52"><span class="icon"></span>http://trac.sagemath.org/sage_trac/ticket/8335#comment:52</a>.
</p>
TicketjpfloriThu, 20 Jun 2013 11:57:34 GMT
https://trac.sagemath.org/ticket/8335#comment:58
https://trac.sagemath.org/ticket/8335#comment:58
<p>
This already fails with:
</p>
<pre class="wiki">find_pseudo_conway_polynomial_tree(5,6,False)
</pre>
TicketjpfloriThu, 20 Jun 2013 12:12:45 GMT
https://trac.sagemath.org/ticket/8335#comment:59
https://trac.sagemath.org/ticket/8335#comment:59
<p>
I think the problem is that we don't (or not anymore, there used to be two calls to the PCPT constructor before in the case where n is prime) ensure consistency of roots chosen for prime degree extension (basically running kind of _frobenius_shift when n is prime).
</p>
TicketjpfloriThu, 20 Jun 2013 12:19:56 GMT
https://trac.sagemath.org/ticket/8335#comment:60
https://trac.sagemath.org/ticket/8335#comment:60
<p>
That was easily fixed.
</p>
<p>
Note that
</p>
<pre class="wiki">find_pseudo_conway_polynomial_tree(11,14,False)
</pre><p>
seems to enter an infinite loop.
</p>
TicketjpfloriThu, 20 Jun 2013 13:04:49 GMT
https://trac.sagemath.org/ticket/8335#comment:61
https://trac.sagemath.org/ticket/8335#comment:61
<p>
Ok, it seems the main issue now is that nth_root is slow for big parameters (or make the range() function oveflow).
</p>
TicketjpfloriThu, 20 Jun 2013 13:11:49 GMT
https://trac.sagemath.org/ticket/8335#comment:62
https://trac.sagemath.org/ticket/8335#comment:62
<p>
The ovrflow happens because I wanted to let nth_root return all roots rather than just one as in David's code.
</p>
<p>
Using David's approach let the calculation for
</p>
<pre class="wiki">GF(next_prime(10000**14))
</pre><p>
finish (although we still get PARI's warnings but that's "not really" a problem).
</p>
TicketjpfloriThu, 20 Jun 2013 13:14:00 GMTstatus changed; work_issues deleted
https://trac.sagemath.org/ticket/8335#comment:63
https://trac.sagemath.org/ticket/8335#comment:63
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
<li><strong>work_issues</strong>
<em>pari_warn, assetion error</em> deleted
</li>
</ul>
<p>
Ok, the set of patch looks quite clean now, so back to needs_review.
</p>
<p>
The only thing not perfect is that we still get PARI's warning in some cases...
</p>
TicketjpfloriThu, 20 Jun 2013 13:18:53 GMTstatus changed
https://trac.sagemath.org/ticket/8335#comment:64
https://trac.sagemath.org/ticket/8335#comment:64
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
And back to needs_work, I did not check the doctests in the modified files.
</p>
TicketjpfloriThu, 20 Jun 2013 13:32:39 GMTstatus changed
https://trac.sagemath.org/ticket/8335#comment:65
https://trac.sagemath.org/ticket/8335#comment:65
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
<p>
Should be ok now.
Reverted David's test for primitivity rather than using is_primitive which would waste a lot of time factoring over and over q = p<strong>n -1.
</strong></p>
TicketjpfloriThu, 20 Jun 2013 13:35:56 GMTdescription, summary changed
https://trac.sagemath.org/ticket/8335#comment:66
https://trac.sagemath.org/ticket/8335#comment:66
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/8335?action=diff&version=66">diff</a>)
</li>
<li><strong>summary</strong>
changed from <em>Finite Field lattices</em> to <em>Finite Field lattices for (pseudo-)Conway polynomials</em>
</li>
</ul>
TicketjpfloriThu, 20 Jun 2013 13:54:04 GMT
https://trac.sagemath.org/ticket/8335#comment:67
https://trac.sagemath.org/ticket/8335#comment:67
<p>
(Small fix to a silly typo)
</p>
TicketjpfloriThu, 20 Jun 2013 15:43:51 GMT
https://trac.sagemath.org/ticket/8335#comment:68
https://trac.sagemath.org/ticket/8335#comment:68
<p>
Added some doctests hopefully showing that embeddings are correct and compatible.
</p>
TicketjpfloriThu, 20 Jun 2013 17:23:38 GMT
https://trac.sagemath.org/ticket/8335#comment:69
https://trac.sagemath.org/ticket/8335#comment:69
<p>
Ok, the last tests I added:
</p>
<pre class="wiki">
sage: old_exists_cp = sage.rings.finite_rings.constructor.exists_conway_polynomial
sage: sage.rings.finite_rings.constructor.exists_conway_polynomial = lambda p, n: False
sage: k = GF(3**10)
sage: l = GF(3**20)
sage: k.modulus() == conway_polynomial(3, 10)
False
sage: l(k.gen()**10) == l(k.gen())**10
True
sage: del k, l
sage: import gc
sage: gc.collect();
sage: sage.rings.finite_rings.constructor.exists_conway_polynomial = old_exists_cp
</pre><p>
introduced some failures in the test:
</p>
<pre class="wiki">sage: GF.other_keys(key, K)
[(9, ('a',), x^2 + 2*x + 2, None, '{}', 3, 2, True),
(9, ('a',), x^2 + 2*x + 2, 'givaro', '{}', 3, 2, True)]
</pre><p>
Indeed, although I explicitely asked to delete k and l and restored a proper exists_... function, the field GF(3<strong>20) stay cached and so the pseudo-Conway, but not Conway, modulus used to build GF(3</strong>2).
</p>
<p>
The reason for that is that we performed arithmetic on elements of k and l which triggered creation of an embedding of k into l which prevents the collection of k and l.
This is bad and is surely the same problem as in <a class="closed ticket" href="https://trac.sagemath.org/ticket/14711" title="defect: Weak references in the coercion graph (closed: fixed)">#14711</a>.
</p>
<p>
So I just removed the hack forcing the use of pseudo-Conway polynomials.
</p>
TicketjpfloriThu, 20 Jun 2013 17:25:11 GMTattachment set
https://trac.sagemath.org/ticket/8335
https://trac.sagemath.org/ticket/8335
<ul>
<li><strong>attachment</strong>
set to <em>trac_8335-fixes-5.11.b1.patch</em>
</li>
</ul>
TicketcarusoWed, 26 Jun 2013 08:24:43 GMTcc changed
https://trac.sagemath.org/ticket/8335#comment:70
https://trac.sagemath.org/ticket/8335#comment:70
<ul>
<li><strong>cc</strong>
<em>caruso</em> added
</li>
</ul>
TicketpbruinWed, 26 Jun 2013 10:27:34 GMTcc changed
https://trac.sagemath.org/ticket/8335#comment:71
https://trac.sagemath.org/ticket/8335#comment:71
<ul>
<li><strong>cc</strong>
<em>pbruin</em> added
</li>
</ul>
<p>
In relation to <a class="closed ticket" href="https://trac.sagemath.org/ticket/12142" title="enhancement: Speed up PARI finite field operations (closed: fixed)">#12142</a>, I am currently working on a patch that makes the construction of irreducible polynomials independent of the finite field implementations (prime_modn, givaro, ntl_gf2e, ext_pari and the future pari_ffelt). Currently every finite field implementation has to do its own parsing of string values of modulus (like 'conway', 'random' etc.). It would be more elegant to handle all these string values in the generic constructor, and always pass an actual polynomial to the finite field implementation.
</p>
<p>
In the current version of Sage, the only situation in which the implementation needs to know whether the field is defined by a Conway polynomial is when converting elements to GAP. This means that always passing a polynomial as the modulus is fine, as long as one can check if the polynomial is a Conway polynomial if and when it is needed. This is easy to do by checking the database.
</p>
<p>
With your patch, each implementation gets an increased dependence on string values for the modulus parameter. I am wondering if this can be avoided by doing all the pseudo-Conway related stuff inside the generic finite field code.
</p>
<p>
[...to be continued...]
</p>
TicketjpfloriWed, 26 Jun 2013 10:35:48 GMT
https://trac.sagemath.org/ticket/8335#comment:72
https://trac.sagemath.org/ticket/8335#comment:72
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/8335#comment:71" title="Comment 71">pbruin</a>:
</p>
<blockquote class="citation">
<p>
In relation to <a class="closed ticket" href="https://trac.sagemath.org/ticket/12142" title="enhancement: Speed up PARI finite field operations (closed: fixed)">#12142</a>, I am currently working on a patch that makes the construction of irreducible polynomials independent of the finite field implementations (prime_modn, givaro, ntl_gf2e, ext_pari and the future pari_ffelt). Currently every finite field implementation has to do its own parsing of string values of modulus (like 'conway', 'random' etc.). It would be more elegant to handle all these string values in the generic constructor, and always pass an actual polynomial to the finite field implementation.
</p>
<p>
In the current version of Sage, the only situation in which the implementation needs to know whether the field is defined by a Conway polynomial is when converting elements to GAP. This means that always passing a polynomial as the modulus is fine, as long as one can check if the polynomial is a Conway polynomial if and when it is needed. This is easy to do by checking the database.
</p>
</blockquote>
<p>
Beware that the last patch which contains my modification to the two original patches by David changes quite a lot of thing.
In particular, I think that with it modulus contains the real modulus as well and I use additional attributes to check for pseudo-Conway construction.
</p>
<p>
Also note that the real nice addition of this patch is mainly the compatible embeddings.
Indeed, for practical purposes, it seems that only the Conway polynomials from the databse will be used.
Constructing pseudo-Conway polynomials is quite as slow as contructions genuine Conway polynomials so when you will actually use them, i.e. for quite large parameters because you have to be outside of the Conway database, it will already be quite slow and unpractical.
</p>
<blockquote class="citation">
<p>
With your patch, each implementation gets an increased dependence on string values for the modulus parameter. I am wondering if this can be avoided by doing all the pseudo-Conway related stuff inside the generic finite field code.
</p>
<p>
[...to be continued...]
</p>
</blockquote>
TicketpbruinWed, 26 Jun 2013 12:16:44 GMT
https://trac.sagemath.org/ticket/8335#comment:73
https://trac.sagemath.org/ticket/8335#comment:73
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/8335#comment:72" title="Comment 72">jpflori</a>:
</p>
<blockquote class="citation">
<p>
Beware that the last patch which contains my modification to the two original patches by David changes quite a lot of thing.
In particular, I think that with it modulus contains the real modulus as well and I use additional attributes to check for pseudo-Conway construction.
</p>
</blockquote>
<p>
OK, I'll try to find out if and how my ideas about making the choice of polynomial independently of the finite field implementation can be harmonised with your patch. At first sight there does not seem to be a huge clash. I am mostly worried about the use of strings like 'conwayz' as a modulus, which really seems to be overloading this parameter too much.
</p>
<blockquote class="citation">
<p>
Also note that the real nice addition of this patch is mainly the compatible embeddings.
</p>
</blockquote>
<p>
I agree that this is a very desirable thing to have, and it is also nice to be able to simply type <code></code>F = GF(p<sup>n</sup>)<code></code> without having to care about variable names and embeddings. I do think it is good to think carefully about how exactly to accomplish this.
</p>
<p>
In particular, I am not sure if it is wise to say in the documentation/specification that this compatibility is achieved using (pseudo-)Conway polynomials, since different implementations are imaginable. I am thinking of the standard models for finite fields by Lenstra and de Smit, which are constructed in a way that does not seem to be related to Conway polynomials.
</p>
<p>
From a conceptual point of view, it is desirable that GF(p<sup>n</sup>) without any arguments should refer to the unique subfield of cardinality p<sup>n</sup> <em>inside a chosen algebraic closure</em> of GF(p). This gives 'compatible embeddings' the very simple meaning of 'inclusions within an algebraic closure'.
</p>
<p>
Such an algebraic closure could be implemented in different ways, for example via (pseudo-)Conway polynomials; algebraic closures of GF(p) resulting from different methods would be non-canonically isomorphic. There might be a default choice that could change in the future, and the user should be able to specify which algebraic closure should be taken.
</p>
<p>
Here is how I would hope a hypothetical future Sage session to look like:
</p>
<pre class="wiki">sage: p = 5
sage: Fpbar = GF(p).algebraic_closure()
sage: Fpbar
Algebraic closure of Finite Field of size 5
sage: Fa = GF(p^2, 'a')
sage: Fa
Finite field in a of size 5^2
sage: is_subfield(Fa, Fpbar)
False
sage: Fb = GF(p^2)
Subfield of size 5^2 of Algebraic closure of Finite Field of size 5
sage: is_subfield(Fb, Fpbar)
True
sage: type(Fpbar)
<class 'sage.rings.AlgebraicClosureFiniteField_pseudo_conway'>
</pre><p>
Would something like this be easy to achieve once this ticket has been implemented?
</p>
TicketjpfloriWed, 26 Jun 2013 12:58:23 GMT
https://trac.sagemath.org/ticket/8335#comment:74
https://trac.sagemath.org/ticket/8335#comment:74
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/8335#comment:73" title="Comment 73">pbruin</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/8335#comment:72" title="Comment 72">jpflori</a>:
</p>
<blockquote class="citation">
<p>
Beware that the last patch which contains my modification to the two original patches by David changes quite a lot of thing.
In particular, I think that with it modulus contains the real modulus as well and I use additional attributes to check for pseudo-Conway construction.
</p>
</blockquote>
<p>
OK, I'll try to find out if and how my ideas about making the choice of polynomial independently of the finite field implementation can be harmonised with your patch. At first sight there does not seem to be a huge clash. I am mostly worried about the use of strings like 'conwayz' as a modulus, which really seems to be overloading this parameter too much.
</p>
<blockquote class="citation">
<p>
Also note that the real nice addition of this patch is mainly the compatible embeddings.
</p>
</blockquote>
<p>
I agree that this is a very desirable thing to have, and it is also nice to be able to simply type <code></code>F = GF(p<sup>n</sup>)<code></code> without having to care about variable names and embeddings. I do think it is good to think carefully about how exactly to accomplish this.
</p>
</blockquote>
<p>
Agreed.
But it just happened I stumled upon this ticket which already looked usable (and was two years old) and thought "oh, let's already get this in; later on we can design better constructions of compatible embeddings and get something more general and fast".
So I decided to postpone the design of a cool and fast system in <a class="new ticket" href="https://trac.sagemath.org/ticket/8751" title="defect: conversion between non-prime finite fields (new)">#8751</a> and only deal with "lattices using (pseudo) Conway polynomials" here.
It's better to have something than nothing.
</p>
<blockquote class="citation">
<p>
In particular, I am not sure if it is wise to say in the documentation/specification that this compatibility is achieved using (pseudo-)Conway polynomials, since different implementations are imaginable. I am thinking of the standard models for finite fields by Lenstra and de Smit, which are constructed in a way that does not seem to be related to Conway polynomials.
</p>
</blockquote>
<p>
I completely agree that using Conway polynomials is a no go as soon as you quit fields of small cardinalities.
I've met Eric Rains who participated in the Magma implementation (or at least the algos behind it) and he was nice enough to share with me a draft describing the algos used.
</p>
<p>
De Feo and Schost and others are also producing nice paper on how to build p- or l-adic towers of finite fields.
What is very nice is that they avoid linear algebra (what Magma may not completely do).
</p>
<blockquote class="citation">
<p>
From a conceptual point of view, it is desirable that GF(p<sup>n</sup>) without any arguments should refer to the unique subfield of cardinality p<sup>n</sup> <em>inside a chosen algebraic closure</em> of GF(p). This gives 'compatible embeddings' the very simple meaning of 'inclusions within an algebraic closure'.
</p>
<p>
Such an algebraic closure could be implemented in different ways, for example via (pseudo-)Conway polynomials; algebraic closures of GF(p) resulting from different methods would be non-canonically isomorphic. There might be a default choice that could change in the future, and the user should be able to specify which algebraic closure should be taken.
</p>
</blockquote>
<p>
I agree, so it makes sense to have a pseudo Conway implementation and other ones later.
</p>
<blockquote class="citation">
<p>
Here is how I would hope a hypothetical future Sage session to look like:
</p>
<pre class="wiki">sage: p = 5
sage: Fpbar = GF(p).algebraic_closure()
sage: Fpbar
Algebraic closure of Finite Field of size 5
sage: Fa = GF(p^2, 'a')
sage: Fa
Finite field in a of size 5^2
sage: is_subfield(Fa, Fpbar)
False
sage: Fb = GF(p^2)
Subfield of size 5^2 of Algebraic closure of Finite Field of size 5
sage: is_subfield(Fb, Fpbar)
True
sage: type(Fpbar)
<class 'sage.rings.AlgebraicClosureFiniteField_pseudo_conway'>
</pre><p>
Would something like this be easy to achieve once this ticket has been implemented?
</p>
</blockquote>
TicketpbruinWed, 26 Jun 2013 13:08:10 GMT
https://trac.sagemath.org/ticket/8335#comment:75
https://trac.sagemath.org/ticket/8335#comment:75
<p>
I started to look at the patches, but was immediately struck by a problem that has nothing to do with finite fields. In <code>QuotientFunctor._apply_functor</code>, the functor R -> R/IR (where I is an ideal of the base ring) to arbitrary rings. This makes perfect sense for any R; you just happen to get the zero ring when IR = R. The existing behaviour is certainly correct (although it is debatable whether the zero ring should be represented as <code>Integers(1)</code>). Why would you want to raise an exception if R is a field?
</p>
TicketjpfloriWed, 26 Jun 2013 13:18:23 GMT
https://trac.sagemath.org/ticket/8335#comment:76
https://trac.sagemath.org/ticket/8335#comment:76
<p>
I think it was the historical Sage behavior until some recent ticket (don't really remember, you should be able to devise which one by looking at the hg log).
</p>
<p>
I also agree returning the zero ring would be a better thing to do.
But then it breaks a bunch of generic constructions in Sage such as polynomial rings over <a class="missing report" title="report does not exist">{0}</a> and quotients of it...
See <a class="ext-link" href="http://trac.sagemath.org/sage_trac/ticket/8335#comment:24"><span class="icon"></span>http://trac.sagemath.org/sage_trac/ticket/8335#comment:24</a> and the few following comments (in case you manage to make some sense of my lonely rants).
</p>
TicketpbruinWed, 26 Jun 2013 13:35:57 GMT
https://trac.sagemath.org/ticket/8335#comment:77
https://trac.sagemath.org/ticket/8335#comment:77
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/8335#comment:76" title="Comment 76">jpflori</a>:
</p>
<blockquote class="citation">
<p>
I think it was the historical Sage behavior until some recent ticket (don't really remember, you should be able to devise which one by looking at the hg log).
</p>
</blockquote>
<p>
In the comments it says that the behaviour used to be to return the integer 0 (?!), and that this was corrected in <a class="closed ticket" href="https://trac.sagemath.org/ticket/9138" title="defect: Categories for all rings (closed: fixed)">#9138</a>. Now that the current implementation is correct, it would be very bad to change something fundamental like this just to make new patches work.
</p>
<blockquote class="citation">
<p>
I also agree returning the zero ring would be a better thing to do.
But then it breaks a bunch of generic constructions in Sage such as polynomial rings over <a class="missing report" title="report does not exist">{0}</a> and quotients of it...
See <a class="ext-link" href="http://trac.sagemath.org/sage_trac/ticket/8335#comment:24"><span class="icon"></span>http://trac.sagemath.org/sage_trac/ticket/8335#comment:24</a> and the few following comments (in case you manage to make some sense of my lonely rants).
</p>
</blockquote>
<p>
Then it seems to me that the generic constructions should be fixed. Until then, any new code should take care that it does not use these constructions in cases where they fail.
</p>
TicketjpfloriWed, 26 Jun 2013 14:04:53 GMT
https://trac.sagemath.org/ticket/8335#comment:78
https://trac.sagemath.org/ticket/8335#comment:78
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/8335#comment:77" title="Comment 77">pbruin</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/8335#comment:76" title="Comment 76">jpflori</a>:
</p>
<blockquote class="citation">
<p>
I think it was the historical Sage behavior until some recent ticket (don't really remember, you should be able to devise which one by looking at the hg log).
</p>
</blockquote>
<p>
In the comments it says that the behaviour used to be to return the integer 0 (?!), and that this was corrected in <a class="closed ticket" href="https://trac.sagemath.org/ticket/9138" title="defect: Categories for all rings (closed: fixed)">#9138</a>. Now that the current implementation is correct, it would be very bad to change something fundamental like this just to make new patches work.
</p>
<blockquote class="citation">
<p>
I also agree returning the zero ring would be a better thing to do.
But then it breaks a bunch of generic constructions in Sage such as polynomial rings over <a class="missing report" title="report does not exist">{0}</a> and quotients of it...
See <a class="ext-link" href="http://trac.sagemath.org/sage_trac/ticket/8335#comment:24"><span class="icon"></span>http://trac.sagemath.org/sage_trac/ticket/8335#comment:24</a> and the few following comments (in case you manage to make some sense of my lonely rants).
</p>
</blockquote>
<p>
Then it seems to me that the generic constructions should be fixed. Until then, any new code should
</p>
</blockquote>
<p>
take care that it does not use these constructions in cases where they fail.
Of course.
But avoiding the coercion model is not that easy.
</p>
<p>
I'll give it a shot, but I cannot promise to come up with anything working.
Obviously I would have done that earlier if it was really easy.
</p>
TicketjpfloriWed, 26 Jun 2013 16:00:39 GMT
https://trac.sagemath.org/ticket/8335#comment:79
https://trac.sagemath.org/ticket/8335#comment:79
<p>
In fact I think that putting back the correct behavior gives no problems and I added all needed fixes to make it work.
</p>
<p>
The real problem was that the quotient functor was applied before the fraction field one or the other way around and you always ended up working in the trivial ring.
So the easy way was raising an error.
But now the functors are applied in a more sensible it should not be a problem.
</p>
<p>
I'll upload a fixed patch when I make sure no tests fail.
</p>
TicketjpfloriWed, 26 Jun 2013 16:13:03 GMTattachment set
https://trac.sagemath.org/ticket/8335
https://trac.sagemath.org/ticket/8335
<ul>
<li><strong>attachment</strong>
set to <em>trac_8335-fixes-5.11.b3.patch</em>
</li>
</ul>
TicketjpfloriWed, 26 Jun 2013 16:14:24 GMT
https://trac.sagemath.org/ticket/8335#comment:80
https://trac.sagemath.org/ticket/8335#comment:80
<p>
I have some failing tests on top of 5.11.b3 but they seem completely unrelated (something with get_test_shell() and I did not test a vanilla install, so they were surely there without these patches).
</p>
TicketpbruinWed, 26 Jun 2013 16:44:49 GMT
https://trac.sagemath.org/ticket/8335#comment:81
https://trac.sagemath.org/ticket/8335#comment:81
<p>
Continuing the discussion from <a class="closed ticket" href="https://trac.sagemath.org/ticket/13214" title="enhancement: Finite field homomorphisms and Frobenius endomorphisms (closed: fixed)">#13214</a>; in the context of my remark
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
there should probably be two categories into which a finite field can be put:
</p>
<ul><li>the category of all finite fields. In this category, between any two objects there are either several morphisms or none at all, but no canonical one.
</li><li>the category of finite subfields of a given algebraic closure of Fp. In this category there is at most one morphism beteen any two objects, namely the inclusion qua subfields of the given algebraic closure.
</li></ul></blockquote>
</blockquote>
<p>
Jean-Pierre Flori wrote (referring to the second option)
</p>
<blockquote class="citation">
<p>
<a class="closed ticket" href="https://trac.sagemath.org/ticket/8335" title="enhancement: Finite field lattices via Conway polynomials (closed: fixed)">#8335</a> provides such an imlementation, though it not really practical for large fields and there is no proper categorical framework as you suggest.
This framework could be implemented in an independent ticket (and should if we want to be able to merge some tickets in a finite amount of time).
</p>
</blockquote>
<p>
Certainly; both this ticket and <a class="closed ticket" href="https://trac.sagemath.org/ticket/13214" title="enhancement: Finite field homomorphisms and Frobenius endomorphisms (closed: fixed)">#13214</a> are already large enough. The question is whether (a draft of) a categorical framework (i.e. algebraic closure of <strong>F</strong><sub><em>p</em></sub>) should be made first, or whether the new code from this ticket should be inserted into the current framework (which implements the first of the two categories) and be moved to a new framework as soon as we have it.
</p>
<p>
I would personally prefer the first option to keep things better packaged; this patch seems to make (pseudo-)Conway polynomials pop up in many different places, and moving them all to one place would require another intrusive Trac ticket later.
</p>
TicketjpfloriWed, 26 Jun 2013 17:11:57 GMT
https://trac.sagemath.org/ticket/8335#comment:82
https://trac.sagemath.org/ticket/8335#comment:82
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/8335#comment:81" title="Comment 81">pbruin</a>:
</p>
<blockquote class="citation">
<p>
I would personally prefer the first option to keep things better packaged; this patch seems to make (pseudo-)Conway polynomials pop up in many different places, and moving them all to one place would require another intrusive Trac ticket later.
</p>
</blockquote>
<p>
As far as functionalities are concerned, remember that Sage currently does not support
</p>
<pre class="wiki">K = GF(p^n)
</pre><p>
So pseudo Conway polynomials never appear where they did not use to.
If you issue the command line which is currently supported:
</p>
<pre class="wiki">K.<a> = GF(p^n)
</pre><p>
you will get the exact same behavior as before, unless he specifies modulus="conway" and wants an extension of too large cardinality; maybe that should be changed back.
</p>
<p>
Nevertheless I agree that a user coming from Magma where
</p>
<pre class="wiki">K := GF(p, n);
</pre><p>
works might be confused...
Though the user might although expect embeddings of finite fields to work out of the box.
</p>
<p>
But as I just realized I guess your concern is about the dissemination of code.
From what I see, apart from code in finite_field_base.py, changes to specific finite field implementations mostly consists in replacing the part about Conway polynomials and tweak it to work with pseudo-Conway ones as well.
Nonetheless it's true that properly moving all of that later will be intrusive.
</p>
<p>
But what about plain Conway polynomials? Shouldn't that be moved as well?
Or do we consider they are standard enough to belong in the <a class="missing wiki">FiniteFields?</a>() category?
But if they do it would be a waste not to use automagically the fact that they provide simple embeddings into each other, wouldn't it? though it would make the separation between the plain finite fields and subfields of a given algebraic closure blurrier.
</p>
<p>
(As you can guess, I'd prefer to get this merged first especially because I hate seeing functional code bitrotting for years on trac, but I get your point :))
</p>
TicketpbruinWed, 26 Jun 2013 23:20:33 GMT
https://trac.sagemath.org/ticket/8335#comment:83
https://trac.sagemath.org/ticket/8335#comment:83
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/8335#comment:82" title="Comment 82">jpflori</a>:
</p>
<blockquote class="citation">
<p>
As far as functionalities are concerned, remember that Sage currently does not support
</p>
<pre class="wiki">K = GF(p^n)
</pre><p>
So pseudo Conway polynomials never appear where they did not use to.
If you issue the command line which is currently supported:
</p>
<pre class="wiki">K.<a> = GF(p^n)
</pre><p>
you will get the exact same behavior as before, unless he specifies modulus="conway" and wants an extension of too large cardinality; maybe that should be changed back.
</p>
</blockquote>
<p>
Deciding what exactly <code>GF(p^n)</code> should mean (if it should mean anything at all) is an important design decision, and it is not at all obvious that Sage should make the same choice as Magma. Probably it is better not to make this decision in this ticket, which already adds a lot of code. Besides, letting an important change of behaviour depend whether the user specify a variable name or not sounds like a risky idea.
</p>
<blockquote class="citation">
<p>
But what about plain Conway polynomials? Shouldn't that be moved as well?
Or do we consider they are standard enough to belong in the <a class="missing wiki">FiniteFields?</a>() category?
</p>
</blockquote>
<p>
They certainly belong to the general finite fields code, but not in any specific implementation, in my opinion. In fact, the goal of the (by now 2) patches that I'm about to post is as follows:
</p>
<ul><li>write a method <code>PolynomialRing_dense_finite_field.irreducible_element</code> (somewhat surprisingly the class did not exist yet) to generate an irreducible polynomial in that polynomial ring, allowing the user to optionally specify an algorithm (Adleman-Lenstra, Conway, random, lexicographically first, sparse);
</li></ul><ul><li>modify the <code>FiniteField</code> constructor to call this algorithm if the <code>modulus</code> argument is a string or <code>None</code>, and always pass an actual polynomial to the implementation class.
</li></ul><p>
For backward compatibility (unpickling), the existing implementations will continue to accept string values for the parameter <code>modulus</code>, but new ones (such as the new PARI interface, see <a class="closed ticket" href="https://trac.sagemath.org/ticket/12142" title="enhancement: Speed up PARI finite field operations (closed: fixed)">#12142</a>) won't have to. The idea is that the specific implementations should "concentrate on doing their job", and things related to magic values of <code>modulus</code> should be in only one place.
</p>
<blockquote class="citation">
<p>
But if they do it would be a waste not to use automagically the fact that they provide simple embeddings into each other, wouldn't it?
</p>
</blockquote>
<p>
As I see it, that should depend on whether you are in the category of all finite fields or in the category of subfields of an algebraic closure of <strong>F</strong><sub><em>p</em></sub>.
</p>
<blockquote class="citation">
<p>
(As you can guess, I'd prefer to get this merged first especially because I hate seeing functional code bitrotting for years on trac, but I get your point :))
</p>
</blockquote>
<p>
Of course I understand that you want to see this finally appear in Sage, and I agree that it is a shame that Sage could have had something like this for years and still doesn't. I guess it will be easier if this big ticket is split into smaller pieces. It tries to do many rather different things at once: implement pseudo-Conway polynomials, adapt the construction of finite fields to use these, implement automatic coercion between the resulting fields, give a meaning to <code>GF(p^n)</code>, and in the process add some new methods to polynomial elements. This makes it harder than necessary to understand and to review.
</p>
TicketdefeoThu, 27 Jun 2013 02:55:43 GMT
https://trac.sagemath.org/ticket/8335#comment:84
https://trac.sagemath.org/ticket/8335#comment:84
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/8335#comment:83" title="Comment 83">pbruin</a>:
</p>
<p>
This discussion looks like the dear old dichotomy between quick feature integration and long specification design.
</p>
<p>
Having some kind of support for lattices of finite fields has been a long standing request. I agree with pbruin that a better interface between generic finite fields and their actual implementation would be beneficial. But this ticket is ready for review, while pbruin's is not. Would it be that hard to adapt pbruin's or any other interface if this ticket is merged? I'm willing to give positive review to this ticket, if it stands some more testing, and it doesn't mess too much with <a class="closed ticket" href="https://trac.sagemath.org/ticket/12142" title="enhancement: Speed up PARI finite field operations (closed: fixed)">#12142</a>.
</p>
<p>
I'm not convinced that the interface can be decided independently of the actual algorithms. Magma's interface is engineered around the fact that constructing fields is fast, but constructing the embeddings is slow (hence the Embed function, which must explicitly be called by the user). If Sage ends up having a different construction (e.g., De Smit-Lenstra lattices... although I've looked into it, and I don't think it is viable in general), I think the interface could be different.
</p>
<p>
There are many solutions to the compatibly embedded finite fields problem, no one being ideal. I'm more in favor of seeing them emerge in parallel, being developed in different tickets under different namespaces and APIs, rather than fixing the API now, and than realizing that it needs to be amended. Once a construction clearly stands out, then we can thrash it upon the user as the default <code></code>GF(p<sup>n</sup>)<code></code> construction (ok, this ticket is already thrashing, but it has the merit of being the first one!).
</p>
TicketpbruinThu, 27 Jun 2013 07:56:50 GMT
https://trac.sagemath.org/ticket/8335#comment:85
https://trac.sagemath.org/ticket/8335#comment:85
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/8335#comment:84" title="Comment 84">defeo</a>:
</p>
<blockquote class="citation">
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/8335#comment:83" title="Comment 83">pbruin</a>:
</p>
<p>
This discussion looks like the dear old dichotomy between quick feature integration and long specification design.
</p>
</blockquote>
<p>
Not quite; I am not at all advocating long specification design, and quick integration of new features (which I am all for) is in fact easier if they are smaller and don't intrude in places where they don't have to.
</p>
<blockquote class="citation">
<p>
Having some kind of support for lattices of finite fields has been a long standing request. I agree with pbruin that a better interface between generic finite fields and their actual implementation would be beneficial. But this ticket is ready for review, while pbruin's is not.
</p>
</blockquote>
<p>
The part that is relevant for this ticket is now ready for review: see <a class="closed ticket" href="https://trac.sagemath.org/ticket/14832" title="enhancement: Unified construction of irreducible polynomials over finite fields (closed: fixed)">#14832</a> and <a class="closed ticket" href="https://trac.sagemath.org/ticket/14833" title="enhancement: Make choosing irreducible polynomials independent of finite field ... (closed: fixed)">#14833</a>.
</p>
<blockquote class="citation">
<p>
Would it be that hard to adapt pbruin's or any other interface if this ticket is merged? I'm willing to give positive review to this ticket, if it stands some more testing, and it doesn't mess too much with <a class="closed ticket" href="https://trac.sagemath.org/ticket/12142" title="enhancement: Speed up PARI finite field operations (closed: fixed)">#12142</a>.
</p>
</blockquote>
<p>
I am actually in favour of quickly solving the main things that this ticket does (implementing pseudo-Conway polynomials and coercion between different finite fields). I just think it shouldn't add more code to the finite fields implementations (Givaro, PARI etc.), and should not (or at least not yet) fix a meaning for <code>GF(p^n)</code>.
</p>
TicketjpfloriThu, 27 Jun 2013 08:11:41 GMTstatus changed; work_issues set
https://trac.sagemath.org/ticket/8335#comment:86
https://trac.sagemath.org/ticket/8335#comment:86
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
<li><strong>work_issues</strong>
set to <em>rebase</em>
</li>
</ul>
<p>
Ok, so I'll be the nice guy and try to rebase this ticket on top of your tickets.
</p>
TicketpbruinSat, 13 Jul 2013 21:05:09 GMTkeywords changed
https://trac.sagemath.org/ticket/8335#comment:87
https://trac.sagemath.org/ticket/8335#comment:87
<ul>
<li><strong>keywords</strong>
<em>sd51</em> added
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/8335#comment:86" title="Comment 86">jpflori</a>:
</p>
<blockquote class="citation">
<p>
Ok, so I'll be the nice guy and try to rebase this ticket on top of your tickets.
</p>
</blockquote>
<p>
Wonderful; these (<a class="closed ticket" href="https://trac.sagemath.org/ticket/12142" title="enhancement: Speed up PARI finite field operations (closed: fixed)">#12142</a> and dependencies, maybe also <a class="closed ticket" href="https://trac.sagemath.org/ticket/14888" title="enhancement: Make FiniteField_pari_ffelt the default for generic finite fields (closed: fixed)">#14888</a>) should now be fairly stable.
</p>
TicketjpfloriThu, 18 Jul 2013 14:18:26 GMT
https://trac.sagemath.org/ticket/8335#comment:88
https://trac.sagemath.org/ticket/8335#comment:88
<p>
I've begun rebasing, cleaning and splitting in a better way the patches here.
</p>
<p>
I have one question: in several finite field constructors based on a given implementation (let's say FiniteField_givaro), you can still pass the "modulus" parameter as a string and the routine corresponding to the given type of modulus is called.
IMHO this kind of defeats what Peter tried to do in <a class="closed ticket" href="https://trac.sagemath.org/ticket/14832" title="enhancement: Unified construction of irreducible polynomials over finite fields (closed: fixed)">#14832</a> and <a class="closed ticket" href="https://trac.sagemath.org/ticket/14833" title="enhancement: Make choosing irreducible polynomials independent of finite field ... (closed: fixed)">#14833</a> (though it predates these patcehs of course).
Any objection to change this behavior and instead more or less call the new irreducible_element function with the appropriate "algorithm" parameter?
</p>
TicketjpfloriThu, 18 Jul 2013 14:27:37 GMT
https://trac.sagemath.org/ticket/8335#comment:89
https://trac.sagemath.org/ticket/8335#comment:89
<p>
(This will potentially introduce a slow down in some constructors, e.g. in finite_field_ntl_gf2e, but this can't really be helped.)
</p>
TicketroedThu, 18 Jul 2013 22:36:47 GMT
https://trac.sagemath.org/ticket/8335#comment:90
https://trac.sagemath.org/ticket/8335#comment:90
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/8335#comment:88" title="Comment 88">jpflori</a>:
</p>
<blockquote class="citation">
<p>
I've begun rebasing, cleaning and splitting in a better way the patches here.
</p>
<p>
I have one question: in several finite field constructors based on a given implementation (let's say FiniteField_givaro), you can still pass the "modulus" parameter as a string and the routine corresponding to the given type of modulus is called.
IMHO this kind of defeats what Peter tried to do in <a class="closed ticket" href="https://trac.sagemath.org/ticket/14832" title="enhancement: Unified construction of irreducible polynomials over finite fields (closed: fixed)">#14832</a> and <a class="closed ticket" href="https://trac.sagemath.org/ticket/14833" title="enhancement: Make choosing irreducible polynomials independent of finite field ... (closed: fixed)">#14833</a> (though it predates these patcehs of course).
Any objection to change this behavior and instead more or less call the new irreducible_element function with the appropriate "algorithm" parameter?
</p>
</blockquote>
<p>
No, I have no objection to a more unified way of generating the modulus.
</p>
TicketjpfloriFri, 19 Jul 2013 09:13:14 GMT
https://trac.sagemath.org/ticket/8335#comment:91
https://trac.sagemath.org/ticket/8335#comment:91
<p>
Ok so let's go this way.
</p>
<p>
As I'll be cut from the internet next week while the workshop in Leiden is taking place and I'm not sure what I'll be able to achieve today, here are some hints on what I plan to do.
Of course feel free to do something completely different and merge the ticket next week!
</p>
<ul><li>rebase David's first patch (PC polys construction) on top of Peter's patches and include the relevant fixes (i.e. those only related to Conway and pseudo-Conway polynomials construction) from the "fixes" patch I posted here, move all the conway and pseudo-conway construction stuff to a separate file (I feel two files, one for Conway, one for pseudo-Conway, would be overkill, but all that stuff currently in constructor.py seems too much), maybe use two algo names "conway" for using the database and pseudo-conway to use the new code (and still use the database when possible). With the current patches, the PCPT is stored into the finite field (so that its not garbage collected), that is not possible with the new way of building moduli, so we have to think of another way, maybe store it in the modulus itself... (though the polynomial does not really care it's pseudo-Conway whereas the FF does). I don't think modifying irreducible_element() to return more stuff would be a good idea, any other advice welcomed!
</li><li>rebase David's second patch (coercion) on top of Peter's patches, include relevant fixes, do not define "GF" without names.
</li><li>keep the design of the <a class="missing wiki">AlgebraicClosure?</a> stuff for later, note that it should not be too hard to move later to the new framework, much less hard than implementing FFs through templates as for the p-adics and polynomial rings :)
</li></ul>
TicketjpfloriFri, 19 Jul 2013 14:29:36 GMTdescription changed
https://trac.sagemath.org/ticket/8335#comment:92
https://trac.sagemath.org/ticket/8335#comment:92
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/8335?action=diff&version=92">diff</a>)
</li>
</ul>
<p>
I found no time to work on this today, so I'll just post the very rough and incomplete patch I produced yesterday evening, not sure it is worth anything, but just in case you can apply it after applying <a class="attachment" href="https://trac.sagemath.org/attachment/ticket/8335/trac_8335-pseudo_conway-5.10.b3.patch" title="Attachment 'trac_8335-pseudo_conway-5.10.b3.patch' in Ticket #8335">trac_8335-pseudo_conway-5.10.b3.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/8335/trac_8335-pseudo_conway-5.10.b3.patch" title="Download"></a> (note that hg will rant and you'll get three rejection files in sage/rings/finite_rings/, just push the new patch on top of that).
Note it does not include anything from <a class="attachment" href="https://trac.sagemath.org/attachment/ticket/8335/trac_8335-fixes-5.11.b3.patch" title="Attachment 'trac_8335-fixes-5.11.b3.patch' in Ticket #8335">trac_8335-fixes-5.11.b3.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/8335/trac_8335-fixes-5.11.b3.patch" title="Download"></a> yet.
</p>
TicketjpfloriFri, 19 Jul 2013 14:30:41 GMTattachment set
https://trac.sagemath.org/ticket/8335
https://trac.sagemath.org/ticket/8335
<ul>
<li><strong>attachment</strong>
set to <em>trac_8335-pseudo_conway-fixes.patch</em>
</li>
</ul>
TicketpbruinMon, 22 Jul 2013 14:25:07 GMT
https://trac.sagemath.org/ticket/8335#comment:93
https://trac.sagemath.org/ticket/8335#comment:93
<p>
OK, thanks. To begin with we'll start by trying to understand better how these patches work.
</p>
TicketpbruinMon, 22 Jul 2013 14:56:28 GMTdependencies changed
https://trac.sagemath.org/ticket/8335#comment:94
https://trac.sagemath.org/ticket/8335#comment:94
<ul>
<li><strong>dependencies</strong>
changed from <em>#13894</em> to <em>#13894, #14833</em>
</li>
</ul>
TicketpbruinTue, 23 Jul 2013 12:55:59 GMTcc changed
https://trac.sagemath.org/ticket/8335#comment:95
https://trac.sagemath.org/ticket/8335#comment:95
<ul>
<li><strong>cc</strong>
<em>mraum</em> <em>fstromberg</em> <em>JCooley</em> <em>davidloeffler</em> <em>dfesti</em> added
</li>
</ul>
<p>
There are a few small problems with applying and testing this set of patches; I am now combining them into one patch that can be applied on top of 5.11.beta3 + (dependencies of this ticket) and that we can use as a starting point during Sage Days 51.
</p>
TicketpbruinTue, 23 Jul 2013 14:43:15 GMT
https://trac.sagemath.org/ticket/8335#comment:96
https://trac.sagemath.org/ticket/8335#comment:96
<p>
I'm going to split the following parts off into separate tickets, which will be dependencies of this one:
</p>
<ul><li>the new squarefree decomposition code and the new <code>any_root</code> function;
</li><li>the code for pseudo-Conway polynomials.
</li></ul><p>
These will hopefully be relatively easy to review. We can then concentrate on implementing coercion between finite fields in this ticket.
</p>
TicketpbruinTue, 23 Jul 2013 15:12:35 GMTdependencies, description changed
https://trac.sagemath.org/ticket/8335#comment:97
https://trac.sagemath.org/ticket/8335#comment:97
<ul>
<li><strong>dependencies</strong>
changed from <em>#13894, #14833</em> to <em>#14958</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/8335?action=diff&version=97">diff</a>)
</li>
</ul>
TicketpbruinTue, 23 Jul 2013 15:47:33 GMT
https://trac.sagemath.org/ticket/8335#comment:98
https://trac.sagemath.org/ticket/8335#comment:98
<p>
Once <a class="closed ticket" href="https://trac.sagemath.org/ticket/14957" title="enhancement: Square-free decomposition and any_root for polynomials (closed: fixed)">#14957</a> and <a class="closed ticket" href="https://trac.sagemath.org/ticket/14958" title="enhancement: Implement pseudo-Conway polynomials (closed: fixed)">#14958</a> are stable enough, the next step will be to update <a class="attachment" href="https://trac.sagemath.org/attachment/ticket/8335/trac_8335-finite_field_coerce-5.8.b0.patch" title="Attachment 'trac_8335-finite_field_coerce-5.8.b0.patch' in Ticket #8335">trac_8335-finite_field_coerce-5.8.b0.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/8335/trac_8335-finite_field_coerce-5.8.b0.patch" title="Download"></a> and <a class="attachment" href="https://trac.sagemath.org/attachment/ticket/8335/trac_8335-fixes-5.11.b3.patch" title="Attachment 'trac_8335-fixes-5.11.b3.patch' in Ticket #8335">trac_8335-fixes-5.11.b3.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/8335/trac_8335-fixes-5.11.b3.patch" title="Download"></a>, according to Jean-Pierre's plan from <a class="ext-link" href="http://trac.sagemath.org/ticket/8335#comment:91"><span class="icon"></span>http://trac.sagemath.org/ticket/8335#comment:91</a>.
</p>
TicketpbruinWed, 24 Jul 2013 14:22:05 GMT
https://trac.sagemath.org/ticket/8335#comment:99
https://trac.sagemath.org/ticket/8335#comment:99
<p>
The patch <a class="attachment" href="https://trac.sagemath.org/attachment/ticket/8335/trac_8335_sd51.patch" title="Attachment 'trac_8335_sd51.patch' in Ticket #8335">trac_8335_sd51.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/8335/trac_8335_sd51.patch" title="Download"></a> contains the changes that remain after splitting off <a class="closed ticket" href="https://trac.sagemath.org/ticket/14957" title="enhancement: Square-free decomposition and any_root for polynomials (closed: fixed)">#14957</a> and <a class="closed ticket" href="https://trac.sagemath.org/ticket/14958" title="enhancement: Implement pseudo-Conway polynomials (closed: fixed)">#14958</a>, and has been rebased on 5.11.beta3 + (dependencies of this ticket).
</p>
<pre class="wiki">Patchbot: apply trac_8335_sd51.patch
</pre>
TicketpbruinThu, 25 Jul 2013 07:27:00 GMTattachment set
https://trac.sagemath.org/ticket/8335
https://trac.sagemath.org/ticket/8335
<ul>
<li><strong>attachment</strong>
set to <em>trac_8335_sd51.patch</em>
</li>
</ul>
<p>
to work on during Sage Days 51
</p>
TicketpbruinMon, 29 Jul 2013 11:48:52 GMTattachment set
https://trac.sagemath.org/ticket/8335
https://trac.sagemath.org/ticket/8335
<ul>
<li><strong>attachment</strong>
set to <em>trac_8335-finite_field_coerce-5.11.b3.patch</em>
</li>
</ul>
<p>
unified, rebased and cleaned up
</p>
TicketpbruinMon, 29 Jul 2013 12:08:49 GMTstatus, dependencies, work_issues, description changed
https://trac.sagemath.org/ticket/8335#comment:100
https://trac.sagemath.org/ticket/8335#comment:100
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_info</em>
</li>
<li><strong>dependencies</strong>
changed from <em>#14958</em> to <em>#14958, #12142</em>
</li>
<li><strong>work_issues</strong>
changed from <em>rebase</em> to <em>wait for #14958</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/8335?action=diff&version=100">diff</a>)
</li>
</ul>
<p>
Besides everything else, the latest patch moves <code>_coerce_map_from_()</code> from the various finite field implementations to the <code>FiniteField</code> base class; it is now implementation-independent. For this reason, this ticket now depends on <a class="closed ticket" href="https://trac.sagemath.org/ticket/12142" title="enhancement: Speed up PARI finite field operations (closed: fixed)">#12142</a>. Various other changes have been made.
</p>
<p>
The syntax for constructing finite fields using Conway polynomials that admit automatic coercion is now
</p>
<pre class="wiki">sage: F.<a> = FiniteField(5^3, conway=True, prefix='z')
</pre><p>
This is not too pretty, but it is meant as a temporary solution until we have algebraic closures of finite fields.
</p>
<p>
Older patches on this ticket contained various changes that were in older attachments and that do not seem immediately relevant to this ticket. I deleted those changes that seemed superfluous and kept those that I thought could be necessary after all.
</p>
<p>
This ticket should be reviewed once <a class="closed ticket" href="https://trac.sagemath.org/ticket/14958" title="enhancement: Implement pseudo-Conway polynomials (closed: fixed)">#14958</a> is done.
</p>
<p>
For patchbot:
</p>
<pre class="wiki">apply trac_8335-finite_field_coerce-5.11.b3.patch
</pre>
TicketjpfloriTue, 30 Jul 2013 12:27:01 GMTstatus, author changed; work_issues deleted
https://trac.sagemath.org/ticket/8335#comment:101
https://trac.sagemath.org/ticket/8335#comment:101
<ul>
<li><strong>status</strong>
changed from <em>needs_info</em> to <em>needs_review</em>
</li>
<li><strong>work_issues</strong>
<em>wait for #14958</em> deleted
</li>
<li><strong>author</strong>
changed from <em>David Roe, Jean-Pierre Flori</em> to <em>David Roe, Jean-Pierre Flori, Peter Bruin</em>
</li>
</ul>
TicketjpfloriTue, 30 Jul 2013 12:38:02 GMTattachment set
https://trac.sagemath.org/ticket/8335
https://trac.sagemath.org/ticket/8335
<ul>
<li><strong>attachment</strong>
set to <em>trac_8335-finite_field_coerce-5.11.b3-14888.patch</em>
</li>
</ul>
<p>
Rebased on top of <a class="closed ticket" href="https://trac.sagemath.org/ticket/14888" title="enhancement: Make FiniteField_pari_ffelt the default for generic finite fields (closed: fixed)">#14888</a>.
</p>
TicketjpfloriTue, 30 Jul 2013 12:38:20 GMTdescription changed
https://trac.sagemath.org/ticket/8335#comment:102
https://trac.sagemath.org/ticket/8335#comment:102
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/8335?action=diff&version=102">diff</a>)
</li>
</ul>
TicketjpfloriTue, 30 Jul 2013 12:44:43 GMTstatus changed; work_issues set
https://trac.sagemath.org/ticket/8335#comment:103
https://trac.sagemath.org/ticket/8335#comment:103
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
<li><strong>work_issues</strong>
set to <em>rebase on top of #14958</em>
</li>
</ul>
<p>
Need to be rebased because of the name changes in <a class="closed ticket" href="https://trac.sagemath.org/ticket/14958" title="enhancement: Implement pseudo-Conway polynomials (closed: fixed)">#14958</a>.
</p>
TicketjpfloriTue, 30 Jul 2013 12:51:54 GMTwork_issues changed
https://trac.sagemath.org/ticket/8335#comment:104
https://trac.sagemath.org/ticket/8335#comment:104
<ul>
<li><strong>work_issues</strong>
changed from <em>rebase on top of #14958</em> to <em>rebase on top of #14958, store ref to PCL in finite field (or implement another way of weak caching)</em>
</li>
</ul>
<p>
My bad.
I thought you still cached the lattice in the finite field but you don't.
(Un)fortunately when the lattice is built it is only weak-cached in conway_polynomials.py (so that it can be gc'ed when no finite field uses it anymore).
</p>
<p>
So either we have to store the lattice in the finite field to keep it alive and be able to use it when building extensions/pushouts and so on, or strongly cache it in conway_polynomials.py (I don't like that solution, in fact I hate caching things too much; note that currently everything is strongly cached anyway because of <a class="ticket" href="https://trac.sagemath.org/ticket/8335#comment:69" title="Comment 69">comment:69</a>, <a class="closed ticket" href="https://trac.sagemath.org/ticket/14711" title="defect: Weak references in the coercion graph (closed: fixed)">#14711</a>).
</p>
TicketjpfloriTue, 30 Jul 2013 12:57:09 GMTattachment set
https://trac.sagemath.org/ticket/8335
https://trac.sagemath.org/ticket/8335
<ul>
<li><strong>attachment</strong>
set to <em>trac_8335-rebase_14958.patch</em>
</li>
</ul>
<p>
Name changes in <a class="closed ticket" href="https://trac.sagemath.org/ticket/14958" title="enhancement: Implement pseudo-Conway polynomials (closed: fixed)">#14958</a>.
</p>
TicketjpfloriTue, 30 Jul 2013 12:57:58 GMTwork_issues, description changed
https://trac.sagemath.org/ticket/8335#comment:105
https://trac.sagemath.org/ticket/8335#comment:105
<ul>
<li><strong>work_issues</strong>
changed from <em>rebase on top of #14958, store ref to PCL in finite field (or implement another way of weak caching)</em> to <em>store ref to PCL in finite field (or implement another way of weak caching)</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/8335?action=diff&version=105">diff</a>)
</li>
</ul>
TicketjpfloriTue, 30 Jul 2013 13:31:37 GMT
https://trac.sagemath.org/ticket/8335#comment:106
https://trac.sagemath.org/ticket/8335#comment:106
<p>
In fact, the more I think about it, the less I like the way things are stored in the pseudo-Conway polynomial code.
</p>
<p>
We should make some big changes when implementing the <a class="missing wiki">AlgebraicClosure?</a> thing...
Has anyone open a ticket for that?
</p>
TicketpbruinWed, 31 Jul 2013 15:06:43 GMT
https://trac.sagemath.org/ticket/8335#comment:107
https://trac.sagemath.org/ticket/8335#comment:107
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/8335#comment:106" title="Comment 106">jpflori</a>:
</p>
<blockquote class="citation">
<p>
We should make some big changes when implementing the <a class="missing wiki">AlgebraicClosure?</a> thing...
Has anyone open a ticket for that?
</p>
</blockquote>
<p>
Not yet, as far as I have been able to find out; I can do it now.
</p>
TicketpbruinWed, 31 Jul 2013 17:00:25 GMT
https://trac.sagemath.org/ticket/8335#comment:108
https://trac.sagemath.org/ticket/8335#comment:108
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/8335#comment:106" title="Comment 106">jpflori</a>:
</p>
<blockquote class="citation">
<p>
In fact, the more I think about it, the less I like the way things are stored in the pseudo-Conway polynomial code.
</p>
</blockquote>
<p>
I dislike it too. It is problematic to store pseudo-Conway lattices globally in a Sage session (at least until they are garbage-collected) given that they are not uniquely defined.
</p>
<p>
It appears that the user could do the following:
</p>
<ul><li>create a finite field <em>k</em><sub>0</sub> using a primitive polynomial <em>f</em><sub>0</sub>
</li><li>throw away <em>k</em><sub>0</sub>, causing the pseudo-Conway lattice containing <em>f</em><sub>0</sub> to be garbage-collected
</li><li>create a field <em>k</em><sub>1</sub> using exactly the same command as for <em>k</em><sub>0</sub>; this will be isomorphic to <em>k</em><sub>0</sub>, but will in general be defined by a polynomial <em>f</em><sub>1</sub> that is different from <em>f</em><sub>0</sub>
</li><li>end up with a <em>k</em><sub>1</sub> that is incompatible with things that were constructed with the help of <em>k</em><sub>0</sub> (e.g. extensions of <em>k</em><sub>0</sub>), even though both of them were generated using pseudo-Conway polynomials.
</li></ul><p>
I was also worried that storing the pseudo-Conway lattice in the finite field would mean that we would forever have to keep suitable pickling/unpickling code around to deal with this. Actually, this is not necessary, since the pseudo-Conway lattice can be reconstructed from the defining polynomial. However, this does not seem to solve the above problem. Using strong references does not solve it either. In both cases, the user may pickle <em>k</em><sub>0</sub>, restart Sage, create <em>k</em><sub>1</sub>, and finally unpickle <em>k</em><sub>0</sub>; then again <em>k</em><sub>0</sub> and <em>k</em><sub>1</sub> will be different in general.
</p>
<p>
All of this is basically a manifestation of the fact that "the" field of <em>p<sup>n</sup></em> elements is only defined up to non-canonical isomorphism.
</p>
TicketjpfloriWed, 31 Jul 2013 17:09:31 GMT
https://trac.sagemath.org/ticket/8335#comment:109
https://trac.sagemath.org/ticket/8335#comment:109
<p>
I suggest we store a strong to the (top of the) lattice in the FF for the moment, as used to be done, and merge this ticket.
</p>
<p>
And let's think of a better design for <a class="closed ticket" href="https://trac.sagemath.org/ticket/14990" title="enhancement: Implement algebraic closures of finite fields (closed: fixed)">#14990</a>.
Having <a class="missing wiki">AlgebraicClosure?</a> object will surely greatly simplify this.
</p>
TicketpbruinThu, 01 Aug 2013 14:12:27 GMT
https://trac.sagemath.org/ticket/8335#comment:110
https://trac.sagemath.org/ticket/8335#comment:110
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/8335#comment:109" title="Comment 109">jpflori</a>:
</p>
<blockquote class="citation">
<p>
I suggest we store a strong to the (top of the) lattice in the FF for the moment
</p>
</blockquote>
<p>
We could do that to make garbage collection less likely, but it won't really solve the problem, see <a class="ticket" href="https://trac.sagemath.org/ticket/8335#comment:108" title="Comment 108">comment:108</a>.
</p>
<blockquote class="citation">
<p>
And let's think of a better design for <a class="closed ticket" href="https://trac.sagemath.org/ticket/14990" title="enhancement: Implement algebraic closures of finite fields (closed: fixed)">#14990</a>.
Having <a class="missing wiki">AlgebraicClosure?</a> object will surely greatly simplify this.
</p>
</blockquote>
<p>
Yes, the more I think about it, the more convinced I am that algebraic closures are the only real solution to the problem of compatible embeddings.
</p>
<p>
Jenny Cooley suggested the following idea, which I think is a good compromise: implement this ticket only for standard (not pseudo-) Conway polynomials. Hopefully this would suffice for most practical purposes, and since they are uniquely determined, we wouldn't have to come up with half-baked solutions to the caching problem. In <a class="closed ticket" href="https://trac.sagemath.org/ticket/14990" title="enhancement: Implement algebraic closures of finite fields (closed: fixed)">#14990</a> (which I am working on now), pseudo-Conway polynomials can then finally be put to use, and they will be cached in the algebraic closure, where they really belong.
</p>
TicketjpfloriThu, 01 Aug 2013 14:16:08 GMT
https://trac.sagemath.org/ticket/8335#comment:111
https://trac.sagemath.org/ticket/8335#comment:111
<p>
I'm ok with that.
</p>
<p>
I think I could accept anything as long as we close this ticket :)
</p>
TicketpbruinFri, 02 Aug 2013 11:02:25 GMTattachment set
https://trac.sagemath.org/ticket/8335
https://trac.sagemath.org/ticket/8335
<ul>
<li><strong>attachment</strong>
set to <em>trac_8335-no_pseudo.patch</em>
</li>
</ul>
<p>
use only (non-pseudo-)Conway polynomials
</p>
TicketpbruinFri, 02 Aug 2013 11:06:44 GMTstatus, description, summary changed; work_issues deleted
https://trac.sagemath.org/ticket/8335#comment:112
https://trac.sagemath.org/ticket/8335#comment:112
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/8335?action=diff&version=112">diff</a>)
</li>
<li><strong>work_issues</strong>
<em>store ref to PCL in finite field (or implement another way of weak caching)</em> deleted
</li>
<li><strong>summary</strong>
changed from <em>Finite Field lattices for (pseudo-)Conway polynomials</em> to <em>Finite field lattices via Conway polynomials</em>
</li>
</ul>
TicketpbruinFri, 02 Aug 2013 11:10:21 GMT
https://trac.sagemath.org/ticket/8335#comment:113
https://trac.sagemath.org/ticket/8335#comment:113
<p>
For patchbot:
</p>
<pre class="wiki">apply trac_8335-finite_field_coerce-5.11.b3-14888.patch, trac_8335-no_pseudo.patch
</pre><p>
Note: <a class="attachment" href="https://trac.sagemath.org/attachment/ticket/8335/trac_8335-rebase_14958.patch" title="Attachment 'trac_8335-rebase_14958.patch' in Ticket #8335">trac_8335-rebase_14958.patch</a><a class="trac-rawlink" href="https://trac.sagemath.org/raw-attachment/ticket/8335/trac_8335-rebase_14958.patch" title="Download"></a> is not needed if we go for this approach.
</p>
TicketjpfloriTue, 06 Aug 2013 11:45:33 GMTstatus changed
https://trac.sagemath.org/ticket/8335#comment:114
https://trac.sagemath.org/ticket/8335#comment:114
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<p>
Looks ok.
Still depending on <a class="closed ticket" href="https://trac.sagemath.org/ticket/14958" title="enhancement: Implement pseudo-Conway polynomials (closed: fixed)">#14958</a> as functions related to (non-pseudo) Conway polys were moved around there.
</p>
TicketjdemeyerWed, 07 Aug 2013 08:01:19 GMTmilestone changed
https://trac.sagemath.org/ticket/8335#comment:115
https://trac.sagemath.org/ticket/8335#comment:115
<ul>
<li><strong>milestone</strong>
changed from <em>sage-5.11</em> to <em>sage-5.12</em>
</li>
</ul>
TicketjdemeyerFri, 30 Aug 2013 08:29:39 GMTmilestone changed
https://trac.sagemath.org/ticket/8335#comment:116
https://trac.sagemath.org/ticket/8335#comment:116
<ul>
<li><strong>milestone</strong>
changed from <em>sage-5.12</em> to <em>sage-pending</em>
</li>
</ul>
TicketjdemeyerTue, 03 Sep 2013 14:51:36 GMTmilestone changed
https://trac.sagemath.org/ticket/8335#comment:117
https://trac.sagemath.org/ticket/8335#comment:117
<ul>
<li><strong>milestone</strong>
changed from <em>sage-pending</em> to <em>sage-5.13</em>
</li>
</ul>
TicketjdemeyerSat, 12 Oct 2013 09:45:04 GMTstatus changed; resolution, merged set
https://trac.sagemath.org/ticket/8335#comment:118
https://trac.sagemath.org/ticket/8335#comment:118
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>merged</strong>
set to <em>sage-5.13.beta1</em>
</li>
</ul>
Ticket