Let N and M be arbitrary 1024+ bit integers.
The objective is to compute the product of N and M (2048+ bits)
There exist various multiplication algorithms for various bit lengths (ex library: GMP). But there is always the assumption that both numbers are equally arbitrary.
Are there algorithms that are even faster under the assumption that for every time N changes, M changes K times with K being 2^20 or more?
An algorithm that given an integer, constructs/primes a special fast algorithm to compute a product just for that integer.
The only algorithm of this kind that I was able to find and that gave rise to this question is described in this paper: https://sci-hub.tw/10.1007/s00224-020-09986-5
C code provided by the author (GMP lib): http://www.fit.vutbr.cz/~ibarina/tmp/n.c
Summary: Uses the Collatz conjecture to do multiplication, O(Nk) where k is the number of odd integers in the Collatz sequence of a given odd operand. If k < log N it can beat current state of the art multiplication algorithms.