Ideal in a union of ideals

Suppose $I$ is an ideal in a ring $R$ and $J,K$ are ideals such that $I\subseteq J\cup K$. Then either $I\subseteq J$ or $I\subseteq K$. Indeed, suppose that there is some $x\in I$ such that $x\not\in J$. If $y\in I$ is arbitrary and $y\not\in K$ then $x + y$ is in neither $J$ nor $K$. Thus, $y\in K$ and so $I\subseteq K$.

In other words, if there is some element of $I$ that is not in $J$, then $I$ is contained entirely in $K$.

A generalisation for commutative rings is as follows: if $J_1,J_2,\dots,J_n\subseteq R$ are ideals such that at most two of them are not prime ideals, and $I$ is an ideal such that $I\subseteq \cup_i J_i$ then $I\subseteq J_k$ for some $k$. Of course, one does not need the hypothesis that at most two of the $J_1,\dots,J_n$ are not prime if $I$ is principal.

If one drops the hypothesis that at most two of the ideals $J_1,\dots,J_n$ are not prime, then the conclusion no longer holds in general, though.

For example, consider the ring $R = \Z/2[x,y]/(x^2,y^2)$. It is a ring with sixteen elements. In $R$, the ideal $(x,y)$ has eight elements. Furthermore,
$$(x,y)\subseteq (x)\cup (y)\cup (x+y).$$
However, each of the ideals $(x), (y),$ and $(x+y)$—none of which are prime—only has four elements, and so $(x,y)$ is not contained in any of them.

A Python 3 implementation of the MD5 Hash

Today we'll see a Python 3 implementation of the MD5 hashing algorithm, which was originally designed by Ron Rivest. Even though the MD5 algorithm has been compromised and is not longer secure, it is still in use today. For example, CS ISOs of Linux distributions often provide MD5 sums in addition to SHA256 sums.

There are a lot of C implementations of MD5 out there. However, they are not easy to read, especially for someone who is not used to C. Python 3, being closer to "math" rather than the computer, reads more like a definition of the algorithm. Of course, the Python implementation is slower than the C one.

This Python implementation is ideal for experimenting with MD5 and learning about it. The code I give below is not the most compact possible, but I believe it is easy to understand.
…read the rest of this post!

Sum of squares a square?

The sum of squares of two integers can be an integer. For example, $3^2 + 4^2 = 25^2$. Those are also the legs of a right-angle triangle. This example is special in that the numbers $3$ and $4$ are consecutive integers!

Can you find a sum of squares of three consecutive integers that make a square?

No, it's not possible. If $n$ is any integer, then the sum
$$n^2 + (n+1)^2 + (n+2)^2 = 3n^2 + 6n + 5.$$
Now, modulo three, any number squared is either 0 or 1. But this polynomial always outputs integers that are 2 mod 3. Therefore, the sum of three consecutive integers cannot be a perfect square.

Exercise: prove that the sum of squares of four consecutive integers cannot be a perfect square.

Maybe, you might be inclined to think that 2 is somehow special, and that a sum of squares of $k$ consecutive integers cannot be a perfect square if $k \gt 2$. But then you would be surprised at this sum of squares of fifty consecutive integers:
$$7^2 + 8^2 + 9^2 + \cdots + 55^2 + 56^2 = 60025 = 245^2.$$
Cool, right? This is by no means the smallest example. Here is another example of 407 consecutive integers:

$$183^2 + 184^2 + \cdots + 589^2 = 8140^2.$$

But are there infinitely many such examples?

OpenMP Tutorial: Part 2

This is a continuation of the OpenMP tutorial. Last time we wrote the following program:

It gives a proof that the number $N = 770948605618065977$ is prime by testing all the possible factors up to the integer part of the square root of $N$. To recap, this program creates two threads and tests half the possible factors on one thread, and half the possible factors on another thread. Wouldn't it be nice to have the program split the loop work up automatically instead of having to do it manually?
…read the rest of this post!

Simple OpenMP Tutorial

Today, I'll give you a simple and practical example of using OpenMP with gcc. What's OpenMP? It's a C/C++/Fortran library for writing multithreaded applications. What's that? Most computers these days have multiple cores so that multiple tasks can be done in parallel. With multiple cores, you can edit pictures and listen to music at the same time without a noticeable slowdown. The intensive editing computations and music decoding happen on separate cores. It's a little more complicated than that, but that's the basic idea.

If your computer has multiple cores, it can use them in a single program. That's where OpenMP comes in. For concreteness, let's say you want to test whether the number 770948605618065977 is prime. If you're sane you'd just use the Miller-Rabin test like we've been discussing on this blog, and be happy with a 99.99999% probability that the number is prime. However, let's say you want to prove this number prime by trying all the numbers up to the integer part of its square root, which is 878036790.

Here is a minimal C program to do this:
…read the rest of this post!

What is your current level of math education?

I'm hoping readers can take the time to answer this important poll. I am trying to determine the current educational background of my readers so I can better target future posts of this blog with a sufficient amount of detail.

What is your highest current level of mathematical education?

 Undergraduate math degree in progress or completed Masters math degree in progress or completed PhD math degree in progress or completed Some math courses outside of degree None, just interested in math

View Results

The perfect notebook

Over the years I have tried many systems to keep math notes: paper notebooks, offline WordPress installation, LaTeX files in folders, and random papers that get left on my desk for too long. None of these were ideal for all purposes. Here are the main drawbacks of each system:

1. Paper notebooks are actually good for learning things. For reading material like books or papers in detail, paper notebooks are the best system for keeping myself on-track of going through every detail, line by line. However, the linear fashion of notebooks makes them hard to consult for main ideas. Additionally, they take up significant space.
2. My offline WordPress installation consists of WordPress installed on Apache running on my laptop. I found it pretty terrible for notes. The blog format is good for presenting self-contained ideas over time but not so good for consulting old notes because it is not built for organising systematic knowledge. Note however, that I still use my offline WordPress installation to test-drive posts for this blog before they go live.
3. Using LaTeX is the obvious solution to writing mathematical notes. And for large works, like complete books or papers, it is the best. However, for a general mathematical notebook, a bunch of random LaTeX documents are not easy to organize or search.
4. Using random loose sheets of paper works for taking notes to help me learn. In this case, writing is just a tool for learning and not for storing information. After I just recycle them.

However, I've finally found system for taking notes that works. …read the rest of this post!

Does this product sequence converge?

Consider the following series:
\begin{align*}
a_1 &= \frac{4}{3}\\
a_2 &= \frac{4}{3}\frac{9}{8}\\
&\vdots\\
a_n &= \frac{4}{3}\frac{9}{8}\cdots\frac{(n+1)^2}{(n+1)^2-1}
\end{align*}
In other words, $a_n$ is the product of all the numbers of the form $n^2/(n^2 – 1)$ for $n=2,\dots, n+1$.

Does $\lim_{n\to\infty} a_n$ exist?…read the rest of this post!

The Lucas primality test

We've been talking about the Miller-Rabin randomized primality test, which is one of the easiest to implement and most effective tests that, given a number, will either prove it to be composite or state that it is most likely prime. As good as it is for practical applications, the Miller-Rabin test leaves something to be desired.

If you need primes for cryptographic applications, Miller-Rabin practically perfect. But what if you want to generate super large primes and state for sure that the numbers you are generating really are primes?

The Lucas test is a fast test that can prove a number prime. Here it is:

Theorem (Lucas Test). Let $a$ and $n\gt 1$ be integers. If $a^{n-1}\equiv 1\pmod{n}$ and $a^{(n-1)/q}\not\equiv 1\pmod{n}$ for every prime factor $q\mid n-1$ then $n$ is prime.

The proof is quite simple: the congruences that $a$ satisfy show that $a$ generate the multiplicative group $\mathbb{Z}/n^\times$. Therefore, $n-1\mid |\mathbb{Z}/n^\times| = \varphi(n)$. However, if $n$ were composite then $\varphi(n) \lt n-1$, which contradicts $n-1\mid\varphi(n)$. Therefore, $n$ is prime.
…read the rest of this post!

Effectiveness of the Miller-Rabin primality test

Last time, I explained the Miller-Rabin probabilistic primality test. Let's recall it:

Theorem. Let $p$ be an odd prime and write $p-1 = 2^kq$ where $q$ is an odd number. If $a$ is relatively prime to $p$ then at least one of the following statements is true:

1. $a^q\equiv 1\pmod{p}$, or
2. One of $a^q,a^{2q},a^{4q},\dots,a^{2^{k-1}q}$ is congruent to $-1$ modulo $p$.

The Miller-Rabin randomized test looks for values of $a$ that don't satisfy the conclusions of this theorem. Such an $a$ is called a witness. If such an $a$ can be found, then $n$ is composite. If no such $a$ is found after a bunch of iterations, then we consider $n$ to be probably prime.

For example, a hundred iterations of Miller-Rabin selected

as a number that is most likely prime. A brute-force factor testing to make sure that this number is prime would take many times the age of the universe. That's pretty crazy! The Miller-Rabin test only takes a couple seconds, but how good is it really?

Now what about the percentage of witnesses for different numbers? Is this percentage close to 75%? In fact, although at least 75% of all possible bases are witnesses for any given composite number, often there are far more bases. In fact, only 0.6% of composite integers below 2000 have fewer than 90% of the total possible bases as witnesses. One such number is 1891 = 31*61. About 76% of possible bases are Miller-Rabin witnesses for 1891, which shows that the estimate of 75% is pretty good.

But for cryptographic applications, we're not interested in finding composite numbers. Given a randomly selected odd composite number, we can say that the probability of the Miller-Rabin test failing to find it composite after $k$ iterations is at most $4^{-k}$, which we can make very small very quickly. However, this conditional probability isn't the same thing as the conditional probability that a randomly selected odd number is composite given that $k$-iterations of Miller-Rabin thinks it is a prime!

A priori, it may be possible that the probability a number is composite given that $k$-iterations of Miller-Rabin thinks it's a prime is higher than $4^{-k}$.

But this isn't the case. Beauchemin, Brassard, Crépeau, Goutier, and Pomerance showed in a paper that this probability (that a randomly selected odd number is composite given $k$-iterations of Miller-Rabin thinks it is a prime) is also at most $4^{-k}$, assuming that the randomly selected odd numbers of sufficiently large (which thankfully is less than the typical modern-day cryptographic application).