Representation ideas

One of the things that could make a huge difference in the speed of an algorithm is the choice of representation. Since many squarings are necessary, the cost of converting between binary and another representation only needs to be incurred once, so if there is even a slight speed-up due to a more efficient representation it is going to make a huge difference.

This thread is to collect ideas about different representations that participants might want to try implementing. I am going to start by suggesting a few that have popped up:

  1. Montgomery multiplication [1]

  2. Chinese remainder theorem based representation

This one is very exciting as squaring a number in the CRT representation is very cheap (as it can be done on the coefficients). In fact, the asymptotically fastest parallel algorithm for powering (computing x^n where x is an n-bit number) is based on this representation [2]. The tricky part is doing modular reduction, one idea is that it can be done without converting back to binary but if it is practical remains to be explored [3].

What makes this representation potentially very powerful is the ability to do a number of squarings before reduction.

  1. Number Theoretic transform

Similar to CRT, Number theoretic transform (based on the Fourier transform, but using roots of unity in finite fields rather than the complex numbers) allows local squarings. I don’t know if reduction is possible in this representation is possible or if conversion back to binary is necessary, but even then it may still be promising as again several squarings would be possible.

[1] https://www.ams.org/journals/mcom/1985-44-170/S0025-5718-1985-0777282-X/S0025-5718-1985-0777282-X.pdf
[2] https://pdfs.semanticscholar.org/29c6/f0ade6de6c926538be6420b61ee9ad71165e.pdf
[3] https://cr.yp.to/antiforgery/meecrt-20060914-ams.pdf