muenx@heike-fbi.informatik.uni-dortmund.de (Holger Muenx) (03/01/91)
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 ||
===========================================================================muenx@heike-fbi.informatik.uni-dortmund.de (Holger Muenx) (03/01/91)
In article <3069@laura.UUCP>, muenx@heike-fbi.informatik.uni-dortmund.de (Holger Muenx) writes: [...] |> 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) [...] Ooops! First posting, then thinking... :-( Line (ii) above is wrong. It should be: (ii) there is at least one unit a in A so that: u*x is a root of X^2-t*X+p. Now it is right! Sorry!! -Holger =========================================================================== || Holger Muenx, IRB, Universitaet Dortmund, 4600 Dortmund, West-Germany || || Internet: muenx@heike.informatik.uni-dortmund.de || ===========================================================================
morain@seti.inria.fr (morain francois jean) (03/01/91)
In article <3069@laura.UUCP>, muenx@heike-fbi.informatik.uni-dortmund.de (Holger Muenx) writes: > > 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. Dear Holger Muenx, You might be interested in reading my thesis, which contains the theory and practice of the ECPP algorithm (or complex multiplication test), together with the material used to test 1000 decimal digit numbers for primality. Yours sincerely, Francois Morain PS: the email address you gave in yours articles seems to be unreachable. Try to answer me by email, just in case.