Friday, 22 April 2016

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 q1,q2,...,qk 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 (q1), norm (q2), ..., norm(qk). 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 q1,q2,...,qk (where k is some natural number). Now the norm of each of these quaternion primes must be a prime in Z, so norm (q1)=p1, norm (q2)=p2, ... ,norm(qk)=pk where p1,p2,...,pk 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 p1,p2,...,pk. Further by the two-square theorem (see page 109) p=a2+b2 for some a, b in Z. Now this is the norm of quaternion q where q=a1+bi+0j+0k since det (q)=a2+b2 but q is not one of q1,q2,...,qk since norm (q) is not any one of norm (q1), norm (q2), ..., norm (qk). 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.

Friday, 1 January 2016

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 3x10109 pairs of numbers to search through. Even if processing one pair corresponded to one instruction on a computer, then a computer operating at 1010 instructions per second could take 1092 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.

Tuesday, 22 December 2015

Reading the same book for 3 years

I have been reading Elements of Number Theory by John Stillwell for the last three years and I have only just started Chapter 8 (out of 12). It was a birthday present and so I would say it has been good value for money! Not that I have been reading it consistently. Sometimes I don't seem to have time to read much for several months and then I will pick it up again and have a burst of working and reading. The way I like to work through a text like this is to read and understand all the proofs and to work religiously through the exercises. Sometimes the proofs require a bit of extra work on paper to be able to understand them. Other times, by thinking about each sentence, I can understand a proof without the need to write anything down.

It may seem a bit bizarre to work through all of the exercises in the order in which they are presented but I find that if you complete one it gives you the confidence to tackle the next one. It also helps with the understanding of the text and, if there weren't exercises, all those proofs would seem a bit dry. So far I have done them all apart from those in section 3.8 until the end of chapter 3. I stopped working on this chapter when I gave up my OU studies as I felt I needed to start afresh on a new chapter. I have covered 56 pages of A4 with my workings! It would be nice to publish them all here but I don't think the publishers of the book, or the universities that use it, would be very happy about this.

I have finished chapter 7 on quadratic integers. This culminated in a proof of Fermat's last theorem for n=3 which I was pleased as punch to understand, especially when it says that this is "probably the most difficult result in this book...". It looks horrible when you just read through it quickly and nothing seems to make sense. You just have to take one sentence at a time and it may be that to understand a small point you have to go away and work at it until the penny drops. This was certainly the case for understanding the congruence classes mod √-3 in Z[ΞΆ3] in figure 7.3. I had to go back to basics to get to grip with this but it was key to some of the pre-stage proofs.

The next chapter in the book is about the four square theorem; that every natural number is the sum of four squares. For this we are introduced to Quaternions and Hurwitz integers. It all looks very intriguing.

Anyway, for all those of you who will be medling with some maths this Christmas instead of the usual crosswords or suduko, have a great time. Happy Christmas!

Friday, 3 July 2015

RSA Factoring Challenge (part 6)

I want to consider an example to show how we can attempt to find a solution to the eight simultaneous equations (1) to (8). I will start with an example where we know the two four digit primes p and q and then attempt to recover p and q from their product n using equations (1) to (8).

Let p be 2029 and q be 4919 then their product n is 9980651. If we didn't know what p and q were then following our analysis in part (1) then (X0,Y0) are either (1,1), (3,7) or (9,9). Let's suppose we try the middle pair first. Plugging (X0,Y0)=(3,7) back into equation (1) we find that C1=2. Equation (2) then becomes equivalent to

$$7X_{1}+3Y_{1} \equiv 3\;\mbox{(mod 10)}$$

From what we discussed in part 5 our possible solutions for (X1,Y1) are (3i,7(3-i)) modulo 10 (where i runs from 0 to 9) and these are the pairs (0,1), (3,4), (6,7), (9,0), (2,3), (5,6), (8,9), (1,2), (4,5) and (7,8).

Let's take the pair (X1,Y1)=(2,3). Substituting the values (X0,Y0)=(3,7), (X1,Y1)=(2,3) and C1=2 into equation (2) we find that C2=2. Equation (3) then becomes equivalent to

$$7X_{2}+3Y_{2} \equiv 8\;\mbox{(mod 10)}$$

and our possible solutions for (X2,Y2) are (3i,7(8-i)) modulo 10 and these are the pairs (0,6), (3,9), (6,2), (9,5), (2,8), (5,1), (8,4), (1,7), (4,0) and (7,3).

Let's take the pair (X2,Y2)=(2,8). Substituting the values (X0,Y0)=(3,7), (X1,Y1)=(2,3),  (X2,Y2)=(2,8) and C2=2 into equation (3) we find that C3=4. Equation (4) then becomes equivalent to

$$7X_{3}+3Y_{3} \equiv 4\;\mbox{(mod 10)}$$

and our possible solutions for (X3,Y3) are (3i,7(4-i)) modulo 10 and these are the pairs (0,8), (3,1), (6,4), (9,7), (2,0), (5,3), (8,6), (1,9), (4,2) and (7,5).

So what are these solutions for p and q? They are the following ten pairs of numbers; (223,8837), (3223,1837), (6223,4837), (9223,7837), (2223,837), (5223,3837), (8223,6837), (1223,9837), (4223,2837) and (7223,5837). Rather than showing that these numbers fail to satisfy equations (5) to (8) we can just multiply them together and compare them to n which is 9 980 651. We find that 223x8837=1 970 651, 3223x1837=5 920 651, 6223x4837=30 100 651, 9223x7837=72 280 651, 2223x837=1 860 651, 5223x3837=20 040 651, 8223x6837=56 220 651, 1223x9837=12 030 651, 4223x2837=11 980 651 and 7223x5837=42 160 651.

As expected none of them equal n. What it does demonstrate is that the method works, since each of the ten products ends in the number 0651, the same as the last four digits of n. This is to be expected as this was what was demanded by satisfying equations (1) to (4).

Friday, 29 May 2015

RSA Factoring Challenge (part 5)

I want to consider the solutions of equation (11) specifically for the values of a and b that we are likely to encounter. From the discussion in that blog entry we can see that in each of the equations (2) to (4) coefficient a takes the values of Y0 and coefficient b takes the values of X0. This means that in these cases a and b are elements of {1,3,7,9} and all the numbers in this set are coprime to 10.

Now suppose the RHS of equation (11) takes the value 5 then there are ten ways in which this number may be obtained on the LHS of the equation. We can have, modulo 10, 0+5, 1+4, 2+3, 3+2, 4+1, 5+0, 6+9, 7+8, 8+7 and 9+6. So if the RHS takes the value c then the 10 possibilities for the LHS are i+(c-i) where i runs through 0 to 9. Note that if c-i<0 then c-i is congruent to 10+c-i modulo 10.

So in essence our solutions for x and y boil down to two equations:-

$$ax \equiv i \;\mbox{(mod 10)}...(14)$$

and

$$by \equiv c-i \;\mbox{(mod 10)}...(15)$$

where i runs through 0 to 9. As a and b are coprime to 10, then a and b have an inverse a-1 and b-1 such that

$$aa^{-1} \equiv 1 \;\mbox{(mod 10)}...(16)$$

and

$$bb^{-1} \equiv 1 \;\mbox{(mod 10)}...(17)$$

Hence our solutions for x and y are

$$x \equiv a^{-1}i \;\mbox{(mod 10)}...(18)$$

and

$$y \equiv b^{-1}(c-i) \;\mbox{(mod 10)}...(19)$$

Previously, in equation (12) we considered the situation where a was 7, b was 3 and c was 4. Now the inverse of 7 modulo 10 is 3 (and vice versa since 3x7=21 which is congruent to 1 modulo 10) and so the 10 pairs of solutions are (3i,7(4-i)) modulo 10 where i runs from 0 to 9. This is congruent to (3i,8-7i) modulo 10. So we obtain the pairs (0,8), (3,1), (6,4), (9,7), (2,0), (5,3), (8,6), (1,9), (4,2) and (7,5) as before.



Thursday, 16 April 2015

RSA Factoring Challenge (part 4)

Looking back at my previous post, is it possible to solve these eight simultaneous equations given that a number n is the product of two prime numbers p and q each of four digits long? The first thing to notice is that equation (1) is equivalent to

$$X_{0}Y_{0} \equiv Z_{0} \;\mbox{(mod 10)}...(9)$$

which is as I discussed in part 1. So for a given Z0 there are either two or three solutions for the pair (X0,Y0) (I shall ignore the fact that we can swap the values for X0 and Y0, as this just reflects the commutative property of the product, that is n=pq=qp).

So, it seems that we could make progress as follows. We take one of the pairs of solutions (X0,Y0) and we plug it back into equation (1) to find C1, the multiple of 10 to be carried over into equation (2). That second equation then becomes equivalent to

$$X_{1}Y_{0}+X_{0}Y_{1} \equiv Z_{1}-C_{1}\;\mbox{(mod 10)}...(10)$$

and this equation is of the form

$$ax+by \equiv c\;\mbox{(mod 10)}...(11)$$

where a,b,c,x and y are elements of {0,1,2,...9} and a, b and c are known and x and y are not. Actually, as we saw in part 1 a and b in this case (being X0 and Y0) are not zero. This equation may or may not have solutions and I will consider this in future blogs. However, consider the case when (X0,Y0) is (3,7) (so Z0 is 1 and C1 is 2) and suppose Z1 is 6 then we have the equation

$$7x+3y \equiv 4\;\mbox{(mod 10)}...(12)$$

By considering all 100 possibilities for x and y we find that there are exactly 10 possible solutions for the pair (x,y) and these are (0,8), (1,9), (2,0), (3,1), (4,2), (5,3), (6,4), (7,5), (8,6) and (9,7). Note that any one solution (x,y) can be obtained from another solution by adding multiples of (1,1) modulo 10.

So it follows that for our one choice of (X0,Y0) we can end up with 10 possibilities for (X1,Y1). Now we can again choose one of these solutions for (X1,Y1), substitute it into equation (2) and using our original values for (X0,Y0) and C1 arrive at a value for C2.

We can use these values in equation (3) which can be written as

$$X_{2}Y_{0}+X_{0}Y_{2} \equiv Z_{2}-X_{1}Y_{1}-C_{2}\;\mbox{(mod 10)}...(13)$$

and this is again of the form of equation (11). Not only that but the coefficients of x and y (a and b) are the same as before since a is Y0 and b is X0. This means that if we have already calculated a table of the hundred possibilities of ax+by modulo 10 then we can just pick out the solutions.

It is no surprise that we can continue in a similar vein until we reach equation (4). By then we have a set of possible solutions for (X0,Y0), (X1,Y1), (X2,Y2) and (X3,Y3), that is for the four digits of both p and q. However, only one of those solutions will satisfy the four remaining equations (5) to (8).

Saturday, 4 April 2015

RSA Factoring Challenge (part 3)

Suppose you had two prime numbers p and q, both m digits long, and these were, respectively, Xm-1Xm-2...X1X0 and Ym-1Ym-2...Y1Y0 (where the subscripted X and Y's represent the decimal digits of p and q) then the product of p and q can be written as the product of

$$(X_{m-1} \times 10^{m-1} + X_{m-2} \times 10^{m-2} + ... + X_{1} \times 10 + X_{0}) \times (Y_{m-1} \times 10^{m-1} + Y_{m-2} \times 10^{m-2} + ... + Y_{1} \times 10 + Y_{0})$$

Ignoring the powers of 10 for the moment, the terms in the above can be written as a matrix of products of digits in p and q. For example for m=4, we get

$$\begin{pmatrix} X_{0}Y_{0} & X_{0}Y_{1} & X_{0}Y_{2} & X_{0}Y_{3} \\
                               X_{1}Y_{0} & X_{1}Y_{1} & X_{1}Y_{2} & X_{1}Y_{3} \\
                               X_{2}Y_{0} & X_{2}Y_{1} & X_{2}Y_{2} & X_{2}Y_{3} \\
                               X_{3}Y_{0} & X_{3}Y_{1} & X_{3}Y_{2} & X_{3}Y_{3}
\end{pmatrix}$$

Suppose that the result of the product was n then, as we have seen in my previous post, we can say that n is either 2m or 2m-1 digits long and we can write n as Z2m-1Z2m-2Z2m-3...Z1Z0 (where the subscripted Z's represent the decimal digits of n). This means that Z2m-1 may be zero. We can now relate the products of the digits in p and q to the digits in n by noticing that the terms along any diagonal line in the above matrix parallel to the one that passes through X3Y0 and X0Y3 have a multiple of 10 which is the same for each term. Since Zi (i running from 0 to 2m-1) involves the sum of these terms modulo 10 we can write a set of simultaneous equations, which for m=4 are:-

$$X_{0}Y_{0}-10C_{1}=Z_{0}...(1)$$
$$X_{1}Y_{0}+X_{0}Y_{1}+C_{1}-10C_{2}=Z_{1}...(2)$$
$$X_{2}Y_{0}+X_{1}Y_{1}+X_{0}Y_{2}+C_{2}-10C_{3}=Z_{2}...(3)$$
$$X_{3}Y_{0}+X_{2}Y_{1}+X_{1}Y_{2}+X_{0}Y_{3}+C_{3}-10C_{4}=Z_{3}...(4)$$
$$X_{3}Y_{1}+X_{2}Y_{2}+X_{1}Y_{3}+C_{4}-10C_{5}=Z_{4}...(5)$$
$$X_{3}Y_{2}+X_{2}Y_{3}+C_{5}-10C_{6}=Z_{5}...(6)$$
$$X_{3}Y_{3}+C_{6}-10C_{7}=Z_{6}...(7)$$
$$C_{7}=Z_{7}...(8)$$

Note that we have to include a carry term Ci for each equation so that we can accommodate the multiples of 10 accumulated in the previous equation. We also know that Z7 may be zero in which case so might be C7 (via equation 8).