Faster Index Calculus for the Medium Prime Case Application to 1175-Bit and 1425-Bit Finite Fields
Many index calculus algorithms generate multiplicative relations between smoothness basis elements by using a process called Sieving. This process allows filtering potential candidate relations very quickly, without spending too much time to consider bad candidates. However, from an asymptotic point of view, there is not much difference between sieving and straightforward testing of candidates. The reason is that even when sieving, some small amount time is spend for each bad candidates. Thus, asymptotically, the total number of candidates contributes to the complexity. In this paper, the authors introduce a new technique: Pinpointing, which allows user to construct multiplicate relations much faster, thus reducing the asymptotic complexity of relations' construction.