BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Gabrielle De Micheli (UCSD) DTSTART:20220210T220000Z DTEND:20220210T230000Z DTSTAMP:20260423T024657Z UID:UCSD_NTS/55 DESCRIPTION:Title: Lattice Enumeration for Tower NFS: a 521-bit Discrete Logarithm Computat ion\nby Gabrielle De Micheli (UCSD) as part of UCSD number theory semi nar\n\nLecture held in APM 6402 and online.\n\nAbstract\nThe Tower variant of the Number Field Sieve (TNFS) is known to be asymptotically the most e fficient algorithm to solve the discrete logarithm problem in finite field s of medium characteristics\, when the extension degree is composite. A ma jor obstacle to an efficient implementation of TNFS is the collection of a lgebraic relations\, as it happens in dimensions greater than 2. This requ ires the construction of new sieving algorithms which remain efficient as the dimension grows. In this talk\, I will present how we overcome this d ifficulty by considering a lattice enumeration algorithm which we adapt to this specific context. We also consider a new sieving area\, a high-dimen sional sphere\, whereas previous sieving algorithms for the classical NFS considered an orthotope. Our new sieving technique leads to a much smaller running time\, despite the larger dimension of the search space\, and eve n when considering a larger target\, as demonstrated by a record computati on we performed in a 521-bit finite field GF(p^6). The target finite field is of the same form as finite fields used in recent zero-knowledge proofs in some blockchains. This is the first reported implementation of TNFS.\n \nIn the pre-talk\, I will briefly present the core ideas of the quadratic sieve algorithm and its evolution to the Number Field Sieve algorithm.\n\ npre-talk at 1:20pm\n LOCATION:https://researchseminars.org/talk/UCSD_NTS/55/ END:VEVENT END:VCALENDAR