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

[Jacob Lifshay]

resending since libre-soc-dev apparently dropped my message...

On Mon, Oct 3, 2022, 19:46 Jacob Lifshay <programmerjake at gmail.com> wrote:

> 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
>