The Renewal Equation

Responses

1. Tim McL

   March 25, 2024 at 3:15 pm

   I don’t instantly know how Sage tests for primality, but it’s open source, so if you’re committed enough and can read the source code, it’s possible to find out. It certainly does not just look for primes in a list, since I think it can handle primes of a hundred digits, and since there are more hundred digit primes than there are atoms in the universe.

   I do know how Maple used to compute primes. First, it stored the product $m$ of the first few primes. (How many? As many as possible to make it possible to store $m$ as a single long int.) It computed $\gcd(m,s)$. If $\gcd(m,s)>1$, then $s$ is not a prime. Then, it stored the product $M$ of he next few primes. (How many? As I recall, enough so that $mM$ was the product of all primes less than 100.) It computed $\gcd(M,s)$. If $\gcd(M,s)>1$, then $s$ is not a prime.

   The only numbers left to consider are either prime or have no prime factors less than 100. To handle them, Maple has to be craftier. The rest of this note is aimed at people who know some math. Sorry.

   Now, there’s a theorem of Lagrange that says that if $p$ is a prime and $0<x<p$ is in the integers mod $p$, which I called $\Bbb Z_p$ and which real people call $\Bbb Z/p$, then $x^{p-1}=1$ in $\Bbb Z/p$. This isn't as hard to test as you think it's going to be, since you can do all the arithmetic in $\Bbb Z/p$. For instance, let $p=43$ and let $x=5$. When you write it in binary, $p-1=42=2+16+32$, so $5^{42}=5^2\cdot5^{16}\cdot5^{32}$. All these powers can be computed in $\Bbb Z/43$ by successive squaring:
   \begin{align*}
   5^2&=25\\
   5^4&=5^2\cdot5^2=25\cdot25=625=23\\
   5^8&=5^4\cdot5^4=23\cdot23=529=13\\
   5^{16}&=5^8\cdot5^8=13\cdot13=169=40\\
   5^{32}&=5^{16}\cdot5^{16}=40\cdot40=1600=9.
   \end{align*}
   (Remember that we're doing all this arithmetic in $\Bbb Z/43$.)

   Now, how do we get $5^{42}$? Well, $5^{42}=5^{32}\cdot5^8\cdot5^2=9\cdot13\cdot25
   =117\cdot25=31\cdot25=775=1$. So in this case, Lagrange's Theorem works.

   The contrapositive of Lagrange's Theorem is that if $x^{p-1}\ne1$ in $\Bbb Z/p$, then $p$ is not a prime. So one way to show that $39$ is not a prime is to do a calculation just like the one above to show that in $\Bbb Z/39,$ $2^{38}=4\ne1$.

   Warning: It's not the case that if $x^{p-1}\ne1$ in $\Bbb Z/p$, then $p$ is a prime. For instance, $341=11\cdot31$, but $2^{340}=1$ in $\Bbb Z/341$.

   This gives us a probabilistic way to test for primality. We pick a random $x$ and compute $x_p=x^{p-1}$ in $\Bbb Z/p$. If $x_p\ne1$, then $p$ isn't prime. If, on the other hand, $x_p=1$, then $p$ might or might not be prime. What do we do then? Pick another random $x$ and try it again. If we get 1 for a whole bunch of values of $x$ in a row, then we start to feel like it's more and more likely that $p$ is prime. If we get 1 enough times in a row, then we report that $p$ is prime, even though there's a small chance that it might not be.

   Weird, isn't it? What we have is a method that can either give us a proof that $p$ is prime (if for some $x$, $x_p\ne1$) or tell us that $p$ is very likely but not certain to be prime (if $x_p=1$ for a bunch of different values of $x$ in a row).

   That's how Maple at least used to test for primality.

   Finally, I've lied a little in this explanation. The trouble is that there are some rare numbers (well, rare, but there are infinitely many of them) for which $x_p=\text {$x^{p-1}$ in $\Bbb Z/p$}$ equals 1 for a whole bunch of values of $x$, and yet for which $p$ is composite. It's therefore hard to be certain how likely a number is to be prime if we got 1 a whole bunch of times in a row. There are improved versions of this method in which, for instance, a composite number is guaranteed to have $x_p\ne1$ for at least half the possible values of $x$. In that case, if $x_p=1$ for $n$ choices of $x$ in a row, then there is at most 1 chance in $2^n$ that $p$ is composite. Maple used one of these methods, which is really not much more complicated than what I just described, but that was complicated enough.

   Make sense?

   Reply
   1. Olly

      April 2, 2024 at 8:45 pm

      Thank you very much for this. It’s wonderful to be able to share math with you again. I’m going to have to come back to it, though. I am just not thriving mentally lately.

      Reply