The microblog: 2020.03.24 03:18:47

2020.03.24 03:18:47 (1242274634868748289) from Daniel J. Bernstein, replying to "Martin R. Albrecht (@martinralbrecht)" (1242013712434827264):

Why is there a (tau+1)/(tau-1) on the exponent of the attack cost? Computing gcd((x0-1)...(x0-R),(x1-1)...(x1-R)) uses R^(1+o(1)) operations, and then spending R^(1+o(1)) operations on ECM is practically guaranteed to trim away all the stray factors, even for tau as small as 2.


2020.03.23 10:01:59 (1242013712434827264) from "Martin R. Albrecht (@martinralbrecht)":

The Approximate GCD Problem