From: Robin Chapman Subject: Re: Elliptic curve problem Date: Thu, 02 Nov 2000 08:55:32 GMT Newsgroups: sci.math Summary: [missing] In article , "Richard Gould" wrote: > Hi, the following problem has me stumped. Any insights would be appreciated: > > Suppose p = 2^k - 1 for some k>=3 and let E be the elliptic curve modulo p > defined by y^2 = x^3 + x > > Suppose that there is a point Q on E so that 2^(k-1)*Q can be successfully > computed and is an ordinary point with y-coord 0. Prove that p is prime. > > (note: it has already being shown that if p is prime then E is of size p+1, > not sure if this helps though) > > It seems the best way to proceed would be by contradiction. If we assume p > is composite then p must have a factor r such that r = 3 mod 4, but it's not > clear where to proceed from here. THis means that Q has order 2^k = p+1 in the "group" of points modulo p. It also must have the same order in the group of points on the curve modulo any prime factor q of p. So this group will have at least p+1 points: impossible by the Hasse-Weil bound when q <= sqrt(p). -- Robin Chapman, http://www.maths.ex.ac.uk/~rjc/rjc.html "`The twenty-first century didn't begin until a minute past midnight January first 2001.'" John Brunner, _Stand on Zanzibar_ (1968) Sent via Deja.com http://www.deja.com/ Before you buy.