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 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 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... Le lundi 28 avril 2014 21:54:33 UTC+2, Martin Albrecht a écrit : > > I just tried to run: > > sage: m = random_prime(10^5) > sage: K.<r> = CyclotomicField(m) > > and I ran out of RAM! Doing a smaller example: > > sage: m = random_prime(10^4) > sage: %prun K.<r> = CyclotomicField(m) > > puts > > sage.rings.number_field.number_field_morphisms.create_embedding_from_approx > > > as the most expensive function call. Continuing to: > > sage: m = random_prime(2*10^3) > sage: K.<r> = CyclotomicField(m) > sage: %prun K.ring_of_integers() > > puts > > sage.matrix.matrix_integer_dense.Matrix_integer_dense._solve_right_nonsingular_square > > > > as the most expensive function call, which would imply John's assumption > is > right. > > Cheers, > Martin > > On Tuesday 15 Apr 2014 13:04:27 François Colas wrote: > > Hi Vincent, > > > > In fact that's exactly what I want to do! > > > > But I am using morphisms: > > > > m = ZZ(int(random()*10^5+1)) > > > > R.<r> = NumberField(cyclotomic_polynomial(m)) > > > > Idl = [] > > > > for (p, e) in factor(m): > > Idl.append(cyclotomic_polynomial(p)) > > > > K = NumberField(Idl, 'k') > > > > F = Hom(R, K) > > > > f = F([...]) > > > > Unfortunately I also need K with big m for cryptographic purpose... :'( > > > > Note that even if you have 3 cyclotomic polynomials in Idl (e.g. 11, 13, > > 17) it's always slow. > > > > Le mardi 15 avril 2014 18:48:11 UTC+2, vdelecroix a écrit : > > > Hi François, > > > > > > Might be related to the ticket #16116 on trac > > > (http://trac.sagemath.org/ticket/16116). Note that for performance, > it > > > is possible to use multivariate polynomials as described in the > > > ticket. > > > > > > Best > > > Vincent > > > > > > 2014-04-15 18:30 UTC+02:00, François Colas <fco...@gmail.com > <javascript:>>: > > > > Hello group, > > > > > > > > I am playing with quotient ring of Z over cyclotomic polynomial but > it > > > > > > is > > > > > > > strangely slow: > > > > > > > > sage: m = random_prime(10^4); m > > > > 2437 > > > > sage: %time R.<r> = ZZ['z'].quotient(cyclotomic_polynomial(m)) > > > > CPU times: user 2.50 s, sys: 0.00 s, total: 2.50 s > > > > Wall time: 2.50 s > > > > > > > > cyclotomic_polynomial(m) is created instantly whatever the size of m > but > > > > the quotient becomes very long: > > > > > > > > sage: m = random_prime(10^5); m > > > > 16231 > > > > sage: %time R.<r> = ZZ['z'].quotient(cyclotomic_polynomial(m)) > > > > CPU times: user 217.82 s, sys: 0.00 s, total: 217.82 s > > > > Wall time: 217.65 s > > > > > > > > > > > > I am using Sage Version 6.1.1, does anyone could confirm this > problem? > > > > > > Groups > > > > > > > "sage-devel" group. > > > > To unsubscribe from this group and stop receiving emails from it, > send > > > > > > an > > > > > > > email to sage-devel+...@googlegroups.com <javascript:>. > > > > To post to this group, send email to > > > > sage-...@googlegroups.com<javascript:>. > > > > > > > > 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.
