asciilifeform: afaik this cannot be done without a physical barrel shifter of the given bitness.☟︎
asciilifeform: incidentally if apeloyee or anybody else knows how to make a 1..ffabitness shifter that doesn't leak the shift amount, on ordinary pc, plz post.
asciilifeform: if that's barrett, it'll be barrett. if it's knuthian, will be knuthian. if newtonian -- newtonian. in no case it will be montgomery, say, or any other non-universal one.
asciilifeform: apeloyee: i want the fastest possible universal reduction that works in fixed spacetime and provably so
asciilifeform: ( and when we do rsa, can store the reciprocal in the key, there's no particular reason to compute it every time )
asciilifeform: the cost of 1 knuthian div is negligible
asciilifeform: still 1 knuthian div, vs the 8192 i have now (in the example)
asciilifeform: apeloyee: my principal problem with barrett is that i don't have a proof that it works with 3 or fewer corrective-subtractions for ALL possible a,b,m in a*b mod m
asciilifeform: and this is only the beginning of the ugh
asciilifeform: mircea_popescu: if 1 gets to be a prime, you then throw out the conventional def of prime, because now you have a prime that divides other primes unequal to itself
asciilifeform: ( really a lengthy .txt , but can be formatted however wanted )
asciilifeform: well naturally whole thing is to be an article.
asciilifeform: will be interesting if any reply, considering how the thing obsoletes half the idiocy they currently print
asciilifeform: mircea_popescu: i've been thinking about sending ffa , when finished, as an article into the saecular derps' 'cryptology journals', strictly for the lulz of getting their reject barf , and then posting, a la al schwartz
asciilifeform: mircea_popescu: lookx to me like your addition dun commute ( or associate... )☟︎
asciilifeform: i'd prefer a macroscale numbertheoretical hash, even one that explicitly stands on strength of, e.g., rsa, to the currently extant soup.
asciilifeform: and incidentally i dun have a nonleaking miller-rabin yet, need nonleaking gcd ( have on paper, but not in ffa yet )☟︎
asciilifeform: mircea_popescu: anything involving 'isprime()' during everyday life is either a table lookup (leaks!) or miller-rabin (slow as fuck, temptation to cut iterations and introduce eggog)
asciilifeform: and imho there is a serious problem with 'not ARX' in linked piece : omitting additions makes the hash ~considerably~ nsa-friendlier : it is easier to implement xor/and/not/shift on, e.g., optical computer, when you don't need addition (and ergo carries)
asciilifeform: ( plenty of known basis for ~weaknesses~ of various . the absence of which, in any particular case, has NO bearing on above. )
asciilifeform: TomServo: there is no scientific basis for the strength of ANY published hash algo whatsoever.
asciilifeform: bonus lul: https://archive.is/tK1o1 << list of public catastrophic bugs in bigint libs . bonus-2 : compiled by the perpetrators of mit's attempt at faux-ffa ( won't link separately, it's a megalith of mechanical 'proof' crapolade )
asciilifeform: ( ...handwaves!1!11!... ) this sums to a potential 25% saving of clock , if finessed.
asciilifeform: there are a total of Bitness * DividendWordness cycles , in this example 64*128 == 8192
asciilifeform: it isn't actually necessary to touch the entire R for the first Bitness*(RemainderWordness-1) (on 64-bit box, and for the 4096b example, that's 64*63 == 4032 ) shots of the inner loop !
asciilifeform: ( hint re FZ_Mod : notice that the first Bitness shift-lefts are really single-word; and same is true of the subtraction, and of the mux; the next Bitness ditto and ditto -- are really 2-word ops; and so on. )
asciilifeform: i ain't linking to pediwikian bowdlerizations , and there is no other source afaik .
asciilifeform: ( the 'corrector' at the end of barrett will have to go through a mux, and fire a fixed # of times, and gotta prove that this-many and no-greater suffices. )
asciilifeform: but i will need an ironclad proof that it worx for ALL possible inputs.
asciilifeform: with barrett, modexp should go back to below-1sec @ 4096b .
asciilifeform: ultimately it would make sense to use barrett reduction but currently i am not satisfied with the proof that it converges ( for some reason, every statement of this proof that i could find, seems to exclude reduction by powers of 2, and i do not yet understand why )
asciilifeform: all of this - naturally - remains properly constantspacetime and unrollable.
asciilifeform: alert reader will also notice that FZ_Mod is now ok with half-width divisors, eliminating the copying in FZ_Mod_Mul and FZ_Mod_Square .
asciilifeform: ^ no barrett yet. and there is still room for polish in barrettless variant, there is still a great deal of avoidable shifting and subtraction of guaranteed-empty words in FZ_Mod ( exercise for alert reader, to see where ! )
asciilifeform: in other noose, asciilifeform found that 1) knuthian division can be sped up by ANOTHER factor of 2, by walking the bits of the quotient instead of shifting'em 2) barrett reduction in constant time is almost certainly possible☟︎
asciilifeform: in this sense 'everything exists' in elvish.
asciilifeform: google trans or similar with a small bit of manual delousing (or perhaps not even)
