pbsd

35 ms·

361.
by pbsd 12y ago
Nobody in their right mind uses AKS for primality testing. You use Miller-Rabin with an appropriate constant number of iterations, with complexity (log n)^(2 + o(1)). Or if you want provability, you use some fast variant of ECPP with (log n
362.
by pbsd 12y ago
Before people read too much into this, these results are purely asymptotic . It is hard to predict if they have any practical impact in the actual factorization of RSA keys (I'm not second-guessing the authors here; this is also clear
363.
by pbsd 12y ago
There is certainly room for improvement, but I don't see an 16x speedup happening on a 5-year horizon using the current AES-NI instruction set.
364.
by pbsd 12y ago
The theoretical maximum for current chips is less than 16 bytes per cycle. On Haswell you can process (in parallel) 7 blocks in roughly the time it would take to process 1. The latency of each round is 7 cycles, a full AES-128 10 rounds is
365.
by pbsd 12y ago
In the context of a crypto competition that sort of bounty is a way to try to get more attention to your design, therefore making your candidate more likely to be selected. Many designs are rejected due to lack of analysis at the time of th
366.
by pbsd 12y ago
Both fast examples create a dependence between loop iterations. The ADD+SBB case creates a dependence between the carry flag and the value loaded from memory; the INC + XOR creates a dependence on the value of RDX and the value loaded from
367.
by pbsd 12y ago
I don't think the number of uops in the loop being a multiple of 4 is the factor there. To see this, replace `ADD RAX, 1` with `INC RAX`, which does the exact same thing but does not alter the carry flag. The number of uops remains the
368.
by pbsd 12y ago
uop fusion is described in Agner's microarchitecture [1] and also on Intel's optimization manual [2, §2.3.2.6]. I don't know of any breakdown of uops for AMD's chips, but it's reasonable to assume that `add reg, mem
369.
by pbsd 12y ago
> For instance they claim an ADD mem, reg instruction would be translated into three 3 uops. This is definitely not the case, x86 chips can do a load+arith_op or a store+arith_op in the same uop. Sort of. An `add mem, reg` operation will
370.
by pbsd 12y ago
That is called the Liouville function; you might get luckier searching for that name. I don't know much about the state-of-the-art on computing it, but I found a description of such a method here, which may be a starting point to compa
371.
by pbsd 12y ago
Nitpick: Pollard's rho is unproven not because it relies on the birthday paradox, but because there's no way to prove that f(x) = x^2 + a behaves like a random walk. It may not because, e.g, the length of the cycle may be the same
372.
by pbsd 12y ago
I'm not sure what's your point. Your claim was that constant-time was not a big issue for many people. Maybe it's not. But the Groestl people wrote an entire report on implementation strategies for it [1], specifically mentio
373.
by pbsd 12y ago
All the deliverables are accessible here [1], and from the most relevant one (D5.4) the short story seems to be: - The core library's memory safety was verified using VCC; - A Frama-C plugin was used to verify (a limited form of) side-
374.
by pbsd 12y ago
I only arrived late here; the thread is already too large to do any proper pedantry. I like libsodium. It demonstrates that usable packaging is important, something that DJB seems to either ignore or not understand. But I only endorse libso
375.
by pbsd 12y ago
I don't think this is a fair assessment. There was a lot of concern over implementation issues during SHA-3 and every finalist did have constant-time implementations, usually coming from the design team itself. The thing with AES and i
376.
by pbsd 12y ago
As great as BCD instructions may be, they can't possibly compete with vector instructions for that kind of operation.
377.
by pbsd 12y ago
Previous related discussion: https://news.ycombinator.com/item?id=8270136
378.
by pbsd 12y ago
There is talk of defining a stable ABI within platforms [1]. I'm not particularly fond of the current proposal, but there seems to be interest. We'll have to see how it plays out. [1] http://www.open-std.org/jtc1&#
379.
by pbsd 12y ago
The C++ analogous, although not exactly the same, is to use a `make_vector` wrapper, like template<typename...Args> inline auto make_vector(Args&&...args) { using T = typename std::common_type<Args...>::type;
380.
by pbsd 12y ago
Nonsense. The standard writing tool in mathematics and computer science is LaTeX, which has plenty of bullshittery of its own. Most researchers will generally be suspicious of a Word-produced paper, since it usually will come from crackpots
381.
by pbsd 12y ago
Although not stated anywhere, the name could be an homage to Horst Feistel, one of the most influential cryptographers of the 20th century.
382.
by pbsd 12y ago
You are correct: overlapping those two incompatible algebras is the main source of nonlinearity in SHA-256.
383.
by pbsd 12y ago
I understand that. The author himself does not claim this approach is faster than bruteforce. Indeed, consider the converse: for mining using a SAT solver to be faster than bruteforce implies that the SAT solver is able to exploit some stru
384.
by pbsd 12y ago
While SAT, and their cousin SMT, solvers are useful in the analysis of symmetric cryptographic primitives, they quickly become useless once the complexity of the problem hits a certain threshold. They are best employed to analyze contained
385.
by pbsd 12y ago
That is a clarification [1] to the standard, to make it legal to avoid or fuse memory allocations if the compiler can prove it's OK. For example, int f() { int * x = new int(0); return *x; } does not really need to
386.
by pbsd 12y ago
One thing does not follow from the other. Core 2 has had paging bugs, ergo x86 has a barely working paging system => Pentium had the FDIV bug, ergo x86 can't be trusted with arithmetic. For the claim to be properly refuted, the clai
387.
by pbsd 12y ago
3-operand LEA has a different performance profile than 2-operand LEA on Sandy Bridge and later chips. The former has 3 cycle latency and only one execution port, whereas the latter has single-cycle latency and can be dispatched to two execu
388.
by pbsd 12y ago
If LEA is slow, don't use it. A simple ADD followed by DEC outperforms LEA in throughput, latency, and size in recent Intel chips. If you're willing to reduce integers to 62 bits (and assuming no overflows are allowed), multipli
389.
by pbsd 12y ago
According to Agner Fog, data domain penalties with SHUFPS are nonexistent, or at least pretty hard to trigger, on Haswell. Previous chips might complain, though. Problem with blends is that they require SSE4.1+, unlike the current version t
390.
by pbsd 12y ago
GCC's vectorized loop is using the usual "round-up" method, but we can easily implement the distributive method there by mixing 32 and 64-bit arithmetic: ; xmm7 = 0 magic 0 magic ; xmm6 = 0 ; xmm5 = 0 (accumulat

More ›