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 -~----------~----~----~----~------~----~------~--~---
test_ell.sage
Description: Binary data
