Forum logs for 07 Oct 2017

Monday, 16 March, Year 12 d.Tr. | Author:
mircea_popescu: so im trying out being 70s, what. do you want me to go in unaware, end up surprised by it ? [03:13]
diana_coman: http://btcbase.org/log/2017-10-07#1722059 <- yes, I got that as part of my previous log combing on this [03:45]
a111: Logged on 2017-10-07 00:26 asciilifeform: http://btcbase.org/log/2017-09-16#1715214 [03:45]
shinohai: http://archive.is/4Jc5B <<< Imagine the Furher parents must have felt ..... [10:14]
asciilifeform: '“the year is 1935 and you have been tasked with creating a mascot to represent the Nazi party at its political rallies.” “Think about all of the information you have learned about Hitler and the Nazi party,” the assignment directed. “You will create a COLORFUL illustration of the mascot. Give the mascot a NAME. You will also write an explanation as to why the mascot was chosen to represent the Nazi party.”' [10:37]
asciilifeform: lol! [10:37]
asciilifeform: '...I think a formal apology should be handed out, and the teacher involved should be reprimanded,” he added. ' [10:38]
BingoBoingo: !~ticker --market all [10:43]
jhvh1: BingoBoingo: Bitstamp BTCUSD last: 4350.03, vol: 5177.09336958 | Bitfinex BTCUSD last: 4359.5, vol: 16987.47514348 | BTCChina BTCUSD last: 4229.3316, vol: 0 | Kraken BTCUSD last: 4359.5, vol: 2319.21013539 | Volume-weighted last average: 4357.49756913 [10:44]
mircea_popescu: anyone came up with inflatable clitler ? [10:53]
BingoBoingo: You mean http://www.spencersonline.com/product/inflatable-hillary-bop-bag-12-inch/128370.uts?Extid=sf_fqntra [10:55]
BingoBoingo: brb [10:55]
asciilifeform: in other puzzlers, http://wotpaste.cascadianhacker.com/pastes/6l4uH/?raw=true << mod6 et al [11:17]
asciilifeform: ^ this 'upper half only' karatsuba works, but the answer is always off by 0 to 3, because the carries from the bottom halves are ( recursively ) lost. somehow gotta be finessed. [11:18]
asciilifeform: http://wotpaste.cascadianhacker.com/pastes/TgRkm/?raw=true << ordinary karatsuba, for convenient comparison. [11:19]
asciilifeform: ( Karatsuba_Term is same for both ) [11:19]
asciilifeform: now! this procrusted-karatsuba is only used for the barrettron, so theoretically could compensate for that 3 with 3 additional subtractor-muxes. and still win ~4x speedup vs last night's . but this is mega-ugly. [11:25]
asciilifeform: ( if it isn't obvious from where the error comes : observe the 3 Karatsuba_Term additions. in ordinary K., they walk over the upper half of XYLo ( lower half of result.) but in TopOnly K. we lose XYLo, so that carryolade is lost. ) [11:29]
asciilifeform: ... could even live with this, if i had a hard proof that it's never moar than 3. [11:32]
asciilifeform: heya hanbot [11:33]
asciilifeform: hanbot: wanna try yer hand at ^ puzzler ? [11:33]
deedbot: http://trilema.com/2017/friday-night-or-las-moiras-revisited/ << Trilema - Friday night, or Las Moiras revisited. [11:47]
mod6: <+asciilifeform> in other puzzlers, http://wotpaste.cascadianhacker.com/pastes/6l4uH/?raw=true << mod6 et al << /me looks [11:52]
mod6: btw, do you have a simple test harness setup for this just to assert some known output values? [11:53]
asciilifeform: mod6: i've been using (unreleased) 'p' as the tester. [11:54]
mod6: ah. gotcha. [11:54]
mod6: i think ima make a quick one for myself just so i can see what youre sayin on stuff like that. [11:54]
asciilifeform: mod6: you should have one already, the factorial thing [11:55]
asciilifeform: ( it will need a small adjustment in re http://btcbase.org/log/2017-10-02#1719728 but otherwise oughta work ) [11:55]
a111: Logged on 2017-10-02 19:31 asciilifeform: note also that the calling style from early versions will not work, there is no longer a .Z , FZ is not a struct any moar, it is just a word array [11:55]
mod6: aha, one similar to that. although, indeed, that works too. [11:55]
mod6: i'd like to also maybe make some unit tests around your procedures/functions. [11:56]
asciilifeform: i've been holding off on releasing the p-interpreter because there are several quite broad changed in the way that it worx, in the pipeline, and i'd rather folx not get used to the old form. [11:56]
asciilifeform: *changes [11:56]
mod6: im basically going to have to do this anyway -- this helps "fitting in mod6 [11:56]
mod6: 's head" [11:56]
asciilifeform: mod6: unit tests will work as pcode known-good in/out pairs [11:57]
asciilifeform: currently i generate them with a pyturd [11:57]
mod6: ah, ok. and yah, no need to let p out of the garage until ffa is pretty much "there". [11:57]
asciilifeform: it is tempting, because currently i suspect that ~nobody is actually running my pastes [11:58]
mod6: mainly, I read through them. because, there's still a lot for me to grok here. and it's easy to fool oneself into groking if you treat it like a blackbox instead of actually reading the code. [11:59]
mod6: (other than the ffa-fact, which i use sometimes to try new, whole, ffa parts out) [11:59]
asciilifeform: mod6: http://wotpaste.cascadianhacker.com/pastes/0k78K/?raw=true << example from asciilifeform's torture room, of what his test looks like [12:01]
* mod6 looks [12:01]
asciilifeform: ^ the 'two second' item, modexp [12:01]
mod6: niiice. [12:01]
mod6: yeah, something simple like this is a good starting spot. [12:02]
asciilifeform: mod6: http://wotpaste.cascadianhacker.com/pastes/H4UGn/?raw=true << for comparison, py script computing same arithm problem [12:02]
asciilifeform: you can run it, get same answer. [12:03]
asciilifeform: ( interestingly, it takes 3.8 sec on my box ) [12:03]
asciilifeform: this is even though python uses a c bignumatron internally. [12:03]
* mod6 looks [12:04]
asciilifeform: phun phakt, this calculation is taken from the gpg autopsies last summer, when asciilifeform was chasing imaginary rng boojum after somebody found a real one [12:04]
mod6: sweet. is pretty interesting tho. [12:04]
mod6: ahh, right. i recal. [12:05]
mod6: *recall [12:05]
asciilifeform: in ffa, unlike in the python example, elongating the 0x10001 to full ffawidth will not change the required time. [12:05]
asciilifeform: ( nor will anything else. ) [12:05]
mod6: :] [12:06]
mod6: super-cool [12:06]
asciilifeform: out of curiosity, how long the py item takes on mod6's box ? [12:07]
mircea_popescu: and in other curiosities, did http://trilema.com/2015/okcupidcom-the-dating-site/#comment-116639 ever come to anything as far anyone knows ? [12:07]
mod6: <+asciilifeform> out of curiosity, how long the py item takes on mod6's box ? << was just saving... lemme give it a try here. want me to try it on the i5/8gb box ? [12:11]
mod6: running... [12:13]
mod6: ok here 'tis: [12:14]
mod6: http://p.bvulpes.com/pastes/cDzHy/?raw=true [12:14]
mod6: grabbed 3 runs for good measure [12:14]
phf: (3s on python, 9s on cmucl, 1.2s on sbcl) [12:16]
shinohai: Python - 0m3.720s for me [12:17]
mod6: (fwiw, that machine I just ran it on has Python 2.7.9) [12:18]
mod6: im gonna try it on the build-donkey box, core2duo/4gb [12:19]
shinohai: (same) [12:19]
asciilifeform: phf: now try same width exponent ! [12:19]
mod6: and same version of py there too. ok just a sec. [12:19]
asciilifeform: betcha it won't be 1.2s nomoar [12:19]
asciilifeform: on heathentron [12:19]
* asciilifeform bbl : meat. [12:20]
mod6: ok here it is: [12:21]
mod6: http://p.bvulpes.com/pastes/D46Hw/?raw=true [12:22]
mircea_popescu: sbcl is actually the champ ?! [12:22]
shinohai: Anyone have the lisp version handy? [12:23]
phf: asciilifeform: wait, that seems like a cheap sleight of hand. obviously increasing number of iterations in an iterative algorithm that you gave is going to increase run time [12:26]
phf: shinohai: http://p.bvulpes.com/pastes/ZqN4y/?raw=true [12:28]
shinohai: ty phf [12:28]
mircea_popescu: phf his point is that if you're going to compare fixtime with something else, better make sure you get a long case in there too. [12:28]
phf: mircea_popescu: well he either has a constant time algorithm in ffa, in which case if the goal is to compare speed specifically we should be comparing fixtime ffa and fixtime something else. otherwise he has a variable time algorithm running at worst case constant time, in which case the comparison is between base operation speed, which is still going to come out on top [12:34]
phf: i guess the point of this exercise is to show that iteration sizes further leak timing information [12:35]
mircea_popescu: you're not having any of this new fangled "constant time ~= fixedtime ie, variable time running at worst case" ? [12:37]
phf: well, it's conveniently two strategies: closed form solutions and constant iterators. if you don't have a closed form solution, you have to iterate, which you simply do at the upper bound constraint by a data type size. i don't see how theoretically it can be anything else [12:41]
mircea_popescu: myeah [12:41]
shinohai: I get 0m1.236s using sbcl (i5) [12:42]
phf: i suspect that ffa's take on expmod is to iterate over every bigit of the exponent, which will have to perform base operations no matter what the numeric size is, but that's a guess. [12:46]
mircea_popescu: why guess, tis published. [12:47]
phf: i'm trying to figure it out from first principles :) (i haven't had time to look at the recent, i.e. past month, versions yet) [12:48]
mircea_popescu: a [12:48]
mircea_popescu: my guess is that it's as close to closed form solutions as possible, hence all the barrett fucking etc, but then again i'm a weak programmer and a very dubious mathematician. [12:49]
shinohai: http://archive.is/iDKq8 <<< Damned Gypsies! [14:49]
asciilifeform: http://btcbase.org/log/2017-10-07#1722372 << in fact we have closed form. [15:26]
a111: Logged on 2017-10-07 16:49 mircea_popescu: my guess is that it's as close to closed form solutions as possible, hence all the barrett fucking etc, but then again i'm a weak programmer and a very dubious mathematician. [15:26]
asciilifeform: http://btcbase.org/log/2017-10-07#1722358 << point was exactly to compare like items. i.e. heathendom does NOT get to 'win' by 'oh hey the hamming weight of exponent is only 2, not 4096, so we only do 4 modexps and not 8192' [15:28]
a111: Logged on 2017-10-07 16:26 phf: asciilifeform: wait, that seems like a cheap sleight of hand. obviously increasing number of iterations in an iterative algorithm that you gave is going to increase run time [15:28]
asciilifeform: the interesting imho discovery is that heathen bignumtrons don't win much (or even any!) speed by normalizing the ints being added/subtracted [15:30]
asciilifeform: i also suspect that they are in fact slower for maxhammingweight case of exponentiation and modulus, vs ffa. [15:30]
asciilifeform: slow and broadcasting seekritz for miles around, whatsnottilike!!111 [15:31]
asciilifeform: 'старый и злой -- чем не жених!' (tm)(r) [15:32]
asciilifeform: and incidentally my base cases are ultra-slow, in theory [15:39]
asciilifeform: 0 asm [15:39]
asciilifeform: so a word mul is actually five MULs [15:39]
asciilifeform: because gotta get upper word somehow [15:39]
asciilifeform: http://btcbase.org/log/2017-10-07#1722376 << modmuls, not exps [16:22]
a111: Logged on 2017-10-07 19:28 asciilifeform: http://btcbase.org/log/2017-10-07#1722358 << point was exactly to compare like items. i.e. heathendom does NOT get to 'win' by 'oh hey the hamming weight of exponent is only 2, not 4096, so we only do 4 modexps and not 8192' [16:22]
shinohai: !!up apeloyee [16:57]
deedbot: apeloyee voiced for 30 minutes. [16:57]
apeloyee: thanks shinohai [16:57]
shinohai: np! [16:57]
apeloyee: !~later tell trinque I put the key at http://p.bvulpes.com/pastes/oRT3V/?raw=true [16:58]
jhvh1: apeloyee: The operation succeeded. [16:58]
apeloyee: asciilifeform: turns out a simple, ffa-suitable O(N^2) algorithm exists for GCD. This is adapted from GMP docs with one extra operation in the loop: http://p.bvulpes.com/pastes/oupUJ/?raw=true . Note: the code as posted is likely wrong, but I'm sure the idea can be made to work. [17:09]
apeloyee: http://btcbase.org/log/2017-10-07#1722289 << and the point of doing karatsuba is? you do 2 recursive calls to Mul_Karatsuba_TopOnly and one to Mul_Karatsuba. should've simply calculated upper_part(XLo*YHi), upper_part(YLo*XHi) and XHi*YHi [17:14]
a111: Logged on 2017-10-07 15:17 asciilifeform: in other puzzlers, http://wotpaste.cascadianhacker.com/pastes/6l4uH/?raw=true << mod6 et al [17:14]
apeloyee: the multiply-by-approximate quotient in barrett's also needs only the lower part (plus 2 extra bits to the left), and lower part of product can be computed exactly (since rounding is not a problem) [17:25]
shinohai: !!up apeloyee [17:27]
deedbot: apeloyee voiced for 30 minutes. [17:27]
apeloyee: http://btcbase.org/log/2017-10-05#1721485 << i thought bernstein's "how to find smooth parts of integers" suggests a remainder tree, not gcd? [17:28]
a111: Logged on 2017-10-05 19:38 asciilifeform: want to gcd(candidate, biggestprimorialthatfitsintheffabitness) [17:28]
apeloyee: http://btcbase.org/log/2017-10-05#1721485 << alternatively, can *construct* numbers which don't have very small factors. pick a nonzero remainder mod 2, mod 3, ... mod largest-prime-fit-in-your-primorial and find what number of primorial is congruent to it using chinese remainder theorem [17:48]
a111: Logged on 2017-10-05 19:38 asciilifeform: want to gcd(candidate, biggestprimorialthatfitsintheffabitness) [17:48]
apeloyee: *what number has such remainder from division by 2,3, ... [17:49]
apeloyee: the primorial has to be, say, 2^32 times less than the ffa maxint. then you can add randomnumber*primorial, and such a number is equally likely to any prime from some interval [17:53]
ben_vulpes: danielpbarron: wouldja mind sharing that stage3 you build your eulora gentoos with? [18:12]
ben_vulpes: meanwhile, found a 20160728.tar.bz2 [18:21]
phf: http://btcbase.org/log/2017-10-07#1722379 << this is probably true but only because ffa mutates an array of bigits, where's any language level bignum system produces a whole new one for each operation [18:39]
a111: Logged on 2017-10-07 19:30 asciilifeform: i also suspect that they are in fact slower for maxhammingweight case of exponentiation and modulus, vs ffa. [18:39]
phf: a whole new bignum that is [18:39]
phf: http://btcbase.org/log/2017-10-07#1722374 << >> http://btcbase.org/log/2017-10-07#1722376 << this seems contradictory, because the python thing posted is not closed form [18:44]
a111: Logged on 2017-10-07 19:26 asciilifeform: http://btcbase.org/log/2017-10-07#1722372 << in fact we have closed form. [18:44]
a111: Logged on 2017-10-07 19:28 asciilifeform: http://btcbase.org/log/2017-10-07#1722358 << point was exactly to compare like items. i.e. heathendom does NOT get to 'win' by 'oh hey the hamming weight of exponent is only 2, not 4096, so we only do 4 modexps and not 8192' [18:44]
BingoBoingo: Trilema re-read of the day http://trilema.com/2014/how-i-was-wrong-cuckolding-or-a-story-about-sigmas/ [19:20]
mircea_popescu: http://btcbase.org/log/2017-10-07#1722405 << this may actually be a better check than any miller-rabin, and at any rate a good complement. gcd with primorial. [19:50]
a111: Logged on 2017-10-07 21:53 apeloyee: the primorial has to be, say, 2^32 times less than the ffa maxint. then you can add randomnumber*primorial, and such a number is equally likely to any prime from some interval [19:50]
* asciilifeform finally eaten log... [20:12]
asciilifeform: http://btcbase.org/log/2017-10-07#1722394 << this looks very , very painful to prove correctness of. i'ma come back to it. [20:13]
a111: Logged on 2017-10-07 21:09 apeloyee: asciilifeform: turns out a simple, ffa-suitable O(N^2) algorithm exists for GCD. This is adapted from GMP docs with one extra operation in the loop: http://p.bvulpes.com/pastes/oupUJ/?raw=true . Note: the code as posted is likely wrong, but I'm sure the idea can be made to work. [20:13]
asciilifeform: http://btcbase.org/log/2017-10-07#1722395 << compute and then what ? gotta multiply [20:14]
a111: Logged on 2017-10-07 21:14 apeloyee: http://btcbase.org/log/2017-10-07#1722289 << and the point of doing karatsuba is? you do 2 recursive calls to Mul_Karatsuba_TopOnly and one to Mul_Karatsuba. should've simply calculated upper_part(XLo*YHi), upper_part(YLo*XHi) and XHi*YHi [20:14]
asciilifeform: http://btcbase.org/log/2017-10-07#1722397 << i don't see anything that only wants ~lower~ half... whatcha talking about [20:14]
a111: Logged on 2017-10-07 21:25 apeloyee: the multiply-by-approximate quotient in barrett's also needs only the lower part (plus 2 extra bits to the left), and lower part of product can be computed exactly (since rounding is not a problem) [20:14]
asciilifeform: http://btcbase.org/log/2017-10-07#1722400 << bernstein's gcd method is neither here nor there, i certainly don't need anything of the kind in ffa, and quite likely it fundamentally does not ffaize [20:15]
a111: Logged on 2017-10-07 21:28 apeloyee: http://btcbase.org/log/2017-10-05#1721485 << i thought bernstein's "how to find smooth parts of integers" suggests a remainder tree, not gcd? [20:15]
asciilifeform: http://btcbase.org/log/2017-10-07#1722402 << this is a fundamentally wrong way to generate cryptographic primes. we had a thread about it, http://btcbase.org/log/2017-08-14#1697562 [20:16]
a111: Logged on 2017-10-07 21:48 apeloyee: http://btcbase.org/log/2017-10-05#1721485 << alternatively, can *construct* numbers which don't have very small factors. pick a nonzero remainder mod 2, mod 3, ... mod largest-prime-fit-in-your-primorial and find what number of primorial is congruent to it using chinese remainder theorem [20:16]
a111: Logged on 2017-08-14 16:14 asciilifeform: ( tldr : superiority of the FUCKGOATS-enabled approach, of get-new-N-bits-from-rng-then-primalitytest-until-done, vs the kochian get-N-bits-then-increment-until-passes-millerrabin ) [20:16]
asciilifeform: the ONLY correct method of generating cryptoprimes, is to 1) get N bits from FUCKGOATS 2) determine, in fixed spacetime every single time, whether that string of bits constitutes a usable prime. [20:16]
asciilifeform: all other methods leak info via timing , amperage, rf noise. [20:17]
asciilifeform: http://btcbase.org/log/2017-10-07#1722405 << in no case can the 'cheap initial primality test' primorial exceed the size of current ffa width. thinkaboutit. [20:18]
a111: Logged on 2017-10-07 21:53 apeloyee: the primorial has to be, say, 2^32 times less than the ffa maxint. then you can add randomnumber*primorial, and such a number is equally likely to any prime from some interval [20:18]
asciilifeform: http://btcbase.org/log/2017-10-07#1722408 << you might consider reading the code ? it has all been posted. [20:18]
a111: Logged on 2017-10-07 22:39 phf: http://btcbase.org/log/2017-10-07#1722379 << this is probably true but only because ffa mutates an array of bigits, where's any language level bignum system produces a whole new one for each operation [20:18]
asciilifeform: http://btcbase.org/log/2017-10-07#1722411 << 1 ) ffa is closed form. i.e. it CAN be written as a number of nand gates, with a 'funnel' at the top, to which you present a,b,c, e.g. 4096bit, numbers, and at the bottom in a little cup you get a^b mod c , and with NO UPWARDS FEEDBACK FLOW of information , i.e. answer comes after same interval of time always, and with strictly downwards signals. [20:20]
a111: Logged on 2017-10-07 22:44 phf: http://btcbase.org/log/2017-10-07#1722374 << >> http://btcbase.org/log/2017-10-07#1722376 << this seems contradictory, because the python thing posted is not closed form [20:20]
asciilifeform: but 2 ) the python example is of course not closed form, and it is imho meaningless to even attempt to write the closed form item in a language like python or cl [20:20]
asciilifeform: ( where there is no assurance of not consing and not branching ) [20:21]
asciilifeform: http://btcbase.org/log/2017-10-07#1722415 << if you have a comp the size of jupiter, you could ~maybe~ have such a thing as a 128bit primorial. [20:24]
a111: Logged on 2017-10-07 23:50 mircea_popescu: http://btcbase.org/log/2017-10-07#1722405 << this may actually be a better check than any miller-rabin, and at any rate a good complement. gcd with primorial. [20:24]
asciilifeform: but certainly not 129. [20:24]
asciilifeform: so no, nobody is replacing miller-rabin with gcd(primorial, x). [20:24]
asciilifeform: ( certainly not even for as large a number as 64bit... much less 4096 ) [20:24]
asciilifeform: i proposed primorial strictly as an initial winnowing to replace the idiot trial divisions koch et al used. [20:25]
asciilifeform: phf, mod6 : funnily enough i went and tried the 'fair fight' max(4096b) a^b mod c in python, http://wotpaste.cascadianhacker.com/pastes/GHATB/?raw=true , but it... bombs [20:31]
asciilifeform: with eggog: [20:31]
asciilifeform: OverflowError: Python int too large to convert to C long [20:31]
asciilifeform: for the obvious reason. [20:32]
asciilifeform: if somebody wants to make the physically possible version of this, to see what happens on max hammingweight... [20:32]
asciilifeform: oh ffs, here goes, [20:44]
asciilifeform: http://wotpaste.cascadianhacker.com/pastes/0A6fb/?raw=true << python 'fair fight' ver [20:44]
asciilifeform: ( and skips unused hammings... ) [20:44]
asciilifeform: 0.018s on this box. [20:44]
asciilifeform: http://wotpaste.cascadianhacker.com/pastes/saynG/?raw=true << all1s. 0.028s. tho i do suspect it shortcuts internally. [20:45]
asciilifeform: ( mainly, i suspect, by recognizing masses of 0 in karatsuba and returning 0 when they get mul'd ) [20:47]
asciilifeform: tldr : initial py snippet i had lying around was braindamaged. [20:48]
asciilifeform: http://btcbase.org/log/2017-10-07#1722367 << i gotta ask if this figure included sbcl load time !? [20:49]
a111: Logged on 2017-10-07 16:42 shinohai: I get 0m1.236s using sbcl (i5) [20:49]
asciilifeform: because if it did, it is meaningless [20:49]
asciilifeform: ( see phf's http://btcbase.org/log/2017-07-03#1678660 , or even naggum's, re why ) [20:50]
a111: Logged on 2017-07-03 14:46 phf: i think ascii already made that point, that if you're profiling lisp with the vm startup, then you should also profile c machine from boot time. at the very least the vm should be warmed up by loading all the dependencies into the core, doing save-lisp on it, and then making sure that your foo.lisp has an up to date fasl. inside lisp though to achieve the optimizations you run variants of your function inside (time ...) until you bring it within the ra [20:50]
asciilifeform: ( orig., iirc, thread : http://btcbase.org/log/2017-07-02#1678490 ) [20:53]
a111: Logged on 2017-07-02 12:50 asciilifeform: http://btcbase.org/log/2017-07-02#1678460 << how about we roll the boot time ( to shell!! ) of your cmachinekernel, how about? [20:53]
* asciilifeform bbl [20:58]
mats: l0l an amzn frontend engineer friend has to work all through christmas week, got his vacation request denied by upper mgmt [21:21]
mats: he put it in almost four months in advance and still can’t take a few days off [21:23]
BingoBoingo: Well, he works in the retail industry. What should he expect? [21:28]
mircea_popescu: http://btcbase.org/log/2017-10-08#1722429 << your chances of generating a random int that is also prime at that sort of length aren't so great. [21:34]
a111: Logged on 2017-10-08 00:16 asciilifeform: the ONLY correct method of generating cryptoprimes, is to 1) get N bits from FUCKGOATS 2) determine, in fixed spacetime every single time, whether that string of bits constitutes a usable prime. [21:34]
mircea_popescu: having a primorial at the ready to exclude a large number of common (ie, low) factors in one single gcd likely speeds this up significantly. [21:35]
mircea_popescu: http://btcbase.org/log/2017-10-08#1722442 << not altogether, hold on to your horses. [21:37]
a111: Logged on 2017-10-08 00:24 asciilifeform: so no, nobody is replacing miller-rabin with gcd(primorial, x). [21:37]
mircea_popescu: recall diana_coman 's trick of "multiply by 6" ? pretty much the inverse of the same idea. [21:38]
asciilifeform: http://btcbase.org/log/2017-10-08#1722468 << quite acceptable, 1 in few thou [21:46]
a111: Logged on 2017-10-08 01:34 mircea_popescu: http://btcbase.org/log/2017-10-08#1722429 << your chances of generating a random int that is also prime at that sort of length aren't so great. [21:46]
asciilifeform: ( try it ) [21:46]
mircea_popescu: yes, but then would you rather 999 r-m or 995 primorial gcd and 4 r-m ? [21:46]
asciilifeform: http://btcbase.org/log/2017-10-08#1722470 << is why i suggested it to begin with, zaps items with factors up to 16bit or so quickly [21:47]
a111: Logged on 2017-10-08 01:35 mircea_popescu: having a primorial at the ready to exclude a large number of common (ie, low) factors in one single gcd likely speeds this up significantly. [21:47]
mircea_popescu: so then what exactly is the argument about. [21:47]
asciilifeform: http://btcbase.org/log/2017-10-07#1722415 looked like a 'who needs miller-rabin' [21:48]
a111: Logged on 2017-10-07 23:50 mircea_popescu: http://btcbase.org/log/2017-10-07#1722405 << this may actually be a better check than any miller-rabin, and at any rate a good complement. gcd with primorial. [21:48]
mircea_popescu: yeah well. [21:48]
asciilifeform: ( where first suggested , ftr : http://btcbase.org/log/2017-08-14#1697598 ) [21:49]
a111: Logged on 2017-08-14 17:15 asciilifeform: idea is, for pre-millerrabin litmus, take gcd(candidate, Qw) where Qw is largest primorial that fits in the ffawidth [21:49]
asciilifeform: worxgreat [21:49]
mircea_popescu: incidentally, if looking for 4096 bit prime wouldn't the correct approach be to take 4094 bits of rng and glue 1 on either end ? [21:51]
mircea_popescu: as no 0 led or 0 terminated string will ever pass anyway [21:51]
asciilifeform: primes >2 are odd, noose at 11 [21:52]
mircea_popescu: aha. get some free bits that way, fwiw. [21:53]
asciilifeform: ( yes you set the low bit to 1 ) [21:53]
asciilifeform: http://www.loper-os.org/?p=568&cpage=4#comment-18272 << in other strange. [21:58]
shinohai: Lol asciilifeform got a brony [22:00]
shinohai: Oh wait, name is "Tina" [22:00]
asciilifeform: i have deeply nfi [22:00]
asciilifeform: in other lullies, http://www.loper-os.org/pub/nsawagenhoneypot.jpg << found on washington metro train today [22:02]
shinohai: TOP KEK "Anonymous access through tor browser"!!!! [22:04]
shinohai: They even bothered to vanitygen a custom tor addy [22:04]
asciilifeform: ads on these trains, ftr, not cheap. ( and certainly not 'to allcomers' ) [22:05]
Category: Logs
Comments feed : RSS 2.0. Leave your own comment below, or send a trackback.
Add your cents! »
    If this is your first comment, it will wait to be approved. This usually takes a few hours. Subsequent comments are not delayed.