logo IMB
Retour

Séminaire de Théorie des Nombres

Counting points on genus 2 Jacobians with real multiplication

Benjamin Smith

( LIX, École polytechnique )

Salle de Conférences

le 06 juillet 2012 à 14:00

(Joint work with P. Gaudry and D. Kohel) We present an accelerated Schoof-type point-counting algorithm for curves of genus 2 equipped with an efficiently computable real multiplication endomorphism. Our new algorithm reduces the complexity of genus 2 point counting over a finite field \(\F_{q}\) of large characteristic from \(\widetilde{O}(\log^8 q)\) to \(\widetilde{O}(\log^5 q)\). We have used our algorithm to compute a 256-bit prime-order Jacobian suitable for cryptographic applications, and also the order of a 1024-bit Jacobian. (The previous "world record", without real multiplication techniques, was a 256-bit Jacobian).