Most factorization algorithms in use today fit in one of two camps: sieve-based methods based on congruences of squares, and algorithms based on decompositions of algebraic groups. In this article, we trace the common thread connecting the latter.
Dirichlet’s Theorem on the infinitude of primes in arithmetic progressions relies on the non-vanishing of non-trivial Dirichlet characters at 1.
In this post, I’ll show how this reduction can be introduced in an intuitive way via sieve theory. If we actually sieve, we obtain estimates for the number of integers whose prime factors lie in given congruence classes.
Just how good are polynomials at producing primes? Do there exist polynomials that produce primes for arbitrarily many consecutive inputs?
In this post, I’ll give a brief overview of what we expect to be able to prove, and show how interpolating polynomials can produce record-breaking prime-generators. (And then break a record, because why not?)