<UkoeHB> "Although idk how you can do..." <- docs.hackliberty.org/books/mathematics/page/understanding-rsa

Not sure if this helps you understand more but I put this together a little while ago actually if you want to take a look

Oh

For the pippenger algorithm used in monero, is there any documentation?

There is also bos-coster and strauss, maybe there are docs somewhere for those too?

Did you try googling it?

Yeah, I know how its usually implemented, but I'm struggling to figure out how its implemented in the C++ code

Trying to figure out what L623 to L649 are doing, as I've not seen the doubling part go first

in multiexp.cc

ptj5gtbtz9[m]: looks like it's bit shifting the result by c bits for each group

note that result_init starts false, so it is only executed on the second pass-through (and not at the end of the last pass-through)

As a personal comment, Straus and Pippenger feel horribly undocumented. They are specific algorithms, of course, yet Straus was a mail-in response to a 1900s mailer which lacks modern descriptions. People who work with Straus right it off as trivial, because it is, and then for Pippenger...

<UkoeHB> "ptj5gtbtz9: looks like it's..." <- Oh I see, it computes one window at a time, I'm guessing this method is not being ran in parallel then?

it's single-threaded

@ptj5gtbtz9: Considering Monero implements Straus and Pippenger, I'd recommend if you want to know the theoretical algorithm, you read through a more legible codebase. If you're curious about Monero specifically... then yeah, read Monero specifically.

for our use-case it makes more sense to run entire multiexp operations in parallel (instead of internally)

okay now it makes sense, I'm pretty bad at reading C++ so I made an incorrect assumption

kayabanerve[m]: I'm aware of how the algorithm for pippenger atleast works theoretically, I was curious as to how monero implemented it

not your fault, this implementation is very opaque

The pippenger algorithm itself is quite simple :) I have not read up on strauss though

Alrighty :) Just wanted to offer the advice in case you were unfamiliar. I try to offer from the lowest level and let people build up, just to ensure inclusion

Now I feel bad because I don't actually know Pippenger :(

every-impl does all these opaque optimizations :(

But Straus, in theory, is dead simple. I'll PM you the block for it which should be readable

<kayabanerve[m]> "But Straus, in theory, is dead..." <- Extremely useful :)

To be clear, I PMed it because I didn't have a link available and I didn't want to spam IRC. If anyone else is interested, they're welcome to ask :p

For those wondering how pippenger works, if you imagine that you want to compute: `123x+245y` You can imagine x and y are points, but it does not matter

I'll write it like this:... (full message at libera.ems.host/_matrix/media/r0/do…20c981509ec0189020630a141933b53a64b)

To get the final result I can compute col3 + col2 * 10 + col1 * 100

This is the very high level explanation without the optimisations

ah interesting

We preferably want to do 2x + 4y in a very efficient way, so the following optimisation is applied

2(x + 2y)

I assume, at least :p

Nope :) this is where the "bucket" termonology comes from haha

booooooooo math

Instead of computing 2x, you have a bucket named b_2 which you put x into , you also have a bucket named b_4 which you put y into

Now we want to get 4 * b_4 + 3 * b_3 + 2 * b_2 + b_1

We can do this efficiently by computing the following:... (full message at libera.ems.host/_matrix/media/r0/do…18df9e21d6af36ea59f7f7e8aa3eddc791d)

and summing all of those together

So instead of directly computing something like 10x + 23y, you just store x in a bucket labelled 10 and y in a bucket labelled 10 for example

There is also another optimisation with signed recoding, but monero does not currently do it I think

thanks for the lesson :)

In the example, I used the base of 10, but in code its usually a base of 2, so you will see the use of doubling/shifting in the algorithm

Np :)

* of 2^c, so

I'll try to write an impl for myself later 👀Thanks :)

Np good luck!