Mathematicians have found a new way to multiply two numbers together | Hacker News Reader

Mathematicians have found a new way to multiply two numbers together

newscientist.com

8 pointssahin6 comments

What are the security implications? Does this make password cracking more feasible?

argh... non-paywall anywhere?

The paper - https://hal.archives-ouvertes.fr/hal-02070778/document

Is there a humanly readable version?

Just kidding, but although I understand the value and importance of the heavy formulation, especially under the circumstances of the media of academic papers where proofs are necessary/desirable, this will be largely useless for disseminating the knowledge of the algorithm for all but a handful of people.

We need someone to write it down for us with all the simplifications that are possible given that we 'trust' all the relevant claims (the algorithm is correct, its complexity is O(n log n), etc.) and we simply don't care for the heavier side of the proofs

The reason it isn't actually important to have a specific algorithmic implementation is that - like other exotic multiplication algorithms with better big-O complexity than the usual ones - the constant factors are much, much bigger, to the point where they would only become noticeably faster for absurdly huge integers. The theoretical aspect of this is the interesting part.

In fact, in this case the algorithm is only intended for numbers with 2^4096 bits. See section 5 of the paper:

  In this section we present the main integer multiplication
  algorithm. We actually give a family of algorithms,
  parameterised by a dimension parameter d > 2. Let n_0 :=
  2^(d^12) > 2^4096, and suppose that we wish to multiply
  integers with n bits. For n < n_0, we may use any convenient
  base-case multiplication algorithm, such as the classical
  O(n^2) algorithm.

Reply on news.ycombinator.com