log☇︎
152600+ entries in 0.614s
asciilifeform: and gcd wins vs however-many trial divisions with barrett.
asciilifeform: in practice on pc speed appears to be inversely proportional to memory used, rather than the cpu cycle count.
apeloyee: the fact that divisions are dog slow, for seconds << what barrett's reduction is for.
apeloyee: the fact that i don't need the batch aspect for anything, for starters << so don't.
asciilifeform: the fact that divisions are dog slow, for seconds
asciilifeform: the fact that i don't need the batch aspect for anything, for starters
apeloyee: bernstein's batch trial division would seem to straightforwardly ffaize. where's the problem?
asciilifeform: but this would weigh more than all of ffa to date !
apeloyee: because the acceptably fast algorithms are simpler.
asciilifeform: but hypothetically it may even be possible to ffaize bernstein's tree. or even to do it in such a way that doesn't wipe out the cpu winning from it. and even possibly to prove that it works and doesn't leak bits and doesn't let composites through once in a while.
asciilifeform: why the hell should i keep random crud in a table to pick up later.
asciilifeform: if gcd(r, p) == 1 -- then worth m-r, otherwise not )
asciilifeform: ( in our concrete case, r, a random , and p, a primorial -- for the pre-mr litmus test )
apeloyee: what two numbers?
asciilifeform: i used bernstein's tree in phuctor, where it made actual sense
asciilifeform: apeloyee: what does remainder tree win when you are testing only 2 numbers ?
asciilifeform: remember that ffa is not strictly for rsa.
asciilifeform: ( and potentially for other primality tests, though i can think of some cryptosystems where it is handy )
asciilifeform: gcd is for the pre-mr sieve, is all.
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?
apeloyee: http://btcbase.org/log/2017-10-07#1722400 << hey, I offered you an idea for GCD. you: "it stinks". I point you to bernstein ( https://facthacks.cr.yp.to/batchtrial.html ). you: "it stinks". maybe GCD is not a sane option ofter all, eh? ☝︎
asciilifeform: can be on any combination of whatever known tests.
asciilifeform: when i say 'week' it does not mean on a particular test.
apeloyee: anyway, I was saying that, if spending a week, may spend a small fraction of the time on the supposed-deterministic test
asciilifeform: situation where rsa is breakable, but no one can yet break it, makes it the sane option . because alternative is to become a donkey fucker ( rely on face to face for all comms , hope that nobody invents listening bug, etc )
asciilifeform: problem is that the historical period where crypto was a contest of bullet vs armour, rather than 'absolute bullet exists'/'absolute armour exists' is not over.
mircea_popescu: then 2 seems the null hypothesis ?
asciilifeform: because it is the null hypothesis.
apeloyee: why should then "ras key for 50n years" should be taken seriously then?
asciilifeform: and all of what they're selling -- stinks.
asciilifeform: in that it may be an actual problem , but NONE of the folx who ever publicly discussed it, have any business being taken seriously.
apeloyee: hey, before quadratic sieve was invented, they used to say that breaking 512-bit rsa will take eleventy zillion years and it's therefore Totally Secure (tm)
mircea_popescu: i know no proof of r-m convergence in terms of factorization.
asciilifeform: mircea_popescu: if it were physically possible as the sole primality test, we'd all use.
asciilifeform: rather than, e.g., 'rsa broken OR aes broken OR prng broke OR riemann is false OR ...'
mircea_popescu: well, so defined it must gcd as primality test.
asciilifeform: but in light of this, a correct rsatron is still one that stands on nothing BUT the assumption that rsa is hard.
asciilifeform: it remains possible that -- somehow -- they do not
asciilifeform: ^ to rephrase, we don't actually know if hard problems exist as a hard law of nature.
mircea_popescu: asciilifeform convergence on it is much narrower than mn tries or w/e a week provides.
mircea_popescu: apeloyee the p/np thing is kinda the label used here for all these, zfc, gnfs, etc.
asciilifeform: mircea_popescu: this is demonstrably true re r-m test tho.
mircea_popescu: if your expectation is that the fifth attempt did not resolve the problem in a manner such as the fifth million would, there's deeper problems.
apeloyee: asciilifeform: yes, that too.
asciilifeform: mircea_popescu: if ~probabilistic~, not 'same' test
asciilifeform: apeloyee: why not also say 'pray that p != np '
mircea_popescu: asciilifeform but the test that takes longer and costs more does not consist of manic re-measuring of the same one length, repeated millions of times.
asciilifeform: whereas some keys are more valuable than any submarine
apeloyee: pray that GNFS will never be improved upon!!
asciilifeform: when submarine is built, meant to last maybe 20yrs, test takes much longer than week
asciilifeform: apeloyee: i don't actually see how 'test for a week' is crackpottery when speaking about a key that is intended to stand up for 50 years ( or longer )
mircea_popescu: "not a root of 1st degree polynomial with smaller parameters than it"
mircea_popescu: but function, not hash table
asciilifeform: unbiased -- in this case -- would mean that it eats ANY bitstring from rng, R, and maps it to UNIQUE prime , P
asciilifeform: but there does not.
asciilifeform: and dispense with tests.
asciilifeform: and incidentally if there existed an UNBIASED constructor of primes, i'd use that
mircea_popescu: asciilifeform yes but this is just the artistic side in you.
asciilifeform: ( i.e. i regard the proof behind strength of the probabilistic ver, as fundamentally stronger than the other's )
mircea_popescu: as per the ancient "doctor, random things in the house are talking to me, am i losing it ?" "have you started answering ?" "not yet" "then not yet"
asciilifeform: i'll take the p(failure) to the week's power, over the possibility of hypothesis falling and ALL keys fucked.
mircea_popescu: well, the running maybe not, but ~believing~ that it achieved something, surely.
apeloyee: doesn't run in geological (e.g. saxena) time << if you have faith in generalized riemann hypothesis and correctness of work on deterministic miller test - you have it. I don't, but running test for a week is imo greater crackpottery than believing in that.
asciilifeform: ( very often abuse of terminology, what people actually mean by 'deterministic version' is 'probabilistic with prng supplying the random' )
asciilifeform: i'm not aware of a fully deterministic test that doesn't run in geological (e.g. saxena) time
jurov: hi mircea_popescu, s.qntr is still traded? i have got some frozen mpex orders
mircea_popescu: and in other bucharest tax office, https://i2.wp.com/www.cronicipebune.ro/wp-content/uploads/IMG_1539.jpg
apeloyee: at that cost, may also do the deterministic miller test then.
asciilifeform: which he'd rather have -- key that he genned inside 50cent chip, staying there, or primality-torture on his fleet of pentiums etc
asciilifeform: this requirement is somewhat in tension with classical airgapism 'this key was born in this tin can, and must die in it' however
mircea_popescu: asciilifeform should prolly be user knob tbh.
asciilifeform: and moreover for long-term key genning, imho a week or longer probabilistic primality test is not inappropriate.
mircea_popescu: well that's what i'm saying.
apeloyee: I think so.
mircea_popescu: apeloyee wasn't it exactly r-m restricted to first 10 primes or such ?
apeloyee: maple did a deterministic test
asciilifeform: i can't think of why to do any such thing
mircea_popescu: this is specifically "all prime bases up to 300".
asciilifeform: i suspect that for any probabilistic test, you can construct a boojum (e.g. you know that he will do 300 rounds, you make one that needs 301 )
mircea_popescu: famously, maple misidentified the guy's number. not because of rng, eiher.
asciilifeform: mircea_popescu: chance of these without sabotaged rng is < chance of meteorite
mircea_popescu: but we don't have to start low. and we don't really want to, either.
mircea_popescu: asciilifeform https://www.researchgate.net/publication/220161766_Constructing_Carmichael_Numbers_which_are_Strong_Pseudoprimes_to_Several_Bases (guy named arnault gave example of number for which all tests up to ~300 were misleading) ☟︎☟︎
apeloyee: each round of miller-rabin is mostly a modexp which makes some tests on the intermediate results. so I don't see how you can avoid a different version of modexp
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'
mircea_popescu: incidentally, since we're on m-r : do we actually pick 4096 bit bases to avoid the arnault number problem ? to leverage the ffa flatness, as in http://btcbase.org/log/2017-10-07#1722376 ? ☝︎
asciilifeform: mircea_popescu: review the mr algo , it is actually surprisingly easy to ffaize, just replace all 'return true' with flag := flag OR true, etc
asciilifeform: then all ACCEPTED primes took exactly same number of cpu clocks, to produce.
asciilifeform: apeloyee: each individual test has to be fixedtime though. then -- yes.
asciilifeform: it doesn't mean that we are forced to BRANCH on it.
asciilifeform: mircea_popescu: all that means is that one of the inputs comes from rng.
mircea_popescu: it naturally makes assumptions about the item you're testing.
apeloyee: if you have N ffa-eligible tests, bailing early out after one of them failed is not a problem.as per above.
asciilifeform: all steps that were previously conditional, happen muxed.
asciilifeform: yes there is.
mircea_popescu: the true problem here is that there's not going to be a fixtime r-m
asciilifeform: there is to be no compromise on leak.
asciilifeform: understand, this thing is 800 lines right now and i consider it too big.
apeloyee: well, I thought it's not a problem, each round of m-r can be implemented by slightly different version of extant modexp
asciilifeform: if you leak in one place, the rest of the places are worthless