Speaker: Andrew N. W. Hone (University of Kent, UK)

Date and time: 22.04.2020, 16:00

Talk title: Efficient ECM factorization in parallel with the Lyness map  

Abstract:  The Lyness map is a birational map in the plane which provides one of the simplest discrete analogues of a Hamiltonian system with one degree of freedom, having a conserved quantity and an invariant symplectic form. As an example of a symmetric Quispel-Roberts-Thompson (QRT) map, each generic orbit of the Lyness map lies on a curve of genus one, and corresponds to a sequence of points on an elliptic curve which is one of the fibres in a pencil of biquadratic curves in the plane. Here we present a version of Lenstra's elliptic curve method (ECM) for integer factorization, which is based on iteration of the Lyness map with a particular choice of initial data. More precisely, we give an algorithm for scalar multiplication of a point on an elliptic curve, which is represented by one of the curves in the Lyness pencil. We explain how this might be implemented efficiently, using suitable projective coordinates, by performing the calculations in parallel using four processors, and make a brief comparison with state of the art methods. This is an introductory talk: no prior knowledge of factorization algorithms, or Lyness maps, is assumed.

To access the online seminar please contact a.tolbey@uniyar.ac.ru