pbsd

10 ms·

91.
by pbsd 5y ago
Intel greatly improved their divider implementation between Skylake and Icelake. The measurements in the OP are on Skylake-SP, prior to these improvements.
92.
by pbsd 5y ago
I agree; compiler-type code will miss the cache most of the time. A simple test with clang++ compiling some nontrivial piece of C++: 0 lsd_uops 1,092,318,746
93.
by pbsd 5y ago
The x86 decoder is not running all the time; the uops cache and the LSD exist precisely to avoid this. With instructions fed from the decoders you can only sustain 4 instructions per cycle, while to get to 5 or 6 your instructions need to b
94.
by pbsd 5y ago
True, but it's entirely voluntary: - clamp(a, b, c), where a, b, c are all l-values would copy everything. Not destructive by default (but wasteful on "big" types). - clamp(a, std::move(b), c) would potentially destroy b, but
95.
by pbsd 5y ago
Having everything be const references is in a sense optimal, but is so prone to misuse that I wouldn't want it in the standard library. One option is to pass everything by value. Move semantics does the rest. Like: template<ty
96.
by pbsd 5y ago
You can also achieve the fix using the arguably more natural template<typename T> T const& clamp(T const& v, T const& lo, T const& hi) { T const& a = v < lo ? lo : v; T const& b = a
97.
by pbsd 6y ago
This is probably the story in page 220 of [1], beginning at "Von Neumann got into trouble at the end of his life because he was really a frog but everyone expected him to fly like a bird.". [1] http://www.uvm.edu/p
98.
by pbsd 6y ago
Oh yeah, I thought the add r,r,2 was odd but didn't investigate. This brings things back to ~2+ cycles per iteration, which strictly speaking does not require fusion. It would be easier to test this explicitly instead of inside some un
99.
by pbsd 6y ago
Based on the information from [1] we have something like this for both loops: .LBB0_2: eor x13, x9, x9, lsr #30 # 2 \* p1-6 mul x13, x13, x11 # 1 \* p5-6 eor x13, x13, x13
100.
by pbsd 6y ago
Schnorr got close to making such a claim in a previous version of the paper [1, Section 6]. Namely, that NTRU is close to being broken if a sufficiently short vector (it is not specified how short) is found. The main claim of Schnorr's
101.
by pbsd 6y ago
GCM is a different type of construction, but the polynomial used there is explainable---it's the irreducible polynomial of the type x^128 + f(x) for which f(x) has the lowest degree (i.e., it's the lexicographically smallest irred
102.
by pbsd 6y ago
The set of operations you have access to as a designer affects immensely what your cipher will look like. If your alien CPUs had a very different instruction set than ours, their ciphers would look very different. Back in the old days memor
103.
by pbsd 6y ago
Presumably https://www.reddit.com/r/crypto/comments/3or80y/i_designed_m...
104.
by pbsd 6y ago
Not only is it a single uop for the last 10 years of Intel chips, you can also run 2 of them per cycle.
105.
by pbsd 6y ago
Yes. Between Pollard's rho, SQUFOF, ECM, the various sieves, etc, there is essentially no range at which this one performs better.
106.
by pbsd 6y ago
Subexponential algorithms in general have long had proven running times. Dixon's method [1], in particular, has had a proven running time since 1980. The number field sieve itself has had some recent progress on that front [2]. However
107.
by pbsd 6y ago
If you really want to know, you could cover most of it with [1,2]. [1] https://www.maa.org/sites/default/files/pdf/upload_library/2... [2] https://www.maa.org/sites/default&#x2F
108.
by pbsd 6y ago
I don't think that's the case on most CPUs; VPGATHERDD on Skylake, Icelake, etc, all issue the same 4/8/16 port2,3 uops regardless of what the addresses are.
109.
by pbsd 6y ago
Indeed; I've always known it as the Tenex bug [1], the Tenex being the system designed by BBN prior to being bought by DEC and renamed to TOPS-20. [1] http://www.bwlampson.site/33-Hints/Acrobat.pdf
110.
by pbsd 6y ago
What does the effect (or lack thereof) look like when doing xmm stores?
111.
by pbsd 7y ago
> Otherwise, if msg is short and it gets broken across a block boundary, this can make meet-in-the-middle--style attacks easier. Can you elaborate? Take SHA-512/256 with some awkward prefix size, let's say 127 bytes. Which atta
112.
by pbsd 7y ago
The single-uop FMA instructions beg to differ. As well as ADC, SBB, CMOVcc, etc, since Broadwell: 1 uop, 3 inputs. LEA itself has consisted of 1 uop for a very long time...but the complex 3-input version gets sent to a different place than
113.
by pbsd 7y ago
For each input source file, cl.exe creates at least 7 temporary files (with suffixes "gl", "sy", "ex", "in", "db", "md", "lk"). The churn of creating and deleting those,
114.
by pbsd 7y ago
https://www.usenix.org/legacy/events/sec03/tech/full_papers/...
115.
by pbsd 7y ago
I would point out that there _are_ consumer-grade chips with AVX-512 beyond the Xeons and Cannonlake: the Skylake-X chips such as i7-7800X, which even happen to have 2 512-bit FMA units, unlike some of the cheaper Xeons. I will point out th
116.
by pbsd 7y ago
A moved-from std::vector<int> will always be empty. However, a moved-from std::vector<int, custom_stateful_allocator> may not be. Howard Hinnant had a Stack Overflow reply a while back going through the possible corner cases of
117.
by pbsd 8y ago
Odlyzko, despite having some notable contributions to index calculus algorithms, was not among the first to invent or suggest its use.
118.
by pbsd 8y ago
Isn't the point of "Prime and Prejudice" that primality tests that are perfectly adequate for RSA key generation are inadequate to verify the primality of adversarial inputs, in protocols like negotiated DHE or whatnot?
119.
by pbsd 8y ago
The first step in the number field sieve is to represent the number to be factored as a polynomial (two, in fact), and it is assumed in the following steps that these polynomials do not split. If these polynomials did split with reasonable
120.
by pbsd 8y ago
You're essentially describing a residue number system, except the different moduli need to be coprime for things to be well-defined. FFT multiplication is basically a residue number system product on polynomials. Evaluating a polynomia

More ›