Finding the Eigenvalue in Elkies' Algorithm

Reference : Finding the Eigenvalue in Elkies' Algorithm


	Document type :	Scientific journals : Article
	Discipline(s) :	Engineering, computing & technology : Computer science
	To cite this reference:	http://hdl.handle.net/10993/2281

Title :	Finding the Eigenvalue in Elkies' Algorithm
Language :	English
Author, co-author :	Müller, Volker [University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC) >]
	Maurer, Markus [> >]
Publication date :	2001
Journal title :	Experimental Mathematics
Publisher :	A K Peters
Volume :	10
Issue/season :	2
Pages :	275-285
Peer reviewed :	Yes (verified by ORBi^lu)
Audience :	International
ISSN :	1058-6458
e-ISSN :	1944-950X
Keywords :	[en] Elkies algorithm ; Elliptic curve ; Point counting
Abstract :	[en] One important part of Elkies' algorithm for computing the group order of an elliptic curve is the search for an eigenvalue of the Frobenius endomorphism. In this paper we compare two well known algorithms with two new ideas based on the Babystep Giantstep method. Moreover we show how resultants can be used to speed up this search. Finally we present a fast probabilistic algorithm for checking whether a given rational function is congruent to an entry in a table of rational functions modulo some fixed polynomial.
Target :	Researchers ; Students
Permalink :	http://hdl.handle.net/10993/2281
DOI :	10.1080/10586458.2001.10504448

File(s) associated to this reference

Fulltext file(s):

	File	Commentary	Version	Size	Access
Limited access	eigenvalue.pdf		Author postprint	204.66 kB	Request a copy

All documents in ORBi^lu are protected by a user license.