{'fraction_non_alphanumeric': 0.06181455633100698, 'fraction_numerical': 0.0009970089730807576, 'mean_word_length': 4.397849462365591, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Sparse multiplication for skew polynomials

Consider the skew polynomial ring L[x; σ], where L is a field and σ is an automorphism of L of order r. We present two randomized algorithms for the multiplication of sparse skew polynomials in L[x;σ]. The first algorithm is Las Vegas; it relies on evaluation and interpolation on a normal basis, at successive powers of a normal element. For inputs A, B ∈ L[x; σ] of degrees at most d, its expected runtime is O~(max(d,r)rRω-2) operations in K, where K = Lσ is the fixed field of σ in L and R ≤ r is the size of the Minkowski sum supp(A) + supp(B) taken modulo r; here, the supports supp(A), supp(B) are the exponents of non-zero terms in A and B. The second algorithm is Monte Carlo; it is "super-sparse", in the sense that its expected runtime is O~(log(d)Srω), where S is the size of supp(A) + supp(B). Using a suitable form of Kronecker substitution, we extend this second algorithm to handle multivariate polynomials, for certain families of extensions.