Opened 12 years ago

Closed 10 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:

Status badges

Description (last modified by mstreng)

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)
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)
   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 12 years ago by lftabera

  • Milestone set to sage-4.5.3

comment:2 Changed 12 years ago by lftabera

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?

comment:3 follow-up: Changed 11 years ago by mstreng

related ticket with different proposal: #10771

comment:4 in reply to: ↑ 3 Changed 11 years ago by SimonKing

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 10 years ago by mstreng

  • 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 10 years ago by mstreng

  • Status changed from new to needs_info

comment:7 Changed 10 years ago by lftabera

  • Status changed from needs_info to needs_review

Yes, this ticket should be resolved as duplicated.

comment:8 Changed 10 years ago by mstreng

  • Description modified (diff)
  • Status changed from needs_review to positive_review

comment:9 Changed 10 years ago by mstreng

  • Authors Luis Felipe Taberea deleted

comment:10 Changed 10 years ago by jdemeyer

  • Resolution set to duplicate
  • Reviewers set to Marco Streng
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.