01:14:23 <Ackermann[m]> <UkoeHB> "Although idk how you can do..." <- https://docs.hackliberty.org/books/mathematics/page/understanding-rsa
01:14:23 <Ackermann[m]> 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 
01:19:43 <Ackermann[m]> Oh 
20:50:26 <ptj5gtbtz9[m]> For the pippenger algorithm used in monero, is there any documentation?
20:51:33 <ptj5gtbtz9[m]> There is also bos-coster and strauss, maybe there are docs somewhere for those too?
20:58:07 <UkoeHB> Did you try googling it?
20:59:06 <ptj5gtbtz9[m]> Yeah, I know how its usually implemented, but I'm struggling to figure out how its implemented in the C++ code
21:01:59 <ptj5gtbtz9[m]> Trying to figure out what L623 to L649 are doing, as I've not seen the doubling part go first
21:02:10 <ptj5gtbtz9[m]> in multiexp.cc
21:17:14 <UkoeHB> ptj5gtbtz9[m]: looks like it's bit shifting the result by c bits for each group
21:19:27 <UkoeHB> 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)
21:22:33 <kayabanerve[m]> 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...
21:22:54 <ptj5gtbtz9[m]> <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?
21:23:07 <UkoeHB> it's single-threaded
21:23:32 <kayabanerve[m]> @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.
21:23:35 <UkoeHB> for our use-case it makes more sense to run entire multiexp operations in parallel (instead of internally)
21:23:48 <ptj5gtbtz9[m]> okay now it makes sense, I'm pretty bad at reading C++ so I made an incorrect assumption
21:24:23 <ptj5gtbtz9[m]> kayabanerve[m]: I'm aware of how the algorithm for pippenger atleast works theoretically, I was curious as to how monero implemented it
21:24:24 <UkoeHB> not your fault, this implementation is very opaque
21:24:55 <ptj5gtbtz9[m]> The pippenger algorithm itself is quite simple :) I have not read up on strauss though
21:25:16 <kayabanerve[m]> 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
21:25:23 <kayabanerve[m]> Now I feel bad because I don't actually know Pippenger :(
21:25:35 <kayabanerve[m]> every-impl does all these opaque optimizations :(
21:25:52 <kayabanerve[m]> But Straus, in theory, is dead simple. I'll PM you the block for it which should be readable
21:32:07 <ptj5gtbtz9[m]> <kayabanerve[m]> "But Straus, in theory, is dead..." <- Extremely useful :)
21:32:28 <kayabanerve[m]> 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
21:33:03 <ptj5gtbtz9[m]> 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
21:35:08 <ptj5gtbtz9[m]> I'll write it like this:... (full message at https://libera.ems.host/_matrix/media/r0/download/libera.chat/4307a20c981509ec0189020630a141933b53a64b)
21:35:34 <ptj5gtbtz9[m]> To get the final result I can compute col3 + col2 * 10 + col1 * 100
21:36:01 <ptj5gtbtz9[m]> This is the very high level explanation without the optimisations
21:36:03 <UkoeHB> ah interesting
21:36:54 <ptj5gtbtz9[m]> We preferably want to do 2x + 4y in a very efficient way, so the following optimisation is applied
21:37:06 <kayabanerve[m]> 2(x + 2y)
21:37:26 <kayabanerve[m]> I assume, at least :p
21:37:29 <ptj5gtbtz9[m]> Nope :) this is where the "bucket" termonology comes from haha
21:37:35 <kayabanerve[m]> booooooooo math
21:38:15 <ptj5gtbtz9[m]> 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
21:39:03 <ptj5gtbtz9[m]> Now we want to get 4 * b_4 + 3 * b_3 + 2 * b_2 + b_1
21:39:53 <ptj5gtbtz9[m]> We can do this efficiently by computing the following:... (full message at https://libera.ems.host/_matrix/media/r0/download/libera.chat/0c72018df9e21d6af36ea59f7f7e8aa3eddc791d)
21:40:05 <ptj5gtbtz9[m]> and summing all of those together
21:40:50 <ptj5gtbtz9[m]> 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
21:41:50 <ptj5gtbtz9[m]> There is also another optimisation with signed recoding, but monero does not currently do it I think
21:43:14 <UkoeHB> thanks for the lesson :)
21:43:19 <ptj5gtbtz9[m]> 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 
21:43:42 <ptj5gtbtz9[m]> Np :)
21:43:43 <ptj5gtbtz9[m]> * of 2^c, so
21:48:56 <kayabanerve[m]> I'll try to write an impl for myself later 👀Thanks :)
21:49:51 <ptj5gtbtz9[m]> Np good luck!