▁▁▁▁▁▁▁⏐▁▁▁▁▁▁▁▁▁▁▁▁ 904
mircea_popescu: BingoBoingo Mocky yeah lol
mircea_popescu: keks of all time, the imaginary "civil society" is gonna benefit from ustardation.
asciilifeform: possible bonus lol if boat stuck during steam back from syria to ukrazuela on acct of winblowz-nt crash
asciilifeform: meanwhile , measurements : 2.533s is cost of 1 shot of 4096bit m-r (on standard tester iron)
asciilifeform: 0.413s for 2048.
mircea_popescu: pretty hefty
asciilifeform: in range of what i estimated earlier, in http://btcbase.org/log/2019-01-11#1886357 ☝︎
a111: Logged on 2019-01-11 17:30 asciilifeform: btw per asciilifeform's chalkboard, the physical cost of constanttime m-r is ~equal to that of (2 modexps of the given width) x (number of witnesses) .
asciilifeform: must point out tho that you dun leak anyffin if you terminate the m-rism for X after first failed shot.
asciilifeform: ( for n00bz, m-r is montecarlistic for probable-primality but deterministic for compositeness, i.e. if outputs 'composite' then you have in fact a composite )
asciilifeform: naturally each new X is pumped from FG, rather than kochian increment or any such thing
asciilifeform: ( as discussed in detail in '17 thrd )
asciilifeform: this means that the gcd pre-litmus is an unambiguous win ( and you also dun leak anyffin if you terminate after X flunks the pre-litmus and you go an' get a new X)
asciilifeform: http://btcbase.org/log/2019-01-09#1885939 << orig thrd re above, for completeness. ☝︎
a111: Logged on 2019-01-09 00:19 asciilifeform: in other noose, constant-time stein-gcd aint so bad, 1msec (2048bit operands) , 6msec (4096bit) , 21msec (8192bit), 81msec (16384bit)
asciilifeform inclined to reject koch's optimization ( which diana_coman retained ) where witness consists of rng(bitness_of_n - 2) , and actually make witness equal to rng(width) mod (n - 2) for full range
asciilifeform: per the proof, it is seemingly harmless ( a carmichael number has 1/4 of the integers as 'liars' ) but what it does is to prevent simple manual test with small numbers , which is imho quite typically kochian
asciilifeform: one oughta be able to feed any valid, per the theorem, witness, up to n - 2 , and get the expected output.
asciilifeform: *up to 1/4
asciilifeform: ( see also http://btcbase.org/log/2019-01-14#1886898 ) ☝︎
a111: Logged on 2019-01-14 18:32 asciilifeform: http://btcbase.org/log/2019-01-13#1886533 << this is not only troo but is how one tests a m-r ( you feed it known liars & known troofers for a particular N and verify output )
asciilifeform: mircea_popescu et al : plox to lemme know if ~any~ part of this is unclear, cuz this is rather important moving part
asciilifeform: closest thing there is to a 'jesus bolt' in the thing, arguably.
asciilifeform: when we sit the thing down on a microcontroller with mask rom, or some other similar iron, it will be important to be able to spot-check the m-r and determine that for some input known only to you, it actually behaves as m-r.
asciilifeform: ( without having to use a microscope or whatnot )
asciilifeform: this type of test is impossible on systems where m-r eats witness straight from rng, without possibility to override by hand.
asciilifeform will bbl,meat
mircea_popescu: asciilifeform it is counterintuitively actually better to test with smaller integers than larger ones.
asciilifeform: mircea_popescu: in that can check result with pen ? or canya think of some other reason..?
asciilifeform: afaik density of 'liars' is uniform across numberline.
mircea_popescu: specifically because density is uniform, if you ~only~ check say 64 bit numbers as witnesses (ie, nothing smaller than 2^63) there's a set of composites < certain limit that'll pass ; whereas if you only check 1-63 bit numbers (so the same ~number~ of numbers) there's a set of composites that'll pass, but they're LARGER than the same limit.
mircea_popescu: much like in the case of usual gcd -- checking a random number for divisibility with 2 provides a much larger benefit (eliminates 50% of candiates) than checking a random number for divisibility with 15,485,863, which only eliminates 0.000% of candidates.
asciilifeform: mircea_popescu: it's that bach conjecture thing.
mircea_popescu: which is also why there exists such a thing as m-r witness sets, ie sets of witnesses guaranteed to not be false up to a certain value of candidates
mircea_popescu: asciilifeform right.
asciilifeform: in so far as anyone can tell, it's troo, and then 64bit witnesses suffice for 4096bit candidates. but not only relies on riemann, but dun win anyffin in ffa, where very small and very large number eat same cpu.
asciilifeform: ( would, if riemann were proven, conserve rng bits, tho , could use fewer of'em )
asciilifeform: incidentally, m-r liars seem to be closed under multiplication, but i have not proven.
mircea_popescu: that'd afaik be a useful result.
asciilifeform: ikr?
mircea_popescu: yes.
asciilifeform: potentially could have cryptoism based on such a thing, if it were in fact troo
mircea_popescu: yes, because not readily computable the reverse, "which number are these liars for"
asciilifeform: ( or even a proofofwork func )
asciilifeform: aha
feedbot: http://bingology.net/2019/01/24/terminal-pantsuit-discourse-no-there-is-no-we-in-si-se-puede/ << Bingology - BingoBoingo's Blog -- Terminal Pantsuit Discourse: No, There is No "We" In "Si se puede"
BingoBoingo: ^ This is getting follow up later
mircea_popescu: BingoBoingo "He/She/You can == Puede" << no you belongs there.
mircea_popescu: also it's not Hondoras, it's Honduras
mircea_popescu: nor is there such a thing as Venezuala. did you get your vowels knotted up there ?
BingoBoingo: Vowels indeed iffy today
feedbot: http://thewhet.net/2019/01/guts-ive-lost/ << The Whet -- Guts I've Lost