less_less

It isn't balanced quinary, but rather redundant balanced quaternary (base 4). In balanced quinary (base 5), each digit has 5x the significance of the previous one, but in Booth's encoding algorithm it's 4x.

If digit i has significance b^i, then b (the base of the exponentiation) is the base (or radix) of the number system.

The page you linked explicitly mentions the binary version of Booth encoding as having base b=2 and three signed digits {-1, 0, 1}. The quaternary version similarly has b=4 and five signed digits {-2, -1, 0, 1, 2} ... and possibly sometimes -0 in practice, not sure.

It's still a modified base 4, because the significance of the i'th digit is 4^i, not 5^i.

Edited to add: I'm also not sure whether real-life implementations have -0 as an option. Of course -0 could be normalized to +0, but it might be cheaper not to bother if the sign is applied after the digit selection.

The model usually measures in terms of fixed-size operations, e.g. 2-input binary gates. There's some variation in how to count memory lookups, but even in models where accessing a large memory counts as only one step, any tables present in the code still have to be fixed-size (except in models like P/poly, but even then they can't be exponential size).

Yeah, that shift-and-add algorithm is sometimes used on microcontrollers, either in software if there's no hardware multiplier, or in hardware if you want the bare minimum in acceleration at a tiny cost in area.

Adds are not really considered negligible; the article is just sloppy. (Some shifts might be negligible in some models because a fixed shift requires no logic gates.) The cost of the adds in Karatsuba is significant both theoretically and in practice, and determines the cutoff where Karatsuba is useful. But the exponent in O(n^(log_2 3)) is dominated by the recursive multiplications; the adds only affect the leading constant hidden in the O().

Residue number systems are really neat! They're sometimes used in crypto implementations, but there you're doing modular multiplication and in most cases the modular reduction then becomes costly, so it's not a free lunch. (Except in RSA and a few other cases. RSA-CRT gets you a "free" ~4x performance boost except it's more brittle to mistakes and side-channel / fault attacks.)

There's also NTT / Fourier multiplication as an option, for big integers or polynomials or modular arithmetic.

Hardware multipliers often use a sort of base-4-ish lookup table trick as well, using the Booth-Wallace algorithm. Booth's idea is to rewrite one of the inputs in base (usually) "4", except that the digits go from -2 to +2 instead of 0 to 3. (That's five possible digits! This helps the rewriting stage not have to propagate carries. Carry propagation is very expensive.) You can use Booth in a base higher than 4, especially if you know one of the multiplicands before the other, but you run into tradeoffs pretty quickly.

Then for each digit, you select between the other input multiplied by 0 (all zeros), +1 (identity), +2 (shift left by one bit), or -1 or -2 (flip all the bits of +1 or +2, plus a correction). Since a number has about half as many digits in base 4 as in base 2, you have about half as many digits to sum as if you'd done this in base 2.

Then you sum up all those results, but since carry propagation is expensive, you mostly use "compressors", e.g. you sum up three intermediates at a time, but you do it bit-by-bit, where three 1-bit numbers add up to a 2-bit number (from 0 to 3). This is called a Wallace Tree. The point is that you are generating carries, but you aren't propagating them, just adding them back into the set of things to be summed.

At the end of the tree step, you have just two numbers left, and you add them conventionally. That's the only step that needs full carry propagation.

If you are implementing a multiply-add, or multiplying several numbers and adding up all the results or similar, then you usually only need one full carry propagation stage.

The overall circuit has quadratic area but only a logarithmic depth in gates. IIRC whether to do Booth or not is a tradeoff: at least in some circumstances the rewrite steps make it slower but smaller. Hardware tool vendors have done a lot of work to tune these circuits very tightly, using e.g. specialized gates like AOI, heuristics for how to set up the tree, etc.

Ah, thanks for the correction. Do I have the soundness bit right? I guess it might apply even if the proof system is only computationally sound, since the simulator has to be efficient, right?

Cryptographer here, but this is not my area and I've only skimmed the paper. As far as I can tell, it's a purely theoretical result but a really cool one. Wall of text that might be wrong, as a rough summary of the result as I understand it:

There are different definitions of "zk", of "proof". Eg do "proofs" of false statements not exist, or are they just hard to find? If they exist but are hard to find, then it's often called an "argument" instead, which is the "AR" in zk-SNARKs and zk-STARKs.

One common definition of zero-knowledge protocols is that you can make an efficient simulator that makes convincing transcripts of the protocol without knowing the relevant secret (up to and including whether the statement to be proved/argued is even true). For interactive proofs, the simulator is usually supposed to output a transcript of the messages sent between the prover and the verifier, and the trick to making the simulator work is to choose later messages before earlier ones (e.g. challenges before commitments). But in non-interactive proofs, there's only one message, so that trick doesn't work and the simulator would have to output the proof itself.

The Goldreich-Oren result shows that this definition of ZK conflicts with soundness, unless the type of problem you're doing ZK proofs for was easy to begin with. IIUC this is for a simple reason: if a simulator can efficiently output a convincing proof of any true statement of the type your zk proof system covers (this is the zero-knowledge property); and if for false statements there is no proof that will convince the verifier (soundness); then you have an efficient algorithm for checking whether the statement is true or not, which is just to check whether your simulator convinces the verifier. This means that the underlying problem is by definition easy, so there's not much point to having zk proofs for it.

Goldreich-Oren doesn't apply to zk-SNARKs or zk-STARKs, because they are not perfectly sound, and in particular because you can get around the impossibility using the trusted setup in zk-SNARKs (essentially a secret key that lets you efficiently prove false statements) and/or by messing around with the random oracle model (pretend that the hash functions are replaced by magic, and then let the simulator tinker with that magic). Also zk-S?ARKs are arguments of knowledge (not just e.g. "a discrete log of this point exists" but "the prover knows the discrete log") which also changes the model.

As I understand it, the new result is basically to make your proof a NIWI-proof ("Non-Interactive Witness Indistinguishable proof", a weaker notion of zk-proof) that:

* Either [real statement you're trying to prove]

* or else [false statement that's almost impossible to prove false], e.g. "there are contradictions in your axiom system".

Such a proof can be made perfectly sound, since NIWI can be perfectly sound, and the second half is supposed to be false. There's no simulator, but if the false statement were true then there would be a simulator, where you always feed the NIWI eg a contradiction in the axiom system, instead of a proof of the real statement. (The definition of NIWI is that it should be hard to distinguish the proof resulting from these two cases.) The new paper also argues that this result, where there's no simulator but it's hard to prove that there's no simulator, is almost as good as the simulator actually existing.

Probably in practice you wouldn't do this, but you would instead try to make sure that a zk-SNARK, zk-STARK, NIWI etc is good enough in your use case.

I've hung out with a lot of pharma folks, and the business is really complicated. Most of the companies aim to both help people and to make a lot of money, and will choose projects based on some balance of those -- sometimes in dubiously ethical ways (e.g. tweaking formulations of existing products to extend the patent) and sometimes in basically fine ways (e.g. lots of the improvements in diabetes management which have helped a ton of people; at least the targeting is fine here though often not the pricing). Obviously chronic diseases that affect lots of rich people are a prime target to make money, so drug companies make lots of drugs for these, and they usually aren't curative because chronic diseases are hard to cure (but see e.g. Hep C which is now curable). There are also companies with rich investors who want to cure death, or at least cure particular diseases that they fear or have a genetic predisposition to (lots of unethical behavior from a certain now-defunct company that tried to do this).

For cancer in particular, pharmas don't (and mostly can't) just target a drug to chronically treat some cancer over the long term but not cure it. Instead they pick some target that's believed to contribute to development (/ metastasis / treatment resistance / whatever) in whatever cancer, and make a drug to interfere with it or to target an immune response to cells that make it. If it's stable, nontoxic, and looks potentially effective enough they'll take it to clinical trials. During clinical trials they'll find out whether it does nothing, gives you a few extra months, or has a chance at curing the disease. Usually the answer is that it does nothing or almost nothing, or isn't worth the side effects, and then the company wasted its time and money. Drugs with a chance to cure common types of cancer can be enormous successes -- see eg Herceptin.

Cancers are difficult diseases and it's rare to find something that reliably cures them. But drug companies aren't pulling their punches. Like they would never say "oh this drug clears breast cancer too reliably, we should make it less effective so that people will be more likely to die but also might take it for longer".

I'm pretty the spec sheet claimed 1000 cycles when I bought my iPhone 17.

They do claim it at least for iPhone 15 "under ideal conditions": https://support.apple.com/en-us/101575

If I understand correctly, Baillie-PSW has been shown to be correct for all integers < 2^64, so for 64-bit ints you might use (some variant of) that instead of M-R.

Edited to add: Sieving has got to be much faster than M-R if you want all primes of a certain size. You would use M-R or Baillie-PSW if you are testing them one at a time.

I picked Hunter's Point because I used to live near it. The problems from decommissioning radioactive ships are bad, but they're far from the only pollution that was there. Lots of VOCs, solvents, oils, radiation from other stuff (eg, glow-in-the-dark equipment made with radium), heavy metals, pesticides, PCBs, and what have you.

But sure, there are other shipyards they cleaned up in less than three decades.

Yeah. It's especially relevant for the author's focus on shipbuilding. The old shipyard at Hunter's Point in San Francisco is horribly polluted, and they've been working to decontaminate it for more than three decades in order to reclaim the land for other uses (in particular, housing). Treasure Island and Yerba Buena Island also have a lot of pollution from the former naval base there. There is a cost to overregulation, and there is a cost to underregulation.

And OK, sure, there's a lot of industry that ought to happen somewhere. Someone has to build ships and electronics and whatever, and if California's code is too strict then it just becomes NIMBYism. But if some company moves their gigafactory to Reno for easier permitting, I don't whether (or more likely by how much) CA is too strict, or NV is too lax. And I know that CA has NIMBYish and overregulatory tendencies, but given the clear bullshit on this website, I'm not inclined to give it the benefit of the doubt either.

I'm especially doubtful when it says "THE classic example of what you can't do in CA" is auto paint shops ("Impossible"!) ... but then the detail it gives is that they're "effectively impossible" to permit in the Bay Area AQMD, that being only one of the state's 35 AQMDs (albeit one of the larger ones).

The laptop keyborad is good enough, but I'd enjoyed using the Kineses before. I moved long distance and the Kinesis was bulky and didn't make the cut for things to haul. Once I was settled I started looking to set up a proper office again, and that included a keyboard. But I didn't find one that was enough better than a laptop keyboard to get regular use.

In addition to what others have pointed out, many of these aren't actually missing from traditional dictionaries: they're just inflected differently. So your example lists phrases like "operating systems", "immune systems" and "solar systems" as missing from traditional dictionaries, but at least the online OED and M-W have "operating system", "immune system" and "solar system" in them. It's just that your script is apparently listing the plural as a separate phrase.

On languages other than English: in general, different languages do word division very differently. At least in German and Dutch, many of those phrasal verbs are separable, meaning that they are one word in the infinitive but are multiple words in the present tense. So for example, where in English you would say "I log in to the website", in Dutch it would be "Ik log in op de website". "Log in" is two words in both cases, but in Dutch it's the separated form of the single-word separable verb inloggen ("I must log in now" = "Ik moet nu inloggen"). The verb is indeed separable in that the two words often don't end up next to each other: "I log in quickly" = "Ik log snel in".

Dutch, like German, has lots of compounds. But there are also agglutinative languages, which have even more complex compound words, perhaps comprising a whole sentence in another language. Eg (from Wikipedia) Turkish "evlerinizdenmiş" = "(he/she/it) was (apparently/said to be) from your houses" or Plains Cree "paehtāwāēwesew" = "he is heard by higher powers"; and these aren't corner cases, that's how the language works.

Glove80 is super nice, though rather expensive.

I got one with low-force switches. It's very comfortable to type on, but between the low-force switches and slightly different layout from a regular keyboard (column-staggered, concave, symbols in different locations) I make more mistakes. So I usually type on my laptop instead, especially while coding.

This thread is pretty weird.

My phrase "how economists expect you to set it" is probably wrong here, since I'm not an economist, I've just read the most basic theory about how to use this tool, and also used it myself (on eBay, you know, years ago when the site was mostly auctions). So I don't really know what "economists expect", but rather the basic guidelines for using this tool. You got me there.

I think this is the problem. When most sciences observe reality diverge from the model, they see that as a flaw in the model. When economists (at least you HN "economists") observe reality diverge from the model, they seem to see that as a flaw in reality.

But like, to double-check here: "reality" means your imagined use of a tool that you do not in fact use, right? Like you say you "don't do auctions" and I'm trying to explain what that option is for, and you're countering that the basic "how to use this tool" explanation is a wrong model of reality?

I'm not defending "you shouldn't ever need to snipe, just bid your max price" as a hard principle, just trying to explain where the idea comes from. Sniping can be strategic for lots of reasons: you don't have to commit to a bid until the last second (in case you find a similar item for cheaper elsewhere), you deny other people information, you might avoid anxiety from wondering whether your bid will win, etc.

That said, the max price is supposed to be a price where you are not especially happy to get the item at that price, but not really sad either, a price where you would say "well, I hoped for better but I guess that's a fair deal". That's not realistically pinned down to the cent. But if you set a max price at $5000 and would be happy to get the item at $5000.02 (for some reason other than satisfaction from sniping), then you set your max price wrong, or at least differently from how economists expect you to set it.

It's not supposed to be some red line absolute max price, but rather "how much is this item worth to you?" You set that as your max bid price. If you get it at auction for less than that, you got a good deal, but if you buy it for more, you got a bad deal. If someone outbids you, then maybe it was worth it to them, but you (supposedly) would not have wanted to buy the item for that much, and would rather use your money for something else.

For tricky-to-price items like unique art pieces, the idea that you can pin this down might be a fantasy, but for commodity items it's pretty reasonable. If you can buy the same thing at costco dot com for $500, then it's probably not worth more than $500 to you, and if at auction you get outbid and it sells for $500.01 then you'll shrug and go order the same thing for a cent less, having wasted only a few minutes of your time. If the item you're bidding on is discontinued (e.g. it's last year's model) but you can buy a slightly better one for $550, and you can spare that extra $50, then again you won't be too sad about getting outbid. Online auctions are more popular for used items, but again in that case you usually still have an idea of what a used item is worth to you.

See also the paper Ribbon filter: practically smaller than Bloom and Xor: https://arxiv.org/abs/2103.02515, which is a similar idea though not by the same authors.

IIRC, binary fuse filters are faster to construct than ribbon filters, but typically not quite as space-efficient. There are also frayed ribbon filters (by me) which are slower and more complex to construct but more space-efficient. There's no paper for those, just a Rust implementation.

Ribbon filters are deployed in Mozilla's Clubcard for distributing compressed certificate revocation lists: https://github.com/mozilla/clubcard and https://jmschanck.info/papers/20250327-clubcard.pdf. CRLs are an almost ideal application of this sort of compressed set tech, since the aggregator runs batch jobs and needs to distribute the set to very many clients. It's not perfectly ideal because CRLs require frequent updates and none of these methods support delta updates. There is a straightforward but inelegant workaround, which is to send a compressed set that represents the delta, and query both on the client.

Another answer to this: https://en.wikipedia.org/wiki/Cayley–Bacharach_theorem

A second special case of this theorem is Pascal's theorem, which says (roughly) that a variant of the elliptic curve group law also works on the union of a conic C and a line L (this union, like an elliptic curve, is cubic), where the group elements are on the conic. One point O on the conic is marked as the identity. To add points A+B, you draw a line AB between them, intersect that with the fixed line L in a point C, draw a second line CO back through the marked identity point, and intersect again with the conic in D:=A+B. This procedure obviously commutes and satisfies the identity law, and according to Pascal's theorem it associates.

Under a projective transformation, if the conic and line don't intersect, you can send the line to infinity and the conic to the units in (IIRC) a quadratic extension of F (e.g. the complex unit circle, if -1 isn't square in F). Since the group structure is defined by intersections of lines and conics, projective transformations don't change it. So the group is isomorphic to the group of units in an extension of F. If they do intersect ... not sure, but I would guess it instead becomes the multiplicative group in F itself.

The multiplicative group of F can be used for cryptography (this is classic Diffie-Hellman), as can the group of units in an extension field (this is LUCDIF, or in the 6th-degree case it's called XTR). These methods are slightly simpler than elliptic curves, but there are subexponential "index calculus" attacks against them, just like the ones against the original Diffie-Hellman. The attack on extension fields got a lot stronger with Joux's 2013 improvements. Since no such attack is known against properly chosen elliptic curves, those are used instead.

Annoyingly, while that d = e^-1 usually isn't used in practice (except in cases where you care about side-channel / fault resistance more than the 4x speedup), the Carmichael totient itself still is used in practice. At least if you want to conform to FIPS 186-5 / SP800-56B, which says that the private key includes d = e^-1 mod the Carmichael totient LCM(p-1,q-1), even if you're going to use the CRT. And that means you have to compute LCM(p-1,q-1), which also has side-channel considerations.

Do the standards require strong primes for RSA? I think FIPS doesn't ... it gives you that option, either for the legacy reasons or to get a proof with Pocklington's theorem that (p,q) really are prime, but just choosing a random (p,q) and running enough rounds of Miller-Rabin on them is considered acceptable IIRC.

The intro textbook descriptions of cryptographic systems omit a lot of very important details.

When using RSA to sign a message m, in practice you don't send m^d mod N. That would generally be insecure, depending on what kinds of messages your system sends and/or accepts. In practical systems, instead you hash m, and then adjust the hash through a (possibly randomized) process called "padding" to be a value in [0,N). There are different standards for padding, and the better designs use additional hashing.

The security of the system depends in part on the hashed-then-padded message "looking random", i.e. not having structure that can be exploited by an attacker. It turns out to be tricky to formalize what exact randomness property you need, so cryptosystems are often analyzed in the "random oracle model" (ROM) in which the hash function has impossibly strong randomness properties.

It seems that usually, if you use a strong hash function, a scheme that's proved secure in the ROM is secure in real life (or at least it's not the ROM part that breaks); the counterexamples are usually really contrived. This article is about a somewhat-less-contrived, but still not quite realistic, example where something that's secure in the ROM would break due to the ROM being an unrealistic model.

Internally, most signature algorithms use hash functions. RSA-PSS, EdDSA and ML-DSA use them to provide something like randomness, and the security analysis of those signature schemes includes arguments assuming (in some very particular, technical ways) that the hash function outputs "look random".

Classical DSA and ECDSA do not use hash functions this way, but in my opinion they aren't stronger for it: they're basically assuming instead that some other mathematical function "looks random", which seems riskier than assuming that about a hash function. I've heard that the reason for this is to get around Schnorr's patent on doing it with hash functions, which has since expired.

The SHA3 and SHAKE hash functions (underlying e.g. ML-DSA) are explicitly designed to "look random" as well.

There are some signature schemes that try not to make such strong assumptions: in particular SLH-DSA targets properties more like first- and second-preimage resistance, target-collision-resistance, and so on.

As I understand the paper, the point is that Fiat-Shamir does *not* give a correct proof of the program's output.

They gave a (maliciously constructed) program whose outputs are pairs (a,b) where certainly a != b (instead the program is constructed such that a = b+1 always). But you can get the corresponding Fiat-Shamir protocol to accept the statement "I know a secret x such that Program(x) = (0,0)", which is clearly a false statement.

Oh yeah, factoring the polynomial is also a good idea. For a long enough list that ought to be better than AFFT too.

Adding to some other comments in the thread: finding missing or extra numbers is closely related to error-correcting codes, especially binary linear codes. In an error-correcting code, you have a string of bits or symbols, with symbol x_i appearing at position i. You choose the code so that valid sequences have a certain mathematical property, and then if one or a few symbols are corrupted, then you can use that property to correct the errors. The property is typically that a certain linear function called the "syndrome" is zero, meaning that sum(x_i * G_i) = 0 where each G_i is some strategically chosen vector, particular to the code. The math for how to correct is particular to the chosen G_i, and it's a really interesting field of study.

In a typical error-correcting code usage, you have an encoder which takes your message, and adds some extra symbols at the end which are calculated so that the syndrome is zero. Then when receiving your message, the receiver calculates the syndrome and if it's not zero, they know that at least one error has occurred. By using the code's decoding algorithm, they can figure out the fewest (and thus hopefully most likely) number of changes which would result in that error syndrome, and use this information to (hopefully) correct the transmission error.

For the missing numbers problem, you can set x_i to "how many times does the number i appear?". Then since the syndrome is sum(x_i * G_i), you can compute the syndrome on an unordered list of the i's. You are expecting the syndrome to be the same as the syndrome of full set 1...n, so when it is not, you can figure out which few x_i's are wrong that would lead to the syndrome you observed. You have an advantage because you know how many numbers are missing, but it's only a slight one.

The author's solution is called the Hamming code: you set F(i) = i, and you do the additions by xoring. Using error-correcting codes generalize to more missing numbers as well, including using xor, but the math becomes more complicated: you would want to use a fancier code such as a BCH or Goppa code. These also use xor, but in more complicated ways.

If you imagine a polynomial L(z) that's zero at all the missing numbers, you can expand the coefficients out. For example, with 2 missing numbers (x,y), you have:

   L(z) = z^2 - (x+y)z + xy.

Then you solve for the roots of L, either using your finite field's variant of the quadratic formula, or e.g. just by trying everything in the field.

* But wait, this doesn't actually work! *

Over fields of small characteristic, such as F_2^m, you need to modify the approach and use different powers. For example, in the equations above, I divided by 2. But over F_2^m in the example shown above, you cannot divide by 2, since 2=0. In fact, you cannot solve for (x,y) at all with only x+y and x^2 + y^2, because

  (x+y)^2   =   x^2 + y^2 + 2xy   =   x^2 + y^2 + 0xy (since 2=0)   =   x^2 + y^2

This will depend on the field, and for F_2^m you want odd powers: sum(x), sum(x^3), sum(x^5) etc. Using sum(x^2) won't help because squaring over F_2^m is a field homomorphism, meaning that sum(x^2) = sum(x)^2.

This is also how BCH error-correction codes work (see https://en.wikipedia.org/wiki/BCH_code): a valid BCH codeword has sum(x^i where bit x is set in the codeword) = 0 for t odd powers i=1,3,5, ... Then if some bits get flipped, you will get a "syndrome" s_i := sum(x^i where bit x was flipped) for those odd powers. Solving from the syndrome to get the indices of the flipped bits is the same problem as here.

The general decoding algorithm is a bit involved, as you can see in the Wikipedia article, but it's not horribly difficult:

  • First, extend the syndrome: it gives sum(x^i) for odd i, but you can compute the even powers s_2i = s_i^2.

  • The syndrome is a sequence of field values s_i, but we can imagine it as a "syndrome polynomial" S(z) := sum(s_i z^i).  This is only a conceptual step, not a computational one.

  • We will find a polynomial L(z) which is zero at all errors z=x and nowhere else.  This L is called a "locator" polynomial.  It turns out (can be checked with some algebra) that L(z) satisfies a "key equation" where certain terms of L(z) * S(z) are zero.  The key equation is (almost) linear: solve it with linear algebra (takes cubic time in the number of errors), or solve it faster with the Berlekamp-Massey algorithm (quadratic time instead, maybe subquadratic if you're fancy).

  • Find the roots of L(z).  There are tricks for this if its degree is low.  If the degree is high then you usually just iterate over the field.  This takes O(#errors * size of domain) time.  It can be sped up by a constant factor using Chien's search algorithm, or by a logarithmic factor using an FFT or AFFT.

Edit: bullets are hard.

Further edit just to note: the "^" in the above text refers to powers over the finite field, not the xor operator.