Fachbereich Mathematik

Veranstaltungskalender Fachbereich Mathematik

Kazuhiro Yokoyama,Rikkyo University/Tokyo: Complexity Bound on Semaev's Naive Index Calculus Method for ECDLP

Referent: Kazuhiro Yokoyama: Complexity Bound on Semaev's Naive Index Calculus Method for ECDLP

Donnerstag,  09.01.2020, 14:00 h

Raum 48-436

Abstract: Since Semaev introduced summation polynomials, a number of works have been devoted to improve index calculus algorithms for solving the elliptic curve discrete logarithm problem (ECDLP), with better complexity than generic algorithms such as Pollard's rho method. In this talk, I give a deep analysis on Groebner basis computation for a polynomial system appearing in the point decomposition problem (PDP) in a naive index calculus method. The analysis is based on linear algebra under simple statistical assumptions on summation polynomials. Specifically, I show that the ideal derived from the PDP has a special structure, and regard Groebner basis computation for the ideal as an extension of the extended Euclidean algorithm with help of the notion of signature. This allows us to obtain a precise analysis on a lower bound on the cost of Groebner basis computation.

Termine im Semester

Hier finden Sie wichtige Termine rund um Studium und Prüfungen, Sitzungen und spezielle Events für den Fachbereich Mathematik.

Zum Seitenanfang