asciilifeform smashes head into desk

asciilifeform: but instead 3 smallers

asciilifeform: so as not to feed a massive turd into an O(N^3) division algo

asciilifeform: i thought you had algo for not having to add'em

asciilifeform: waitasec didja.... add them?!

asciilifeform: ( and what part of (a+b) mod m == (a mod m) + (b mod m) is breakable with infinitely many a,b,m values, is hard ? try it yourself )

asciilifeform: ( i promise i have nfi how to do it. just like i don't know how to make 2+2=5 )

asciilifeform: let's hear?

asciilifeform: because it dun distribute.

asciilifeform: nope. and nobody else does either afaik.

asciilifeform: true

asciilifeform: lol

asciilifeform: ( this is the 'new' karatsuba, simplified, and demands powers-of-two-bitnessed operands. should be easier to read than old.)

asciilifeform: it and the prev, http://btcbase.org/log/2017-09-12#1712905 . ☝︎

asciilifeform: *paste

asciilifeform: i highly recommend to read the past 1st, it is not long

asciilifeform: mircea_popescu: all we got atm for mod is http://btcbase.org/log/2017-09-12#1712980 . nothing moar. ☝︎

asciilifeform: and if mircea_popescu writes one -- i dun care if in fortran, cobol, malbolge, whichever, so long as it's something resembling a proggy -- i promise to read.

asciilifeform: what we do not have -- and don't have because it doesn't actually work -- is the karatsuba cut for modular mult.

asciilifeform: that one -- we already ahve (see the paste, and the old pastes)

asciilifeform: i was speaking specifically of the division algo

asciilifeform: but modulus only is distributive over multiplications, not additions.

asciilifeform: and yes it'd be 133337 if it worked, we would have a direct modular equivalent of karatsuba

asciilifeform: aha mod

asciilifeform: 1) mircea_popescu describes algo for mod. 2) turns out exactly knuths's, that is in existing ffa 3) describes 'do it to each term of a+b+c in karatsuba' 4) this dun work, if it worked we would be bragging about the new 133337 recursive modular mult algo we've got

asciilifeform: i think we missed a step in the thread

asciilifeform: exactly as was stated.

asciilifeform: problem is exactly 'modular multiplication without division'

asciilifeform: aside from the fact that i already wrote it in july -- nuffin

asciilifeform: 'restoring division' in vol2 of knuth.

asciilifeform: it's == to the existing one.

asciilifeform: ( and worth keeping in mind that in ffaworld adding two B-bit integers does NOT give a B-bit integer, it gives a B+W bit one. where W is our word width. )

asciilifeform: so i'd say it yes would be worth cycles. if anybody knew of an algo.

asciilifeform: well we are talking about a O(NlogN) rsa vs a O(N^5) one

asciilifeform: any other takers?

asciilifeform: suggest something that doesn't reduce to my existing algo ?

asciilifeform: 'distributive' means that you can do the above. and you can't.

asciilifeform: ( do i need to list contradiction, or is it obvious )

asciilifeform: died pretty quickly.

asciilifeform: try (n+3) mod m =?= (n mod m) + (3 mod m)

asciilifeform: the fundamental problem is that mod is not actually distributive.

asciilifeform: this is not one iota cheaper than what i have here.

asciilifeform: for reference

asciilifeform: http://wotpaste.cascadianhacker.com/pastes/oVOak/?raw=true << subj ☟︎

asciilifeform: with the subtract

asciilifeform: and you restated knuth's division algo again

asciilifeform: any mention of 'if' turns into 'do BOTH and then mux'

asciilifeform: we can't 'if'

asciilifeform: well yes. but how the hell do i distribute mod. observe in http://btcbase.org/log/2017-09-12#1712923 it dunwork. ☝︎

asciilifeform: this is still a restatement of the thing i asked for tho. i do not know of a way to distribute mod.

asciilifeform: ( one answer is that at the very bottom of the barrel, where karatsuba hits the basecase comba mult, we permit division )

asciilifeform: before you do, say how to compute the mods without division.

asciilifeform: whereas nao we have http://btcbase.org/log/2017-09-12#1712830 ☝︎

asciilifeform: if you could do this, you'd save much moar than 10% , because wouldn't have division anywhere

asciilifeform: and from where got the 3

asciilifeform: single pass of knuth where

asciilifeform: go upstack plox,

asciilifeform: and EVERY SHOT OF EVERY SUBOP must be pessimal

asciilifeform: because again constanttime

asciilifeform: and yes you gotta subtract ALL of the words, even if it is obvious that subtractand does not go into the scratch

asciilifeform: if you're taking about the division, we already have this.

asciilifeform: no 'but first bit...' etc.

asciilifeform: it ain't constanttimespace.

asciilifeform: we dun get to do this

asciilifeform: 3.

asciilifeform: 1mod2=1, 1mod2=1, 1mod2=1, but 1+1+1 = ... ☟︎

asciilifeform: take trivial case, a=b=c=1 and n=2

asciilifeform: try it yerself

asciilifeform: sadly.

asciilifeform: xy = (a+b+c), but xy mod n != (a mod n)+(b mod n)+(c mod n)

asciilifeform: ( nao if only modulus were a distributive operation ! then could take mod for each of the 3 addition arguments inside karatsuba, and we'd be golden )

asciilifeform: http://wotpaste.cascadianhacker.com/pastes/uLQBe/?raw=true << karatsuba, for reference ☟︎

asciilifeform: lol

asciilifeform: this is called slidingwindow and it's what koch does.

asciilifeform: that ain't constantspacetime

asciilifeform: mircea_popescu: elaborate?

asciilifeform: mircea_popescu: the classical ffa exponentiator, for reference, looks like http://wotpaste.cascadianhacker.com/pastes/S4dWM/?raw=true . the ~modular~ exponentiator must look like http://wotpaste.cascadianhacker.com/pastes/AiB9t/?raw=true . however it needs 'first, steal the chicken', i.e. FZ_Mod_Mul and FZ_Mod_Square .

asciilifeform: then yes

asciilifeform: rothbart: where did you get your existing one ?

asciilifeform: ( because if you are doing anything other than karatsuba for mult of whatever variety, you're sunk )

asciilifeform: the approach i've been (futile, so far) taking is, to find a way to interleave modularization into karatsuba

asciilifeform: and oh did i mention 3) idiot specialforms (e.g. barrett's) , because if mother dropped you as a child specialform constraints on moduli seem like ok idea

asciilifeform: ( EVERYBODY, without exception, 1) did something intrinsically nonconstanttime 2) lied about it in print )

asciilifeform: the literature has been screamingly, frothing-at-the-mouth antihelpful

asciilifeform: i've been fighting with the modular mult thing since july

asciilifeform: lol

asciilifeform: which are the only reason we are able to do anything reasonably efficiently at all

asciilifeform: other than taking away O(1) machine shifts

asciilifeform: what would that do ?

asciilifeform: to arbitrary base ?

asciilifeform: and it is not only O(N^3), but when you modularly exponentiate it actually gets done B times, and not to B-sized inputs, but 2B ( because we have a multiply and then also a square, in each step of the B-step modular exponentiation bitwise )

asciilifeform: ^ you just described knuth division lol

asciilifeform: i am referring, of course, to the standard shift-and-substract knuth division, which is in the previously posted ffa

asciilifeform: (B being bitness )

asciilifeform: and it happens B^2 times ☟︎

asciilifeform: it's an O(N^3) op

asciilifeform: mircea_popescu: ruinously

asciilifeform: mine took more than a week

asciilifeform: rothbart: still waiting for shitcoin node to sync ?

asciilifeform: rothbart: ( summary : we discovered that gpg is a turd, and is to be burned down, not encased in iron )