Xref: utzoo comp.theory:1591 sci.math:15451
Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!helios!bcm!dimacs.rutgers.edu!seismo!uunet!mcsun!unido!laura!heike-fbi!muenx
From: muenx@heike-fbi.informatik.uni-dortmund.de (Holger Muenx)
Newsgroups: comp.theory,sci.math
Subject: Algebra & Number Theory (& Elliptic Curves Primality Test)
Message-ID: <3069@laura.UUCP>
Date: 28 Feb 91 20:57:19 GMT
Sender: news@laura.UUCP
Reply-To: muenx@heike-fbi.informatik.uni-dortmund.de (Holger Muenx)
Organization: University of Dortmund, Germany
Lines: 54


Guten Tag!

In order to implement a primality test with elliptic curves I am currently
working with an article from A. K. Lenstra and H. W. Lenstra, Jr, namely
"Algorithms in Number Theory" in the "Handbook of Theoretical Computer
Science". Unfortunately, they omitted most of the proofs for the discussed
facts.

For my first question the knowledge of the article is not necessary.

They consider the imaginary quadratic field Q(sqrt(t^2-4*p)) and its ring of
integers A for a given prime p and abs(t)<2*sqrt(p) for a given integer t.
Now my problem: They claim that the following is equivalent.

	 (i) p = x*conj(x) for one x in A
	(ii) u*x is a root of X^2-t*X+p for all units u in A

In (ii) conj(x) is the complex conjugation of x. The implication (ii) => (i)
is clear if you consider the fact

	u unit <=> u*conj(u) = 1.

But how to prove (i) => (ii)?

(The authors mention this in (2.6).)

The next question deals with the kind of the primality test. You need the
lecture of the article to understand as I cannot describe all the background
here.

To my mind the Lenstras' method in (5.4) and (5.6) is a "Las Vegas" test,
meaning that the result is right if the algorithm terminates. So if the
algorithm stops you know if the considered number is a prime or not.
Unfortunately, there is a chance that the algorithm does not stop, as you
have to find a point P on an elliptic curve which matches some criteria.
On a random selected point the probality that it does not match is lower
than 1/2 but does exist. It is impractical to try all points as there
are many of them (but a finite number).

So: It is really a "Las Vegas" test or not?

Finally, my third (and last) question is why the chance to find a non-matching
point P as described above is lower than 1/2.

Any information to enhance my knowledge and understanding are appreciated.
Thanks in advance,

                                                       -Holger

===========================================================================
|| Holger Muenx, IRB, Universitaet Dortmund, 4600 Dortmund, West-Germany ||
||          Internet: muenx@heike.informatik.uni-dortmund.de             ||
===========================================================================