asciilifeform: incidentally, if it turns out that mircea_popescu had in fact buried 10,001 opterons somewhere in the desert, now'd be the time to dig'em up. and profit margin will be very respectable.
asciilifeform: ( if mircea_popescu needed a 2009opteron for own use -- asciilifeform could, in principle, help. but if he needed a rack-house filled with them -- the gods themselves, could not help. )
asciilifeform: 'republican isp' on magicpacketable-nsaware iron...
asciilifeform: number of nsaware-free workstations or servers in production today : still 0.
asciilifeform: surprisingly tough, because the OF bit is ~not~, as is in the case of familiar add/substract, the next bit of the product ! (which, observe earlier, can actually be 0 in the case of some overflows) but stands for merely the fact that P != X*Y .
asciilifeform still chewing on a formal proof re subj
asciilifeform: Framedragger: nobody canceled, e.g., elementary theft of boxes, either
asciilifeform: ( not to mention the idiot 'attribution' thing. why the hell would usg ~not~ broadcast false bgp to point to rutelecom. )
asciilifeform: 'On Wednesday, large chunks of network traffic belonging to MasterCard, Visa, and more than two dozen other financial services companies were briefly routed through a Russian government-controlled telecom under unexplained circumstances that renew lingering questions about the trust and reliability of some of the most sensitive Internet communications.' didjaknow.
asciilifeform: and now you've given him 3x the 'broadcast', neh
asciilifeform: enemy can just as readily observe your 'blind' and 'deblind' exponentiations, as your original unblinded one...
asciilifeform: btw i'm still waiting to meet an explanation re how 'blinding' (e.g., koch's) supposed countermeasure to timing attack, is supposed to help.
asciilifeform: and so conceivably side channel remains ( not only current per se, but how does cpu current consumption affect clock jitter? betcha it does. and afaik 0 public discussion of this, exists. )
asciilifeform: also irritating is the fact that, while we have constant-time routines, it is impossible to guarantee constant-current (yes)
asciilifeform: ( as for code -- in the end it mist be entirely self-contained. and provably correct. it's a backbone for, e.g., 'tmsr rsa', 'p', eventually gossipd, etc. )
asciilifeform: mircea_popescu: i gotta come up with proper proof...
asciilifeform: mircea_popescu ^ runs in SAME space, and same order of complexity , as the old routine...
asciilifeform: ^ draft. still needs proof-of-workage.
asciilifeform: this here seems like the finalsolution, folx.
asciilifeform: when the left shifter ( x ) overflows for the first time, we set a bit, q, and clear another, r. r is set whenever right-shifter (y) overflows. now : if r is set again subsequently to q being set -- it means we overflow.
asciilifeform: you take multiplicands x, y, and accumulator a (initially 0) , and do : while y!=0: { if odd(y): { a += x } ; x <= x*2; y <= y/2 } .
asciilifeform: i'll review, for the l0gz, the 'ancient egyptian' mult algo, which is the simplest practical, and illustrative of the difficulty of determining overflow ~while doing the mult~ in fixed space.
asciilifeform: ( it is how the problem is 'solved' on all known hardware ALUs )
asciilifeform: keep in mind that 'double the available register width' IS NOT A SOLUTION !!
asciilifeform: for my purposes i could entirely do with a constant-time-and-space mult algo that knows when to set the overflow flag.
asciilifeform: let's formalize the problem statement. N is integer, N>1 . x, y are int, 0 <= x < 2^N; 0 <= y < 2^N. determine an f, such that f(x,y) is true iff x*y >= 2^2N ; such that complexity of f is less than that of * operation.
asciilifeform: however i've also not turned up a rigorous proof that it is unsolvable. which is bothersome imho.
asciilifeform: apparently this is a bona fide unsolved problem.
asciilifeform: 'This paper presents efficient methods for performing unsigned or two's complement integer multiplication with overflow detection or saturation. ' supposedly.
asciilifeform: and incidentally the given formulation doesn't work, take the first case, 0011*0110 . it turns into 001*010 = 010. the result (N-1 = 3) has 1 leading zero. no overflow. apply recurse again, we get 00*00 -- definitely no overflow, and no moar leading 1s to flip...
asciilifeform: 'If l1 + l2 = N-1 let a' be equal to a with its leading 1 set to 0, let b' be equal to b with its leading 1 set to 0, let N' = N - 1 and apply the same algorithm.' << the problem with this is that it reduces to actually DOING THE MULT
asciilifeform: now let's do mircea_popescu's third statement:
