On 30 April 2014 10:09, François Colas <fco...@gmail.com> wrote: > What I am trying to do is to use the prime factorisation of m to compute in > another field than Q(zeta_m) (i.e. Q(zeta_m1, zeta_m2, ..., zeta_ml)) or > Q[x]/<Phi_m> (i.e. Q[x1, ..., xl] / <Phi_m1, ..., Phi_ml>) because I need m > between 1000 and 10000 and actually sage is not able to do this. The idea is > to have a faster arithmetic. > > In fact I should have written: > > Idl = [cyclotomic_polynomial(p^e, 'q'+str(i)) for (i, (p, e)) in > enumerate(factor(m))] > > In this case 2 cyclotomic polynomials never define the same extension field > right? >
Yes, that is certainly true. In fact if m and n are distinct positive integers then Phi_m and Phi_n generate the unit ideal in Z[X] so they are coprime in this stronger sense: their reultant is 1, not just a nonzero constant). Sometimes it is possible to do computations in Z[X] / (X^m-1) which should be cheaper. Of course this is not the rings you actually want, as it is the direct sum of the d'th cyclotomic rings for all d|m, but any equality in this ring is also an inequality in the m'th cyclotomic ring as that is a quotient of this. John > > PS: Phi_m = cyclotomic_polynomial(m) > > Le mercredi 30 avril 2014 10:07:55 UTC+2, John Cremona a écrit : >> >> On 29 April 2014 19:23, Martin Albrecht <martinr...@googlemail.com> wrote: >> > On Monday 28 Apr 2014 14:57:59 François Colas wrote: >> >> Hi Martin, >> >> >> >> Here is two examples using multivariate quotients and extension fields >> >> which should be faster than computing CyclotomicField(m) or >> >> NumberField(cyclotomic(m), 'r') : >> >> >> >> m = 3*5*7 >> >> pi = prime_factors(m) >> >> Qi = PolynomialRing(QQ, len(pi), 'q') >> >> Idl = [cyclotomic_polynomial(p, 'q'+str(i)) for (i, p) in >> >> enumerate(pi)] >> >> K = Qi.quo(Idl, 'k') >> >> %time K.fraction_field() >> >> CPU times: user 0.10 s, sys: 0.00 s, total: 0.10 s >> >> Wall time: 0.10 s >> > >> > Okay, this one does pretty much nothing as far as I can tell except for >> > checking that Idl is prime. This check could/should be specialised for >> > this >> > type of input. >> > >> > Am I right in assuming that I = <f_1, ..., f_m> with all f_i irreducible >> > and >> > <f_i> \intersect <f_j> = \empty then I is a prime ideal? >> >> NO! If f1 and f2 define the same extension field then <f1,f2> will >> not be prime, e.g. f1=x^2-2 and f2=x^2-8 over QQ. >> >> John >> >> > >> >> and with NumberField: >> >> >> >> m = 3*5*7 >> >> pi = prime_factors(m) >> >> Idl = [cyclotomic_polynomial(p) for p in pi] >> >> %time NumberField(Idl, 'k', check=False) >> >> CPU times: user 2.30 s, sys: 0.01 s, total: 2.31 s >> >> Wall time: 2.30 s >> > >> > Running >> > >> > sage: %prun NumberField(Idl, 'k', check=False) >> > >> > 4 1.761 0.440 1.761 0.440 >> > number_field_rel.py:1034(_rnfeltreltoabs) >> > >> > this is because we're building a tower of number fields: >> > >> > def NumberFieldTower(v, names, check=True, embeddings=None): >> > if len(v) == 0: >> > return QQ >> > if len(v) == 1: >> > return NumberField(v[0], names=names, embedding=embeddings[0]) >> > f = v[0] >> > w = NumberFieldTower(v[1:], names=names[1:], >> > embeddings=embeddings[1:]) >> > if isinstance(f, polynomial_element.Polynomial): >> > var = f.variable_name() >> > else: >> > var = 'x' >> > >> > name = names[0] >> > R = w[var] # polynomial ring >> > >> > f = R(f) >> > i = 0 >> > >> > sep = chr(ord(name[0]) + 1) >> > return w.extension(f, name, check=check, embedding=embeddings[0]) >> > >> > The last line of this code in number_field.py consumes all the time. I >> > don't >> > know what could be done here. >> > >> >> Now try to play with prime factors in m (e.g. m = 5*7*11 or m = >> >> 7*11*13), >> >> it becomes uncomputable quickly with both... >> > >> > >> > Cheers, >> > Martin > > -- > You received this message because you are subscribed to the Google Groups > "sage-devel" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to sage-devel+unsubscr...@googlegroups.com. > To post to this group, send email to sage-devel@googlegroups.com. > Visit this group at http://groups.google.com/group/sage-devel. > For more options, visit https://groups.google.com/d/optout. -- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at http://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
