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!
Tuesday, 22 December 2015
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).
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.
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).
$$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).
$$(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).
Thursday, 26 March 2015
RSA Factoring Challenge (part 2)
In my previous blog I asked the question "If you knew that a number was the product of two primes of the same
length (in decimal digits) could you use the knowledge of the product to
determine what the factors were?" In what follows I will assume that for a number n we want to find the m-digit primes p and q such that n=pq.
So a question that you could ask is how many digits does n have if p and q have m digits? Primes p or q can't exceed 10m-1 as 10m is an m+1 digit number and
$$(10^{m}-1)^{2}=10^{2m}-2 \times 10^{m}+1$$
For m>1 this is the number 999...800...1 which is 2m digits long. The m+1 digit from the right is an 8 and all the digits to the left of the 8 are 9's (there are m-1 of them) and all the digits to the right are 0's except the last which is a 1.
Primes p and q cannot be less than 10m-1 as one less than this is an m-1 digit number and
$$(10^{m-1})^{2}=10^{2m-2}$$
which is a 2m-1 digit number. It follows then that if p and q have m digits, then n will have between 2m-1 and 2m digits. It also follows that if n has k digits, then p and q will have k/2 digits if k is even and (k+1)/2 digits if k is odd.
So, if RSA-220 was the product of two prime factors containing the same number of decimal digits, then we would be looking for primes that are 110 digits long.
So a question that you could ask is how many digits does n have if p and q have m digits? Primes p or q can't exceed 10m-1 as 10m is an m+1 digit number and
$$(10^{m}-1)^{2}=10^{2m}-2 \times 10^{m}+1$$
For m>1 this is the number 999...800...1 which is 2m digits long. The m+1 digit from the right is an 8 and all the digits to the left of the 8 are 9's (there are m-1 of them) and all the digits to the right are 0's except the last which is a 1.
Primes p and q cannot be less than 10m-1 as one less than this is an m-1 digit number and
$$(10^{m-1})^{2}=10^{2m-2}$$
which is a 2m-1 digit number. It follows then that if p and q have m digits, then n will have between 2m-1 and 2m digits. It also follows that if n has k digits, then p and q will have k/2 digits if k is even and (k+1)/2 digits if k is odd.
So, if RSA-220 was the product of two prime factors containing the same number of decimal digits, then we would be looking for primes that are 110 digits long.
Wednesday, 25 March 2015
RSA Factoring Challenge (part 1)
In a diversion away from my continuing study of number theory, I have been thinking about the difficulty of factoring large integers. My attention was caught by the RSA Factoring Challenge which was set up by the RSA Laboratories to "learn about the actual difficulty of factoring large numbers of the type used in RSA keys." I have described RSA encryption in my other concurrent blog and the keys are used in the modulus of the encryption and decryption. The RSA challenge was terminated in 2007 and the monetary prizes that were offered were withdrawn, however, not all of the numbers were factored. So what were these numbers?
Wikipedia has a list of the RSA numbers and reports on the success of people factoring them. These numbers are semiprimes, that is they are a product of two primes (not necessarily distinct). One thing that I noticed as I was looking down the list of factorisations was that in most cases the two primes had the same number of decimal digits and this got me thinking about this specific problem. If you knew that a number was the product of two primes of the same length (in decimal digits) could you use the knowledge of the product to determine what the factors were?
My first thought was that you could probably have a guess at what the last digit of each prime was. If the last digit of the product n=pq was Z and the last digits of the two primes p and q were X and Y, then
$$XY \equiv Z \;\mbox{(mod 10)}$$
This is true because the products of all the other digits involve multiples of 10 and these products are congruent to zero modulo 10 and therefore can't contribute to the remainder here. This result is also true regardless of the number of digits in p and q. Now because prime numbers larger than 5 can only end in 1, 3, 7 or 9, then if Z was 1 then (X,Y) are either (1,1), (3,7) or (9,9) (or vice versa for X and Y). The other pairings for (X,Y) are (1,3) and (7,9) for Z=3, (1,7) and (3,9) for Z=7 and (1,9), (3,3) and (7,7) for Z=9 (or vice versa).
So, for example, for RSA-220 which is the 220 decimal digit number
we can say that the last digits of the two primes that divide it could be (1,1), (3,7) or (9,9).
Wikipedia has a list of the RSA numbers and reports on the success of people factoring them. These numbers are semiprimes, that is they are a product of two primes (not necessarily distinct). One thing that I noticed as I was looking down the list of factorisations was that in most cases the two primes had the same number of decimal digits and this got me thinking about this specific problem. If you knew that a number was the product of two primes of the same length (in decimal digits) could you use the knowledge of the product to determine what the factors were?
My first thought was that you could probably have a guess at what the last digit of each prime was. If the last digit of the product n=pq was Z and the last digits of the two primes p and q were X and Y, then
$$XY \equiv Z \;\mbox{(mod 10)}$$
This is true because the products of all the other digits involve multiples of 10 and these products are congruent to zero modulo 10 and therefore can't contribute to the remainder here. This result is also true regardless of the number of digits in p and q. Now because prime numbers larger than 5 can only end in 1, 3, 7 or 9, then if Z was 1 then (X,Y) are either (1,1), (3,7) or (9,9) (or vice versa for X and Y). The other pairings for (X,Y) are (1,3) and (7,9) for Z=3, (1,7) and (3,9) for Z=7 and (1,9), (3,3) and (7,7) for Z=9 (or vice versa).
So, for example, for RSA-220 which is the 220 decimal digit number
2260138526203405784941654048610197513508038915719776718321197768109445641817 9666766085931213065825772506315628866769704480700018111497118630021124879281 99487482066070131066586646083327982803560379205391980139946496955261
we can say that the last digits of the two primes that divide it could be (1,1), (3,7) or (9,9).
Friday, 23 January 2015
The division property in integer-like sets
In 'Elements of Number Theory' John Stillwell considers the division property in the integer-like sets of numbers Z[i] (the Gaussian integers, p107) and Z[√-2] (an example of a set of quadratic integers, p119). In the case of the Gaussian integers it is relatively easy to visualize 'multiples' of integers as forming a square grid as in Figure 6.1. However, for the quadratic integers Z[√-2] this doesn't appear to be so easy and you wonder how the grid in Figure 7.1 arises and how Pythagoras' theorem in this case can be applied in the proof.
I will attempt to go through both cases and explain how I see it. Firstly, the Gaussian integers. Suppose μ and β are the Gaussian integers
$$ \mu=m+ni...(1)$$
$$ \beta=r+si...(2)$$
where m, n, r and s are elements of Z and i=√-1. Then
$$\mu\beta=m\beta+n\beta i...(3)$$
Now we have that
$$\beta i=ri+si^{2}=-s+ri...(4)$$
If we think of β and βi as vectors on the complex plane, then β is the vector (r,s) and βi is the vector (-s,r). So, as Stillwell says, i rotates the vector β anticlockwise through 90 degrees. We can see that using the standard dot product of these vectors
$$(r,s)\cdot(-s,r)=r(-s)+sr=0...(5)$$
as expected for mutually orthogonal vectors. We can see therefore that equation (3) is telling us that μβ is the sum of real multiples of β and βi. We can therefore think of this as a square grid with β and βi as base vectors, as anticipated.
Now what about the quadratic integers Z[√-2]? Suppose that this time μ and β are the quadratic integers
$$ \mu=a+b\sqrt{-2}...(6)$$
$$ \beta=c+d\sqrt{-2}...(7)$$
where a, b, c, and d are elements of Z. Then
$$\mu\beta=a\beta+b\beta\sqrt{-2}...(8)$$
What is β√-2? We have
$$\beta\sqrt{-2}=c\sqrt{-2}+d(\sqrt{-2})^{2}=-2d+c\sqrt{-2}...(9)$$
If we again think about μ and β as being vectors, then β is the vector (c,d) and β√-2 is the vector (-2d,c). In the normal sense it does not look like these two vectors are orthogonal, however, if we define the dot product of two vectors (w,x) and (y,z) to be
$$(w,x)\cdot(y,z)=wy+2xz...(10)$$
then
$$(c,d)\cdot(-2d,c)=-2cd+2dc=0...(11)$$
and so we retrieve the orthogonality of β and β√-2. The definition in equation (10) also fits in with the definition of the norm since
$$norm\beta=(c,d)\cdot(c,d)=c^{2}+2d^{2}...(12)$$
which is as defined by Stillwell (p120). Hence we can again think that equation (8) is telling us that μβ is the sum of real multiples of β and β√-2; i.e. we can think of a grid with β and β√-2 being base vectors, as described in the book (Figure 7.1). Note, however, that this is not a square grid as β and β√-2 are not the same length.
I want to go one step further and show that the proof on page 119 doesn't have to rely on Pythagoras' Theorem. We can see from Figure 7.1 that |ρ| is less than or equal to the length of the vector from the origin to the centre of the figure. That is the vector
$$\frac{\beta}{2}+\frac{\beta\sqrt{-2}}{2}...(13)$$
which is
$$\frac{1}{2}(c,d)+\frac{1}{2}(-2d,c)=\frac{1}{2}(c-2d,d+c)...(14)$$
It follows that
$$\left|\rho\right|^{2}\le\frac{1}{2}(c-2d,d+c)\cdot\frac{1}{2}(c-2d,d+c)...(15)$$
Expanding the RHS we get
$$ \frac{1}{2}(c-2d,d+c)\cdot\frac{1}{2}(c-2d,d+c)=\frac{1}{4}((c-2d)^{2}+2(d+c)^{2})=\frac{1}{4}(c^{2}-4cd+4d^{2}+2d^{2}+4cd+2c^{2})...(16)$$
and so
$$ \frac{1}{2}(c-2d,d+c)\cdot\frac{1}{2}(c-2d,d+c)=\frac{1}{4}(3c^{2}+6d^{2})=\frac{3}{4}(c^{2}+2d^{2})=\frac{3}{4}\left|\beta\right|^{2}...(17)$$
Hence we have
$$\left|\rho\right|^{2}\le\frac{3}{4}\left|\beta\right|^{2}...(18)$$
as obtained in the book.
I will attempt to go through both cases and explain how I see it. Firstly, the Gaussian integers. Suppose μ and β are the Gaussian integers
$$ \mu=m+ni...(1)$$
$$ \beta=r+si...(2)$$
where m, n, r and s are elements of Z and i=√-1. Then
$$\mu\beta=m\beta+n\beta i...(3)$$
Now we have that
$$\beta i=ri+si^{2}=-s+ri...(4)$$
If we think of β and βi as vectors on the complex plane, then β is the vector (r,s) and βi is the vector (-s,r). So, as Stillwell says, i rotates the vector β anticlockwise through 90 degrees. We can see that using the standard dot product of these vectors
$$(r,s)\cdot(-s,r)=r(-s)+sr=0...(5)$$
as expected for mutually orthogonal vectors. We can see therefore that equation (3) is telling us that μβ is the sum of real multiples of β and βi. We can therefore think of this as a square grid with β and βi as base vectors, as anticipated.
Now what about the quadratic integers Z[√-2]? Suppose that this time μ and β are the quadratic integers
$$ \mu=a+b\sqrt{-2}...(6)$$
$$ \beta=c+d\sqrt{-2}...(7)$$
where a, b, c, and d are elements of Z. Then
$$\mu\beta=a\beta+b\beta\sqrt{-2}...(8)$$
What is β√-2? We have
$$\beta\sqrt{-2}=c\sqrt{-2}+d(\sqrt{-2})^{2}=-2d+c\sqrt{-2}...(9)$$
If we again think about μ and β as being vectors, then β is the vector (c,d) and β√-2 is the vector (-2d,c). In the normal sense it does not look like these two vectors are orthogonal, however, if we define the dot product of two vectors (w,x) and (y,z) to be
$$(w,x)\cdot(y,z)=wy+2xz...(10)$$
then
$$(c,d)\cdot(-2d,c)=-2cd+2dc=0...(11)$$
and so we retrieve the orthogonality of β and β√-2. The definition in equation (10) also fits in with the definition of the norm since
$$norm\beta=(c,d)\cdot(c,d)=c^{2}+2d^{2}...(12)$$
which is as defined by Stillwell (p120). Hence we can again think that equation (8) is telling us that μβ is the sum of real multiples of β and β√-2; i.e. we can think of a grid with β and β√-2 being base vectors, as described in the book (Figure 7.1). Note, however, that this is not a square grid as β and β√-2 are not the same length.
I want to go one step further and show that the proof on page 119 doesn't have to rely on Pythagoras' Theorem. We can see from Figure 7.1 that |ρ| is less than or equal to the length of the vector from the origin to the centre of the figure. That is the vector
$$\frac{\beta}{2}+\frac{\beta\sqrt{-2}}{2}...(13)$$
which is
$$\frac{1}{2}(c,d)+\frac{1}{2}(-2d,c)=\frac{1}{2}(c-2d,d+c)...(14)$$
It follows that
$$\left|\rho\right|^{2}\le\frac{1}{2}(c-2d,d+c)\cdot\frac{1}{2}(c-2d,d+c)...(15)$$
Expanding the RHS we get
$$ \frac{1}{2}(c-2d,d+c)\cdot\frac{1}{2}(c-2d,d+c)=\frac{1}{4}((c-2d)^{2}+2(d+c)^{2})=\frac{1}{4}(c^{2}-4cd+4d^{2}+2d^{2}+4cd+2c^{2})...(16)$$
and so
$$ \frac{1}{2}(c-2d,d+c)\cdot\frac{1}{2}(c-2d,d+c)=\frac{1}{4}(3c^{2}+6d^{2})=\frac{3}{4}(c^{2}+2d^{2})=\frac{3}{4}\left|\beta\right|^{2}...(17)$$
Hence we have
$$\left|\rho\right|^{2}\le\frac{3}{4}\left|\beta\right|^{2}...(18)$$
as obtained in the book.
Sunday, 4 January 2015
Geometric characterization of the primes that are sums of two squares
Previously, we saw that Fermat's two square theorem says that all primes of the form 4n+1 are the sum of two integer squares. Using Euclid's integer solutions to the Pythagorean equation z2=x2+y2 we obtain the following geometric characterization of the primes that are the sum of two squares (Elements of Number Theory p112):-
"The primes that are the sums of two squares are those that occur as hypotenuses of right-angled triangles with integer sides."
This is a nice result. We can now imagine all of these sorts of primes as being part of right-angled triangles with integer sides and there are infinitely many of them. It is a very satisfactory geometric picture of these types of primes. However, is the triangle with hypotenuse prime p unique? This is the basis of Exercise 6.6.2 (p112):-
"6.6.2. Given a prime p=4n+1, is the integer right-angled triangle with hypotenuse p unique?"
As an example of some of the work that I have done with this book, I thought I would show how I proved this.
We aim for a proof by contradiction. Given a prime p=4n+1 we suppose to the contrary that the integer right-angled triangle with hypotenuse p is not unique. So there are at least two integer right-angled triangles with hypotenuse p. Let the non-hypotenuse sides of two of these triangles be a1, b1, and a2, b2.
Firstly, we can show that a1 and b1 are coprime. Suppose that they are not then there exists a positive integer c (not equal to 1) that divides a1 and b1 such that a1=cx1 and b1=cy1. Then by Pythagoras for a right-angled triangle:-
$$ a_{1}^{2}+b_{1}^{2}=p^{2} $$
$$ \Rightarrow c^{2}x_{1}^{2}+c^{2}y_{1}^{2}=p^{2}$$
$$ \Rightarrow c^{2}(x_{1}^{2}+y_{1}^{2})=p^{2}$$
Now as c divides the LHS, c must divide p2, but the only divisors of p2 are 1, p or p2. If c was p2 this would imply
$$ x_{1}^{2}+y_{1}^{2}=1/p^{2}$$
and x1 and y1 would not be integers. If c was p then this would imply
$$ x_{1}^{2}+y_{1}^{2}=1$$
and so either x1=0 and y1=1 or x1=1 and y1=0 and these are not right-angled triangles. Hence c=1 and we have reached a contradiction. Thus a1 and b1 are coprime (as are a2 and b2).
Hence, by the theorem for Primitive Pythagorean Triples (top of page 112) we can say that
$$a_{1}=u_{1}^{2}-v_{1}^{2}$$
$$b_{1}=2u_{1}v_{1}$$
$$a_{2}=u_{2}^{2}-v_{2}^{2}$$
$$b_{2}=2u_{1}v_{2}$$
for some integers u1,v1,u2,v2. It follows that
$$a_{1}^{2}+b_{1}^{2}=(u_{1}^{2}+v_{1}^{2})^{2}=p^{2}$$
and
$$a_{2}^{2}+b_{2}^{2}=(u_{2}^{2}+v_{2}^{2})^{2}=p^{2}$$
However, we know that as p=4n+1 there is only one u, v such that p=u2+v2 (top of page 110) and so there is only one u, v such that p2=(u2+v2)2. Thus, we have reached a contradiction. Hence the integer right-angled triangle with hypotenuse p must be unique.
"The primes that are the sums of two squares are those that occur as hypotenuses of right-angled triangles with integer sides."
This is a nice result. We can now imagine all of these sorts of primes as being part of right-angled triangles with integer sides and there are infinitely many of them. It is a very satisfactory geometric picture of these types of primes. However, is the triangle with hypotenuse prime p unique? This is the basis of Exercise 6.6.2 (p112):-
"6.6.2. Given a prime p=4n+1, is the integer right-angled triangle with hypotenuse p unique?"
As an example of some of the work that I have done with this book, I thought I would show how I proved this.
We aim for a proof by contradiction. Given a prime p=4n+1 we suppose to the contrary that the integer right-angled triangle with hypotenuse p is not unique. So there are at least two integer right-angled triangles with hypotenuse p. Let the non-hypotenuse sides of two of these triangles be a1, b1, and a2, b2.
Firstly, we can show that a1 and b1 are coprime. Suppose that they are not then there exists a positive integer c (not equal to 1) that divides a1 and b1 such that a1=cx1 and b1=cy1. Then by Pythagoras for a right-angled triangle:-
$$ a_{1}^{2}+b_{1}^{2}=p^{2} $$
$$ \Rightarrow c^{2}x_{1}^{2}+c^{2}y_{1}^{2}=p^{2}$$
$$ \Rightarrow c^{2}(x_{1}^{2}+y_{1}^{2})=p^{2}$$
Now as c divides the LHS, c must divide p2, but the only divisors of p2 are 1, p or p2. If c was p2 this would imply
$$ x_{1}^{2}+y_{1}^{2}=1/p^{2}$$
and x1 and y1 would not be integers. If c was p then this would imply
$$ x_{1}^{2}+y_{1}^{2}=1$$
and so either x1=0 and y1=1 or x1=1 and y1=0 and these are not right-angled triangles. Hence c=1 and we have reached a contradiction. Thus a1 and b1 are coprime (as are a2 and b2).
Hence, by the theorem for Primitive Pythagorean Triples (top of page 112) we can say that
$$a_{1}=u_{1}^{2}-v_{1}^{2}$$
$$b_{1}=2u_{1}v_{1}$$
$$a_{2}=u_{2}^{2}-v_{2}^{2}$$
$$b_{2}=2u_{1}v_{2}$$
for some integers u1,v1,u2,v2. It follows that
$$a_{1}^{2}+b_{1}^{2}=(u_{1}^{2}+v_{1}^{2})^{2}=p^{2}$$
and
$$a_{2}^{2}+b_{2}^{2}=(u_{2}^{2}+v_{2}^{2})^{2}=p^{2}$$
However, we know that as p=4n+1 there is only one u, v such that p=u2+v2 (top of page 110) and so there is only one u, v such that p2=(u2+v2)2. Thus, we have reached a contradiction. Hence the integer right-angled triangle with hypotenuse p must be unique.
Subscribe to:
Posts (Atom)