On Nov 9, 2007, at 11:46 AM, Steffen wrote: > The easier %4 == 3 case seems to be implemented efficiently, but the > %4 == 1 not. The algo from Tonelli and Shanks might be a good solution > here. Any thoughts on other/better algorithm? > > Steffen
I actually wrote this code. It eventually dispatches down to square_root_mod_prime (for large enough p), which has some references for the algorithm I used. It actually beats pari for large p (100+ digits)--after doing an initial pre-calculation. It looks like for the range you're dealing with, pari is 3-7 times faster. However, as much as 25% or so of that is overhead (Sage can handle sqrts of composite numbers, and return all square roots. The conversion sage->pari->pari sqrt->sage is slower than doing the operation simply using Sage. If someone thinks Tonelli and Shanks will be faster and wants to implement it, that could be good. - Robert sage: p = next_prime(11^8); print p, p%16 214358891 11 sage: K = GF(p) sage: a = K.random_element()^2 sage: time a.sqrt() 69738242 Time: CPU 0.00 s, Wall: 0.00 s sage: a = K.random_element()^2 sage: time L = [a.sqrt() for _ in range(10000)] CPU time: 0.22 s, Wall time: 0.22 s sage: b = pari(a) sage: time L = [b.sqrt() for _ in range(10000)] CPU time: 0.07 s, Wall time: 0.07 s sage: time L = [K(pari(a).sqrt()) for _ in range(10000)] CPU time: 0.73 s, Wall time: 0.73 s sage: from sage.rings.integer_mod import square_root_mod_prime sage: time L = [square_root_mod_prime(a,p) for _ in range(10000)] CPU time: 0.15 s, Wall time: 0.15 s --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~----------~----~----~----~------~----~------~--~---
