Opened 4 years ago
Closed 4 years ago
#25379 closed defect (fixed)
random failure in QuadraticResidueCodeOddPair
Reported by:  vdelecroix  Owned by:  

Priority:  blocker  Milestone:  sage8.3 
Component:  coding theory  Keywords:  thursdaysbdx, random_fail 
Cc:  cremona  Merged in:  
Authors:  Jeroen Demeyer  Reviewers:  Frédéric Chapoton 
Report Upstream:  N/A  Work issues:  
Branch:  28a4212 (Commits, GitHub, GitLab)  Commit:  28a4212ce9b8479d305c850a2959a28e07c93b6e 
Dependencies:  Stopgaps: 
Description
Reported on https://groups.google.com/forum/#!topic/sagerelease/zh04lo8d44U and also on some patchbots
sage t long src/sage/coding/code_constructions.py ********************************************************************** File "src/sage/coding/code_constructions.py", line 624, in sage.coding.code_constructions.QuadraticResidueCodeOddPair Failed example: codes.QuadraticResidueCodeOddPair(17, GF(13)) Exception raised: Traceback (most recent call last): File "/home/vdelecro/sage_patchbot/local/lib/python2.7/sitepackages/sage/doctest/forker.py", line 562, in _run self.compile_and_execute(example, compiler, test.globs) File "/home/vdelecro/sage_patchbot/local/lib/python2.7/sitepackages/sage/doctest/forker.py", line 972, in compile_and_execute exec(compiled, globs) File "<doctest sage.coding.code_constructions.QuadraticResidueCodeOddPair[0]>", line 1, in <module> codes.QuadraticResidueCodeOddPair(Integer(17), GF(Integer(13))) File "/home/vdelecro/sage_patchbot/local/lib/python2.7/sitepackages/sage/coding/code_constructions.py", line 666, in QuadraticResidueCodeOddPair return DuadicCodeOddPair(F,Q,N) File "/home/vdelecro/sage_patchbot/local/lib/python2.7/sitepackages/sage/coding/code_constructions.py", line 425, in DuadicCodeOddPair gg1 = P2(coeffs1) File "sage/structure/parent.pyx", line 920, in sage.structure.parent.Parent.__call__ (build/cythonized/sage/structure/parent.c:9734) return mor._call_(x) File "sage/structure/coerce_maps.pyx", line 145, in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (build/cythonized/sage/structure/coerce_maps.c:4555) raise File "sage/structure/coerce_maps.pyx", line 140, in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (build/cythonized/sage/structure/coerce_maps.c:4423) return C._element_constructor(x) File "/home/vdelecro/sage_patchbot/local/lib/python2.7/sitepackages/sage/rings/polynomial/polynomial_ring.py", line 404, in _element_constructor_ return C(self, x, check=check, is_gen=False, construct=construct) File "sage/rings/polynomial/polynomial_zmod_flint.pyx", line 100, in sage.rings.polynomial.polynomial_zmod_flint.Polynomial_zmod_flint.__init__ (build/cythonized/sage/rings/polynomial/polynomial_zmod_flint.cpp:14356) lst = [k(i) for i in x] File "sage/structure/parent.pyx", line 920, in sage.structure.parent.Parent.__call__ (build/cythonized/sage/structure/parent.c:9734) return mor._call_(x) File "sage/rings/finite_rings/hom_prime_finite_field.pyx", line 46, in sage.rings.finite_rings.hom_prime_finite_field.SectionFiniteFieldHomomorphism_prime._call_ (build/cythonized/sage/rings/finite_rings/hom_prime_finite_field.c:3457) raise ValueError("%s is not in the image of %s" % (x, self._inverse)) ValueError: 10*z^3 + 9*z^2 + z is not in the image of (map internal to coercion system  copy before use) Ring morphism: From: Finite Field of size 13 To: Finite Field in z of size 13^4 ********************************************************************** 1 item had failures: 1 of 13 in sage.coding.code_constructions.QuadraticResidueCodeOddPair [146 tests, 1 failure, 2.83 s]  sage t long src/sage/coding/code_constructions.py # 1 doctest failed 
Change History (18)
comment:1 Changed 4 years ago by
 Summary changed from coercion and QuadraticResidueCodeOddPair to random failure in QuadraticResidueCodeOddPair
comment:2 Changed 4 years ago by
comment:3 Changed 4 years ago by
 Branch set to u/chapoton/25379
 Commit set to ea8fa5c491d9055ed1b213526d439ce82177de34
 Status changed from new to needs_review
Here is a tentative of enhancement of this lifting procedure.
New commits:
ea8fa5c  enhance one lifting procedure in code constructions

comment:5 Changed 4 years ago by
I'm not sure about the context here, but there are serious performance penalties in using GF(q**n)
rather than GF(q**n)
as n
increases. Is there a reason we need to do so?
comment:6 Changed 4 years ago by
could you please clarify ?
comment:7 followup: ↓ 10 Changed 4 years ago by
We've added the following comment
This is now designed to work only with finite fields with automatic names, built using ``GF(q)``.
and changed FF = GF(q**k,"z")
to FF = GF(q**k)
meaning that we're using pseudoConway polynomials for the extension if k
is large, rather than a randomly selected polynomial.
Here's some timings (I use number=1 and repeat=1 to eliminate caching effects).
sage: for k in srange(100,150): ....: if len(k.factor()) < 3: continue ....: print "3^%s conway "%k, ....: timeit("FF = GF(3^%s)"%k,number=1,repeat=1) ....: print "3^%s random "%k, ....: timeit("FF = GF(3^%s,'z')"%k,number=1,repeat=1) 3^102 conway 1 loops, best of 1: 717 ms per loop 3^102 random 1 loops, best of 1: 2.93 ms per loop 3^105 conway 1 loops, best of 1: 537 ms per loop 3^105 random 1 loops, best of 1: 3.1 ms per loop 3^110 conway 1 loops, best of 1: 794 ms per loop 3^110 random 1 loops, best of 1: 3.17 ms per loop 3^114 conway 1 loops, best of 1: 962 ms per loop 3^114 random 1 loops, best of 1: 3.41 ms per loop 3^120 conway 1 loops, best of 1: 1.25 s per loop 3^120 random 1 loops, best of 1: 3.77 ms per loop 3^126 conway 1 loops, best of 1: 1.47 s per loop 3^126 random 1 loops, best of 1: 3.51 ms per loop 3^130 conway 1 loops, best of 1: 1.06 s per loop 3^130 random 1 loops, best of 1: 6.67 ms per loop 3^132 conway 1 loops, best of 1: 1.26 s per loop 3^132 random 1 loops, best of 1: 5.12 ms per loop 3^138 conway 1 loops, best of 1: 1.57 s per loop 3^138 random 1 loops, best of 1: 3.71 ms per loop 3^140 conway 1 loops, best of 1: 1.5 s per loop 3^140 random 1 loops, best of 1: 4.89 ms per loop
These will continue to worsen as the number of factors of the degree increases.
comment:8 Changed 4 years ago by
Ok. The modified function is only used in this precise file, and I have no idea if its use here involve finite fields for high powers of primes or not.
What is crucial is to have finite fields that have a coherent system of inclusions, all of them sitting in a common algebraic closure. If I understood correctly, this is only ensured by using the syntax GF(q)
without names.
comment:9 Changed 4 years ago by
In any case, there should at least be a test showing that it doesn't work if the assumption
This is now designed to work only with finite fields with automatic names, built using ``GF(q)``.
does not hold.
comment:10 in reply to: ↑ 7 Changed 4 years ago by
Replying to roed:
meaning that we're using pseudoConway polynomials for the extension if
k
is large, rather than a randomly selected polynomial.
When you look at the code, it's certainly assuming implicitly(!) that the defining polynomial is primitive (its root generates the multiplicative group).
comment:11 Changed 4 years ago by
There are more issues with this code:
sage: S1 = [1,3,4,5,7,12,13]; S2 = [2,6,8,9,10,11,14] sage: codes.DuadicCodeEvenPair(GF(3), S1, S2) ... ArithmeticError: multiplicative order of 3 not defined since it is not a unit modulo 15
comment:12 Changed 4 years ago by
 Branch u/chapoton/25379 deleted
 Commit ea8fa5c491d9055ed1b213526d439ce82177de34 deleted
 Status changed from needs_review to needs_work
There are various issues with these functions, I think a stopgap is the best solution. I opened #25896 for the actual issues.
comment:13 Changed 4 years ago by
 Branch set to u/jdemeyer/25379
comment:14 Changed 4 years ago by
 Commit set to 3eee0002a1ea161b861269564292e144c77f9cfd
 Status changed from needs_work to needs_review
New commits:
3eee000  Add a stopgap to DuadicCodeEvenPair/DuadicCodeOddPair

comment:15 Changed 4 years ago by
 Commit changed from 3eee0002a1ea161b861269564292e144c77f9cfd to 28a4212ce9b8479d305c850a2959a28e07c93b6e
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
28a4212  Add a stopgap to DuadicCodeEvenPair/DuadicCodeOddPair

comment:16 Changed 4 years ago by
 Reviewers set to Frédéric Chapoton
 Status changed from needs_review to positive_review
ok
comment:17 Changed 4 years ago by
 Keywords random_fail added
comment:18 Changed 4 years ago by
 Branch changed from u/jdemeyer/25379 to 28a4212ce9b8479d305c850a2959a28e07c93b6e
 Resolution set to fixed
 Status changed from positive_review to closed
There's a function in code_constructions.py that makes me dizzy:
How does
pol.roots(F,multiplicities=False)[0]
know to return the *right* root ofpol
(i.e., the one that coerces back toa
), rather than a random root?