Proof that there are infinitely many quaternion primes

Sometimes proofs can be annoyingly difficult. I have been reading about quaternions in Elements of Number Theory and Exercise 8.4.2 asks you to prove that there are infinitely many quaternion primes without assuming that every natural number is the sum of four squares. I have been racking my brains over this one for a few days and finally I came up with a proof that I think works today.

What we know is that a quaternion "prime" is defined to have a norm which is prime in Z otherwise the norm will end up being the product of two quaternions of smaller norm. I was originally thinking that we should adopt the proof of showing that there are infinitely many primes in Z (see page 2 of the book) by assuming a finite number of quternion primes q₁,q₂,...,q_k and then forming a product of their norms and then adding 1. This new natural number is then not divisible by any of the norms norm (q₁), norm (q₂), ..., norm(q_k). But this hits snags straight away because you don't know if this new number is prime in Z and you don't know if it even relates to a quaternion.

After much thought, here is my proof.

Let us suppose to the contrary that there are only a finite number of quaternion primes q₁,q₂,...,q_k (where k is some natural number). Now the norm of each of these quaternion primes must be a prime in Z, so norm (q₁)=p₁, norm (q₂)=p₂, ... ,norm(q_k)=p_k where p₁,p₂,...,p_k are primes in Z.

Now there are an infinite number of primes in Z of the form 4n+1 (see page 113) and so we can always choose a prime p of this form which is not one of p₁,p₂,...,p_k. Further by the two-square theorem (see page 109) p=a²+b² for some a, b in Z. Now this is the norm of quaternion q where q=a1+bi+0j+0k since det (q)=a²+b² but q is not one of q₁,q₂,...,q_k since norm (q) is not any one of norm (q₁), norm (q₂), ..., norm (q_k). Further q must be a quaternion prime since norm (q) is prime in Z. Therefore we have reached a contradiction. It follows that there must be infinitely many quaternion primes.

RSA Factoring Challenge (part 7)

In my previous post I considered an example of trying to find the two primes in the product 9980651 by satisfying equations (1) to (4) in part 3. So just how many possible solutions would we come up with if we went about this in a systematic way? As we saw there were 3 possible solutions in solving equation (1), and 10 each for equations (2), (3) and (4). This means that we would have at most 3x10x10x10=3000 potential solutions to search through until we found the pair of primes (2029,4919) that we were looking for.

How does this compare with, say, trial division? We know that the product consists of two primes each of which contain four decimal digits. Therefore a simple approach would be to divide 9980651 by all the integers between 1000 and 9999, a total of 9000 numbers. An alternative approach would be to divide by all the primes between 1000 and 9999, a total of 1061 such numbers. This is fewer than the 3000 pairs of solutions we would come up with but then you would have to calculate what these primes were in advance.

If we consider the products of primes which are 100 digits or more, then we can see that the challenge is enormous. For example, for RSA-220 there would be 3x10¹⁰⁹ pairs of numbers to search through. Even if processing one pair corresponded to one instruction on a computer, then a computer operating at 10¹⁰ instructions per second could take 10⁹² years to find the right pair! So, unless this method can somehow be improved then it is not going to be a viable method for this challenge. In fact, it illustrates just how difficult it is to crack these products of large primes.