I haven't posted anything here for nearly two years - where does the time go! Since that time I have continued on with my study of number theory and getting through chapters 9 and 10 of John Stillwell's Elements of Number Theory on Quadratic Reciprocity and Rings. I was making very slow progress I must say. I started chapter 11 on Ideals but before I had got very far I felt like a change and last September began reading the books in the OU's M337 Complex Analysis course. So far I have only worked through book A1 and am halfway through A2. Slow progress indeed! I just do enough to keep the old brain ticking over.
Book A1 of M337 introduces complex numbers and goes over some familiar stuff that we have seen in MS221 and M208 (e.g. nth roots of a complex number). Book A2 is a bit more interesting as it starts to deal with complex functions where the domain and image are sets of complex numbers. Here, nothing is very obvious as we are mapping from a 2d plane to a 2d plane and it is not easy to see what a function is doing. One thing that struck me, that I hadn't really thought about before, is that the complex plane is not an ordered field like the set of real numbers. For example, you can't write an inequality like 1+2i > 1+i. So any ordering can only be done with functions that map to a real line (such as the modulus).
I also liked the approach to determining the image of a complex function. For example, Problem 1.2(b) asks you to determine the image of the function f with rule f(z) = (3z+1)/(z+i). Now there is a convention which states that if a function is specified by just its rule then it is understood that its domain is the set of all complex numbers to which the rule is applicable and its codomain is C (the set of all complex numbers). So here the domain A = C - {-i} (i.e. the whole of the complex plane except the point -i) because when z = -i the denominator in the rule is zero. So the image of f is
$$ f(A) = \{ w = \frac{3z+1}{z+i} : z \in A \}$$
The aim is to write this set in terms of the image point w and a condition on w. Since
$$ w = \frac{3z+1}{z+i} \Leftrightarrow w(z+i)=3z+1 \Leftrightarrow z(w-3)=1-wi \Leftrightarrow z = \frac{1-wi}{w-3}$$
the the image of f is
$$ f(A) = \{ w : z = \frac{1-wi}{w-3} \neq -i \}$$
Now we can imagine the image point w moving around the complex plane and at the same time see the point z in the domain from which it is mapped. We want both w to exist and z not to be equal to -i. You can see that z is never equal to -i for any w in C. Also, (1-wi)/(w-3) is just another complex number and so, as w ranges over all of C, so does z. The only point that is excluded in the image is when w=3 as again this would make the denominator in z zero. Thus we have that
$$ f(A) = \{ w : w \neq 3 \} $$
and so the image of f is C - {3}. Neat!
Sunday 4 March 2018
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.
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.
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!
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).
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).
Subscribe to:
Posts (Atom)