[Libre-soc-dev] next things to work on -- bigint rsa mul algorithm for bigint presentation

[Jacob Lifshay]

Now that the nlnet deadline is effectively over (no time left for new
work), I'd like to work on my bigint presentation:

If for some reason my presentation is rejected, this would just get
published online somewhere instead.

I want to build a practical 2048-bit modular exponentiation function for
RSA -- the subtasks should fit under
https://bugs.libre-soc.org/show_bug.cgi?id=773 and probably other gigabit
router subtasks too.

it would use montgomery multiplication and a toom-cook multiplication
algorithm generator that we can instantiate with different parameters to
find the most efficient one. toom-cook covers all of (Toom-1) traditional
O(n^2) long multiplication, (Toom-2) O(n^1.58) karatsuba multiplication,
and higher algorithms such as Toom-3 O(n^1.46)

It would be run on a simplistic model cpu with 1 256-bit simd add unit and
1 256-bit wide-mul unit (the model would be adjustable) and scalar units, I
would create a simulator for that, the simulator would cover ALU pipeline
timing and dependencies but not much else. the simulator would be designed
to output timing info such that blender can generate an animation of those
ALUs executing the algorithm. the simulator would probably be written in
python and use our existing isacaller simulator to generate execution
traces for it to run on.

I'm estimating this taking 3-4 weeks of work, it would probably be the most
significant demo of svp64 actually providing a significant speed-up so far
(isacaller doesn't count since it doesn't simulate actual cpu timing,
soc.git isn't far enough along to simulate multi-issue and operation
merging for SIMD backends).

this would cover the last half of the bigint presentation, the first half
would be explaining concepts.

What do you think?

Jacob