asciilifeform: ( as for the other thing -- much of asciilifeform's oddball 'must work for all integers!' thrust, is on acct of his interest in cryptosystems other than classic rsa, e.g. c-s and variations on theme )
asciilifeform: rather than to hold up orchestra for its gilding.
asciilifeform: upstack, i'ma polish off stein, and see if the lily in fact needs gilding ~after~
asciilifeform: ( apeloyee originally proposed it as substitute for primality testing per se; where it elementarily constricts the domain of possible primes, and is unacceptable per my lights )
asciilifeform: mircea_popescu: the 'lose variety of primes' was my objection to using wholly-constructed primes. rather than in prelude to m-r .
asciilifeform: rather than 'watch out, be sure that you constructed right inputs, or you might get soup'
asciilifeform: so , my spec was 'all operators do The Right Thing arithmetically, and program stops if you demand div0' , like yer cpu does.
asciilifeform: mircea_popescu: barrett is the 1 that actually works for all integers without restricted domain.
asciilifeform: ( and if you montgomery, then you gotta either test whether gcd(N, modulus) == 1 , or ~assume~ , the latter is a mine that user will step on. unlike div0ism , it is not an inexpensive test . )
asciilifeform: http://btcbase.org/log/2019-01-06#1884935 << i actually considered to have 'if low bit is 0 - i.e. N is even -- then montgomery, otherwise barrett' but what this does is break constanttimeism of modexp -- nao you broadcast the parity of N for whole planet, cuz entirely diff execution profiles for the 2 algos. and montgomery is at the very most a 10% revvup over barrett.☝︎
asciilifeform: not particularly relevant to the problem of general-purpose isPrime() tho, so i'ma put it back on shelf for nao.
asciilifeform: ( mircea_popescu is elementarily correct here )
asciilifeform: grr nao i gotta find the orig statement, which wasn't obv. broken
asciilifeform: ( why this is, is because for certain types of pubkeycrypto, you want to test adjacent nums for primality. rsa in particular. )
asciilifeform: oh hm i recall nao. ( it was because operator 'P' wants to be a general-purpose primality test, valid for any input whatsoever that fits in the ffawidth, rather than simply 'generate prime' )
asciilifeform: i can't recall why i barfed tho, nao i gotta dig out the notes...
asciilifeform: btw iirc apeloyee had a comment re 'why do you want to gcd(x, primorial), why dontcha generate a random x and multiply it by primorial + 1 '
asciilifeform: mircea_popescu: nonzero rule is elementarily cuz you cant div0.
asciilifeform: anyway i suspect that i'm overmassaging this particular piece, most of cost of primegen will be in m-r regardless of how i bake gcd.
asciilifeform: so happens that it is needed as a general-purpose knob tho.
asciilifeform: yes , you can do this is if all you want gcd for is primegen.
asciilifeform: tho i finally see what mircea_popescu was getting at earlier re daykin.
asciilifeform: and yes it is possible to daykin with a hardcoded list of primorials, 1 for each possib bitness. the issue aint even that you gotta keep around e.g. 8192 primorials; ( you do, they can't be sliced ) , but that it leaks the bitness of X .
asciilifeform: whole point is that it tests for divisibility by million small primes in 1 pull of trigger.
asciilifeform: mircea_popescu: if you gotta do multiple calls to gcd to take gcd(x, primorial) you lose the win from using gcd.
asciilifeform: it is used to take gcd(x, primorial(currentwidth)) , and if it dun equal 1 or x , then x is 'cheaply known composite' .
asciilifeform: orig q was whether it is possible to improve the constant factor of stein.
asciilifeform: this much is correct, and why i have gcd to begin with. right nao i have a modified stein that goes in constanttime.
asciilifeform: gcd(x, primorial) gotta use same instructions when x = 0, 1, ... as when it equals 2^ffawidth - 1 .
asciilifeform: on top of this, if you actually carry out a diff stream of instructions for 2047 and 2048, you leak the bitness of the integer under test.
asciilifeform: ( would be nifty if it were, tho... )
asciilifeform: primorial that fits in, e.g., 2047 bits, is not equal to '1st 2047 bits of primorial that fits in 2048'
asciilifeform: ( storing e.g. 8192 primorials, ~would~ work, tho ugly, but ~would~ leak the bitness when fired )
asciilifeform: 'product but up to bitness' dun do the same job
asciilifeform: soo hm, what's the idea, 8192 stored primorials ?
asciilifeform: ( i suspect btw that if there were , you could nail rsa, thinkaboutit )
asciilifeform: mircea_popescu: magic # primorials are unavoidable. but i dun immediately see how to make it go with daykin, there aint a bailey-borwein-plouffe-style algo for gcd
asciilifeform: and even a dog-slow gcd is still faster than knuth-division by each of million smallprimes.
asciilifeform: this isnt catastrophic (or surprising, apeloyee warned about it yr+ ago) , and the only place where need gcd is the pre-millerrabin primorial 'divisible by small primes?' litmus. but would still be good to cut the constant down.
asciilifeform: so anyffin we do for gcd is gonna be quadratic, q is strictly re the constant factor.
asciilifeform: (i.e. working subquadratically in worst-case)
asciilifeform: it is interesting to note, i did an exhaustive dig re gcd algos; and found that there are half a dozen sub-quadratic ones, but none of those can be made constant-time.
asciilifeform: ( e.g. 64 bits worth of 'increment this 4096-bit fz by 1' is roughly 400 years... )
asciilifeform: you get a potentially 'geological' number of steps that increment by 1.
asciilifeform: mircea_popescu: in moar pedestrian matters : daykin's algo , turns out, aint good for much -- at least, not in anyffin like orig form. consider the case where P is large ( but not at all close to complement(P) ) and Q is 1.
asciilifeform: this concludes the 'state of asciilifeform' broadcast for nao -- plox to lemme know if i missed sumthing.
asciilifeform: to entirely round off the chalkboard, mircea_popescu may be interested to know that no one has called the 1-800 since we last spoke of it. the current summed cost stands at 12 orcbux, and is set to increment by 22 orcbux/mo ( we've spent the vendor's 'test drive' bait). i'ma cover the lunch money cost of this item until given to know that it aint wanted.
asciilifeform: ( there is also a 'giant ice40' that amberglint dug up recently, that gotta be tested, but i dun even physically have 1 yet, and deliberately not bought so as not to distract from moar urgent matters )
asciilifeform: there is also a serpent-on-ice40 thing, with similar level of unfinishitude; and a ice40-powered 'FG2', ditto.
asciilifeform: to round out the 'loose ends' thread -- asciilifeform also has a ~90% built node-walker and www front end for same. but it is in refrigerator, no one is direly starving for the lack of the thing, i expect i'll come back and finish it off strictly after ffa is fielded .
asciilifeform: mircea_popescu: any idea what happened to esthlos ?
asciilifeform: and without pizarro, it will be very very cold and dark and we'll be drifting in the unforgiving vacuum of interstellar space.
asciilifeform: http://btcbase.org/log/2019-01-05#1884603 << BingoBoingo i'd ~really~ like to hear what is current plan for gettin' heathen custom, so as to finally get the hell out of the red. asciilifeform dun have a massive treasure chest that can run pizarro 'on battery' 4evah (hopefully not surprising, this)☝︎☟︎
asciilifeform: i admit that i'm at least a little curious how phf finally managed escape velocity from the bigzone, but if he doesn't feel like spilling re subj, also won't cry.☟︎
asciilifeform: hopefully he comes back soonish ( i'ma not even pester him re bolix, bolix is asciilifeform's personal war, learned not to expect help from anyone, and currently in refrigerator, i dun expect to spend much time on it while ffa undone )
asciilifeform: ( already hats off to ave1 , who did year+ of gnat cleanup that asciilifeform was solidly convinced he'd have to do with own hands; and the fixed inlining gave us a ~2x ffa speedup 'for phree' ! )
asciilifeform: also at some point it'd be great to have a mips gnat, so i can plant ffa on pocket-sized irons. but that's for muchlaters.
asciilifeform: http://btcbase.org/log/2019-01-05#1884619 << from ave1 , i hope to see a 'port' of tmsr-gnat that can be hard-welded into cuntoo as primary gcc ( to remove the hack where it builds gcc5, then down to 4.9, and neither of'em being a gnat )☝︎
asciilifeform: so long as they know which end of the rifle bullet goes out from.
asciilifeform: rright, but i dun necessarily mean to even discourage people from using directly.
asciilifeform: ( for the l0gz, refresher: pcode is meant to give a mechanically simple system where yer privkey is a pcode string, and so is yer pubkey, and so are ciphertexts, and whole mechanism is set in motion simply by feeding pcode to the processor )
asciilifeform: ffa is designed to be used via pcode (aka 'peh') but i'm not about to tell folx that they absolutely must. given the stated reqs (you gotta test for div0ism, we dun do it internally given as it's thermonuke performance) it can be safely used directly.
asciilifeform: ( i'ma stop here, folx who ate ch4 know all of this kindergartenisms )
asciilifeform: and likewise, you can put as many fz on stack as the stack height given in invocation of ffacalc, but not any moar.
asciilifeform: ( this being for the given bitness, which in pehbot is hard-welded to 256 )
