Opened 10 years ago
Closed 8 years ago
#9819 closed enhancement (duplicate)
Add a default gcd and lcm methods for fields
Reported by: | lftabera | Owned by: | AlexGhitza |
---|---|---|---|
Priority: | major | Milestone: | sage-duplicate/invalid/wontfix |
Component: | algebra | Keywords: | lcm, gcd, fields |
Cc: | Merged in: | ||
Authors: | Reviewers: | Marco Streng | |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
This ticket should be closed as fixed by #10771
For the case of field elements gcd and lcm methods are not of great interest. However, they can be addecuated for some reasons.
- Some algorithms may accept as input either polynomials or rational functions. In these algorithms we may reduce a list of polynomials and rational functions to a common denominator. If all the inputs are polynomials, the denominators are the one element of the base field. In this case, lcm would fail.
See #9063 for a case of this problem.
- Rational numbers already have custom gcd and lcm methods.
-It would erase the following problem. Currently, if we are dealing with elements in a finite field, the gcd of the elements can be computed sometimes coercing to the integers and doing computations. This lead to inconsistencies.
sage: a=F(2) sage: gcd(a,a) 2 sage: gcd(a,p) --------------------------------------------------------------------------- TypeError Traceback (most recent call last) /home/luisfe/Varios/Comprobantes-gastos/<ipython console> in <module>() /opt/SAGE/sage-4.5.2/local/lib/python2.6/site-packages/sage/rings/arith.pyc in gcd(a, b, **kwargs) 1423 return ZZ(a).gcd(ZZ(b)) 1424 except TypeError: -> 1425 raise TypeError, "unable to find gcd of %s and %s"%(a,b) 1426 1427 from sage.structure.sequence import Sequence TypeError: unable to find gcd of 2 and p
I propose the following:
- For gcd, follow the convention of the rational cesa. If both elements are 0, return 0 (on the appropriate field). Otherwise return 1
- For lcm, if one of the elements is zero, return zero. Otherwise return 1.
#9063 depends on this bug to be merged.
Change History (10)
comment:1 Changed 10 years ago by
- Milestone set to sage-4.5.3
comment:2 Changed 10 years ago by
comment:3 follow-up: ↓ 4 Changed 9 years ago by
related ticket with different proposal: #10771
comment:4 in reply to: ↑ 3 Changed 9 years ago by
Replying to mstreng:
related ticket with different proposal: #10771
I wouldn't say that it is a different proposal. #10771 treats the case of fields that happen to be the fraction field of a unique factorization domain. In this case, one can do better than to return either 0 or 1.
However, #10771 does not consider the case of fields that are no fraction fields, or are fraction fields of rings that do not provide lcm and gcd. I suggest that for that purpose, one should implement gcd and lcd as element methods of the category of Fields()
. That would also solve the problem that IntegerMod_int
does not derive from FieldElement
.
comment:5 Changed 8 years ago by
- Milestone changed from sage-4.8 to sage-duplicate/invalid/wontfix
Is everything on this ticket fixed already? It seems that #10771 did implement Fields.ElementMethods.gcd()
after all and its behaviour is as requested in this ticket.
comment:6 Changed 8 years ago by
- Status changed from new to needs_info
comment:7 Changed 8 years ago by
- Status changed from needs_info to needs_review
Yes, this ticket should be resolved as duplicated.
comment:8 Changed 8 years ago by
- Description modified (diff)
- Status changed from needs_review to positive_review
comment:9 Changed 8 years ago by
comment:10 Changed 8 years ago by
- Resolution set to duplicate
- Reviewers set to Marco Streng
- Status changed from positive_review to closed
To make thing worse, currently (sage 4.5.3.alpha2) GF(5)(4) is an IntegerMod_int that does not derive from FieldElement? but CommutativeRingElement?