Comments on: Experiment: N-Way Split Karatsuba http://bvt-trace.net/2019/01/experiment-n-way-split-karatsuba/ Fri, 21 Aug 2020 17:12:42 +0000 http://polimedia.us hourly 1 By: Stanislav Datskovskiy http://bvt-trace.net/2019/01/experiment-n-way-split-karatsuba/#comment-6 Stanislav Datskovskiy Sun, 20 Jan 2019 15:52:13 +0000 http://bvt-trace.net/?p=14#comment-6 The variant given here is also known as Toom–Cook algorithm. It is complicated, and, on top of that, does not win in application to the sizes of integer typically used in crypto. Which is why I did not use it (or any other "heavies", e.g. Strassen's, Fuhrer's, etc) in FFA. Re: FFT: A hypothetical constant-time FFT multiplier would be interesting. AFAIK there is not an approach known to this. The variant given here is also known as Toom–Cook algorithm.

It is complicated, and, on top of that, does not win in application to the sizes of integer typically used in crypto. Which is why I did not use it (or any other "heavies", e.g. Strassen's, Fuhrer's, etc) in FFA.

Re: FFT: A hypothetical constant-time FFT multiplier would be interesting. AFAIK there is not an approach known to this.

]]> By: Mircea Popescu http://bvt-trace.net/2019/01/experiment-n-way-split-karatsuba/#comment-5 Mircea Popescu Sun, 20 Jan 2019 15:35:22 +0000 http://bvt-trace.net/?p=14#comment-5 The fundamental problem with math-as-images is the most curdling aspect of all this ; otherwise, it's not particularly surprising n-way is slower than 1-way for this application, and as you say it thus has no practical utility beyond education. The fundamental problem with math-as-images is the most curdling aspect of all this ; otherwise, it's not particularly surprising n-way is slower than 1-way for this application, and as you say it thus has no practical utility beyond education.

]]>