Dear John, I was also searching for curves of cofactor one and that's what the first part was supposed to do, I am sorry I forgot to say it in the previous post. Anyway I will add some lines and hope that this time things will work well. Many thanks.
Adam On Wed, Jun 24, 2009 at 2:13 PM, John Cremona <[email protected]>wrote: > 2009/6/24 adam mohamed <[email protected]>: > > > > I did not know that. I tought that by the line: S = > P.division_points(n_1), > > I would get a non-trivial point in that case witouh having to return all > the > > points. Can I just chose a non-trivial random point on the curve or what > is > > the best to choose a point without going on whole of unecessary things? > > If you do p = E.random_point() when the curve has prime order then > with very large propbility you will get a nontrivial point, hence a > point which is certainly a generator. > > When the order is 4*q with q a prime, do G,gens = E.abelian_group(); > test G.is_cyclic() sine you want t a cyclic group; then P=gens[0] is > a generator, q*P will have order 4 and 4*P will have order q. > > The attached version of your function does something like this; but > of course it would be vastly better to implement a serious algorithm > instead of picking curves at random. > > John > > > > > What I am trying to do is to find elliptic curves over F_p with with > point > > of order 4. Idealy I need E( F_p ) = Z/4Z*Z/(big prime)Z. > > > > Best wishes, > > > > Adam > > > > > > > > On Wed, Jun 24, 2009 at 12:49 PM, John Cremona <[email protected]> > > wrote: > >> > >> Here is the problem Adam. You have a prime l which is about 2^165. > >> You construct random curves over the field GF(l) and count the number > >> of points n_1 on them. This is possible using Sage's use of an > >> efficient SEA algorithm. When the number n_1 is prime, you then ask > >> for all the points of order n_1 on the curve using the division_points > >> () function. This is crazy! For a start, all the points on the curve > >> will be returned; that is a list of points far too big to store. But > >> you will never get there anyway since the division_points() function > >> creates the division polynomial which has degree (n_1^2-1)/2, i.e. > >> about 2^330. > >> > >> It's hard to make a constructive suggestion without knowing what it is > >> you are trying to do. If you write that down clearly, I'll try to > >> help. I found that the abelian_group() function works fine > >> for curves of this size (which makes me pleased, since I wrote it), > >> whether or not the group is cyclic (which is > >> usually is), so it may be that you should first find the generator(s) > >> of the group and their orders, and work with that. > >> > >> John > >> > >> On Jun 23, 2:17 pm, adam mohamed <[email protected]> wrote: > >> > Hi All, > >> > > >> > I solve the problem with the memory, thanks to William. But, now when > I > >> > impose some strict conditions so that I have to toss say 100 times in > >> > order > >> > to hope for some curves to pop up, I am getting different kind of > >> > errors. I > >> > have attached the code and the error message I got hereby. Maybe my > code > >> > is > >> > too naive that why I am having this problem. > >> > > >> > What I don't get is why the code seems to do well when the conditions > >> > are > >> > less restrictive but once I change a little bit, them Sage is not > happy! > >> > Maybe one has to implement Reinier algorithms in order to avoid these > >> > kind > >> > of problems. Is this doable in Sage now? > >> > > >> > Best wishes, > >> > > >> > Adam > >> > > >> > On Tue, Jun 23, 2009 at 1:14 PM, John Cremona > >> > <[email protected]>wrote: > >> > > >> > > >> > > >> > > On Jun 22, 7:59 pm, adam mohamed <[email protected]> > wrote: > >> > > > Hi, > >> > > >> > > > Thanks for the very quick response. I will try that tomorrow. Now > >> > > > I > >> > > > understand the problem that we met when running the same code in > a > >> > > > linux > >> > > > machine. > >> > > > I am doing this search for cryptographic applications, so I am > >> > > > dealing > >> > > with > >> > > > primes from the size of 170 bit Length. > >> > > > I would like the 2-sylow of E( F_p) to be Z/4Z and #E( F_p) = > 4*L > >> > > > with > >> > > > L prime. > >> > > >> > > > Reinier Broker did his PhD about EC with prescribed order and we > >> > > > will > >> > > would > >> > > > like to find out if his algorithms have been implemented in Sage? > >> > > >> > > Hello Adam, > >> > > >> > > No, as far as I know Sage has nothing implemented for finding curves > >> > > with prescribed order or structure. > >> > > >> > > John > >> > > >> > > > Regards, > >> > > >> > > > Adam > >> > > >> > > > On Mon, Jun 22, 2009 at 6:31 PM, William Stein <[email protected]> > >> > > > wrote: > >> > > >> > > > > On Mon, Jun 22, 2009 at 5:35 PM, > >> > > > > harivola<[email protected] > >> > > >> > > > > wrote: > >> > > >> > > > > > Hi all, > >> > > >> > > > > > I am running a small script on a windows xp machine and some > >> > > > > > time I > >> > > > > > am getting this error message: > >> > > > > > /usr/local/sage/local/bin/sage-sage: line 348: 19954 Killed > >> > > > > > python "$@" > >> > > >> > > > > You're probably running out of memory (=RAM). Try editing the > >> > > > > file > >> > > > > sage_vmx.vmx and increase the amount of RAM that is made > available > >> > > > > to > >> > > > > the vmware machine running Sage. The default amount is very > >> > > > > small. > >> > > >> > > > > > I don't get the meaning of that. By the way, does someone know > >> > > > > > an > >> > > > > > efficient way in Sage to search for EC with prescribed order ( > I > >> > > > > > need > >> > > > > > curves over a big prime field with rational points of order 4 > >> > > > > > and > >> > > > > > cofactor 4 ). Thanks. > >> > > >> > > > > Be way more precise. How big is "big prime field"? Do you want > >> > > > > #E(F_p) = 4*n with n odd? Do you require that #E(E_p)[2] = 4 > too? > >> > > >> > > > > William > >> > > >> > > > > > Best wishes > >> > > >> > > > > -- > >> > > > > William Stein > >> > > > > Associate Professor of Mathematics > >> > > > > University of Washington > >> > > > >http://wstein.org > >> > > >> > > >> > > >> > full_output.txt > >> > 42KViewDownload > >> > > >> > test_ell.sage > >> > 2KViewDownload > >> > > > > > > > > > > > > > --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/sage-support URLs: http://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
