asciilifeform: ( so sometimes 'not used', but the discarding takes provably same time as nondiscarding )

asciilifeform: the output is muxed via constanttimemuxer

asciilifeform: we do 4 motherfucking squares, and 4 subtracts

asciilifeform: we dun branch!!!

asciilifeform: read mine.

asciilifeform: 4

asciilifeform: nope.

asciilifeform: (it subtracts EVERY time, then muxes )

asciilifeform: at least mine doesn't

asciilifeform: division dun branch on seekrit

asciilifeform: how?

asciilifeform: and division is O(N^2).

asciilifeform: it'll be pretty sad, because squaring gives a doublewide bitness.

asciilifeform: ( exp-via-squaring, mod after each squaring )

asciilifeform: this weekend i'ma see just how sad is key genning with the saddest but proper algo , quoted earlier.

asciilifeform: makes the rest of ffa an exercise in complete pointlessness, to use anything of the kind.

asciilifeform: therefore rubbish.

asciilifeform: not unrollable.

asciilifeform: it needs branching omfg

asciilifeform: mircea_popescu: this is the sliding window in gpg2.

asciilifeform: nogood tho. because cannot be expressed as FINITE, KNOWN (for particular ffawidth) sequence of good ol'fashioned word-arithmetic ops.

asciilifeform: ( because table lookups are nonconstanttime on just about any iron you can get your hands on. caches. )

asciilifeform: also uses the same idiotic sliding window thing that makes gpg2 radiate seekritbranchingly for kilometres

asciilifeform: branches.

asciilifeform: it dun go

asciilifeform: found it back in may

asciilifeform: wassat

asciilifeform: hm?

asciilifeform: need same thing here again.

asciilifeform: recall, constanttime karatsuba did not (afaik) publicly exist before i posted it...

asciilifeform: want -- faster.

asciilifeform: aha. we have one.

asciilifeform: elementarily.

asciilifeform: alwaysworstcase.

asciilifeform: that's what constanttime is

asciilifeform: always-worstcase modexp

asciilifeform: we want the opposite

asciilifeform: (i.e. always-worstcase)

asciilifeform: ain't looking for the rsa pill here. but for nonretarded variant of montgomery's algo

asciilifeform: depends what means 'good solution'

asciilifeform: thinkaboitit

asciilifeform: mircea_popescu: if it did not look like this, rsa would not even be useful

asciilifeform: but if anyone has better idea -- write in

asciilifeform: ( for 3 wks or so nao... )

asciilifeform: currently trying to express montgomery reduction ffaically.

asciilifeform: aha!

asciilifeform: there is not an equiv of karatsuba for it

asciilifeform: division is the single most expensive arithmetic op.

asciilifeform: sloooow

asciilifeform: http://wotpaste.cascadianhacker.com/pastes/HuJDk/?raw=true << for anybody who forgot how division worx.

asciilifeform: FZ_Mod(B, M, B)

asciilifeform: grr,

asciilifeform: ( for modexp, that is )

asciilifeform: the sad and slow constantspacetime solution , is the same exponentiation-by-squaring ffa has now, http://wotpaste.cascadianhacker.com/pastes/BVxyN/?raw=true , but after FZ_Square(B, B, C_Sqr); we FZ_Mod(B, M B) every time.

asciilifeform: because antifitsinhead.

asciilifeform: it was the most effective optimization i knew, and the one i rejected first and most incurably.

asciilifeform: incidentally various heathen bignumtrons use carry-save form. it is one of the reasons why they are 10,000s of lines, and mine is ~1k.

asciilifeform: nor subtract

asciilifeform: can't 'add in any order you wish'

asciilifeform: there is carry.

asciilifeform: mno.

asciilifeform: where, e.g., word addition, is sequential.

asciilifeform: we cannot do this. because the simplicity of ffa comes from using strictly ordinary machineword arithmetic.

asciilifeform: by ignoring the carry, and reconstituting later

asciilifeform: understand, that's how he makes the ops independent ( rather than chained )

asciilifeform: which dun work with conventional machine arithm

asciilifeform: also his thing uses carry-save form

asciilifeform: ( the infallible litmus for ffability : 'can this be UNROLLED TO DEATH?' if not -- no go )

asciilifeform: i dun see it

asciilifeform: if you can picture a branch-free form, lemme know

asciilifeform: any practical modexp algo has to 'mod as it goes along'

asciilifeform: so that falls out trivially.

asciilifeform: now if you were to try to rsa by exping first and THEN mod, the universe could not hold your intermediates

asciilifeform: no reason why it oughta

asciilifeform: (' a little bit ' of seekrit-branch is same as 'little big pregnant' )

asciilifeform: otherwise whole thing is a massive waste.

asciilifeform: it is the only acceptable form for ptron.

asciilifeform: where control flow is SAME regardless of what the exponentiation args are.

asciilifeform: what is needed is a wholly algebraic process. like my mult. ☟︎

asciilifeform: ergo much branching. and all of it on seekrit bits.

asciilifeform: you can , but still have the 'guessing and undo' thing

asciilifeform: ( rather than word arithm )

asciilifeform: aha. wants fast bittwiddle

asciilifeform: AND branches on seekrits.

asciilifeform: it's catastrophically slow on general-purpose comp

asciilifeform: he's the d00d with the '90s rsa chip

asciilifeform: or, more formally, no way to prove the absence of arbitary number of classes of 'easy case'

asciilifeform: (problem from 'use as cryptosystem' pov)

asciilifeform: (no way to prevent 'easy case')

asciilifeform: has same problem as every other nphard

asciilifeform: ( generating ideal additionchain for a particular exp, incidentally, is np-hard )

asciilifeform: and as such is unsuitable for ptron

asciilifeform: knuth has one with 'addition chains', but it requires the exponent to be welded into place for all time

asciilifeform: ^ if asciilifeform is wrong here, folx, plz to write in !!

asciilifeform: ( every single motherfucking modexp in the open lit, branches on seekrit )

asciilifeform: turns out, none is publicly known.

asciilifeform: anyway this is the easy bit. hard bit apparently is the final crown, coughing up a sane modexp

asciilifeform: tabula proof!

asciilifeform: currently i lean to unrolling them ~in the proof doc~ and leaving proggy as is.

asciilifeform: we definitely don't need any case of comba above 8 tho