{'fraction_non_alphanumeric': 0.03337783711615487, 'fraction_numerical': 0.009345794392523364, 'mean_word_length': 4.555555555555555, '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}}
Constructing nonresidues in finite fields and the extended Riemann hypothesis

We present a new deterministic algorithm for the problem of constructing kth power nonresidues in finite fields Fpn , where p is prime and k is a prime divisor of pn−1. We prove under the assumption of the Extended Riemann Hypothesis (ERH), that for fixed n and p → ∞, our algorithm runs in polynomial time. Unlike other deterministic algorithms for this problem, this polynomial-time bound holds even if k is exponentially large. More generally, assuming the ERH, in time (n log p)O(n) we can construct a set of elements that generates the multiplicative group Fpn . An extended abstract of this paper appeared in Proc. 23rd Ann. ACM Symp. on Theory of Computing, 1991.