hal-00671948, version 1

Finding ECM-friendly curves through a study of Galois properties

Razvan Barbulescu () ¹, Joppe W. Bos () ², Cyril Bouvier () ¹, Thorsten Kleinjung () ², Peter L. Montgomery () ³

Algorithmic Number Theory Symposium (2012)

• 1:  CARAMEL (INRIA Nancy - Grand Est / LORIA)
• 
  INRIA – CNRS : UMR7503 – Université de Lorraine France
• 2:  Laboratory for Cryptologic Algorithms (LACAL)
• http://lacal.epfl.ch/
  École Polytechnique Fédérale de Lausanne Station 14, CH-1015 Lausanne, Switzerland Switzerland
• 3:  Microsoft Research [Redmond]
• http://research.microsoft.com/en-us/labs/redmond/default.aspx
  Microsoft One Microsoft Way Redmond, WA 98052-6399 United States

Available versions :  v1 (2012-02-20) v2 (2012-09-04)

Bibliographic reference

• Type of document: Peer-reviewed conferences/proceedings
• Domain:

  Computer Science/Cryptography and Security

  Computer Science/Computer Arithmetic

  Mathematics/Number Theory

• Title: Finding ECM-friendly curves through a study of Galois properties
• Abstract: In this paper we prove some divisibility properties of the cardinality of elliptic curves modulo primes. These proofs explain the good behavior of certain parameters when using Montgomery or Edwards curves in the setting of the elliptic curve method (ECM) for integer factorization. The ideas of the proofs help us to find new families of elliptic curves with good division properties which increase the success probability of ECM.
• Abstract in french: Dans cet article on démontre des propriétés liées au cardinal d'une courbe elliptique quand on la réduit modulo un nombre premier aléatoire. Ces preuves expliquent le bon comportement de certains paramètres quand on implémente la méthode de factorisation par courbes elliptiques (ECM) avec des courbes de Montgomery et d'Edwards. Les idées ressorties des preuves citées auparavant ont permis la découverte de nouvelles familles de courbes elliptiques ayant de bonnes propriétés de torsion, augmentant ainsi la probabilité de succès d'ECM.
• ACM Classification: G.: Mathematics of Computing
• Full text language: English
• Publication date: 2012-02-20
• Audience: international
• Conference title: Algorithmic Number Theory Symposium
• Conference city: San Diego
• Country: United States
• Conference date: 2012-07-09
• Conference date (end): 2012-07-13
• Organizer: University of California
• Keywords: Elliptic Curve Method (ECM) – Edwards curves – Montgomery curves – torsion properties – Galois groups

Attached file list to this document: 

• hal-00671948, version 1
• http://hal.inria.fr/hal-00671948
• oai:hal.inria.fr:hal-00671948
• From: Razvan Barbulescu <>
• Submitted on: Monday, 20 February 2012 09:47:24
• Updated on: Friday, 20 April 2012 17:21:03