The real type of a finite family of univariate polynomials characterizes the combined sign behavior of the polynomials over the real line. We derive explicit formulas for numbers of real types subject to various degree bounds. For the special case of a single polynomial we present a closed-form expression involving Fibonacci numbers. This allows us to precisely describe the asymptotic growth of the number of real types as the degree increases, in terms of the golden ratio.

Categories of partitions are combinatorial structures arising from the representation theory of certain compact quantum groups and are linked to classical diagram algebras such as the Temperley-Lieb algebra. In this paper, we present efficient algorithms and data structures for partitions of sets and their corresponding category operations, including a concrete implementation in the computer algebra system OSCAR. Moreover, we show that there exists a category of partitions for which the natural computational problems of deciding membership of a given partition as well as counting partitions of a given size are algorithmically undecidable.

Modern CPUs use a variety of undocumented microarchitectural hash functions to efficiently distribute data within microarchitectural structures such as caches. A well-known function is the cache slice function that distributes cache lines to the slices of the last-level cache. Knowing these functions considerally improves microarchitectural attacks, such as Prime+Probe or Rowhammer. However, while several such linear functions have been reverse-engineered, there is no generic or automated approach for reverse-engineering non-linear functions, which are common with modern CPUs.In this paper, we introduce a novel generic approach for automatically reverse-engineering a wide range of microarchitectural hash functions. Our approach combines techniques initially used for logic-gate minimization and from computer algebra to infer the hash functions based on input-output pairs observed via side channels. With our framework, we infer 3 previously unknown non-linear hash functions on both AMD and Intel CPUs, including the new Alder Lake hybrid-CPU architecture. We verify our approach by reproducing known hash functions and evaluating side-channel attacks that rely on these functions, resulting in success rates above 97.65 %. We stress the need to design such functions with both performance and security in mind and discuss alternative designs that can be used in future CPUs.