[Libre-soc-bugs] [Bug 942] New: next things to work on -- bigint rsa mul algorithm for bigint presentation

[bugzilla-daemon at libre-soc.org]

https://bugs.libre-soc.org/show_bug.cgi?id=942

            Bug ID: 942
           Summary: next things to work on -- bigint rsa mul algorithm for
                    bigint presentation
           Product: Libre-SOC's first SoC
           Version: unspecified
          Hardware: Other
                OS: Linux
            Status: CONFIRMED
          Severity: enhancement
          Priority: ---
         Component: Conferences
          Assignee: programmerjake at gmail.com
          Reporter: programmerjake at gmail.com
                CC: libre-soc-bugs at lists.libre-soc.org, lkcl at lkcl.net,
                    programmerjake at gmail.com
   NLnet milestone: ---

posting here because libre-soc-dev is currently broken.

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?

-- 
You are receiving this mail because:
You are on the CC list for the bug.