2008/12/17 dmharvey <dmhar...@cims.nyu.edu>: > > On Dec 17, 5:32 pm, Alasdair <amc...@gmail.com> wrote: >> What facilities are available to me here? For example, the following: >> >> p=211 >> F.<x>=GF(p)[] >> G.<a>=GF(p^17,name='a',modulus=x^17+2*x^2+1) >> g=G.multiplicative_generator() >> r=G.random_element() >> discrete_log(r,g) >> >> ties up my computer for several minutes while using all possible CPU, >> then finally Sage gives up the ghost and crashes. > > The order of your field has a prime factor of > 473657018821793557815477348357239, which has ~108 bits, so the best > algorithms I know would need to do a search of size about 2^54, which > is kind of big. Probably computationally infeasible on the hardware > you are using. But maybe there are better algorithms, and I don't know > exactly what algorithm Sage is using.
Sage is using a completely generic dlog algorithm based on baby-step-giant-step, which is of course extremely inefficient for large fields. If someone out there would like to implement something better, that would be very good! Also: the multiplicative_generator() function is pretty stupid. If the field's generator does not generator the multiplicative group it just tries elements at random until one is found that does. That would be much easier to improve. John Cremona > > david > > > > --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-support@googlegroups.com To unsubscribe from this group, send email to sage-support-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-support URLs: http://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
