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 Z₀ there are either two or three solutions for the pair (X₀,Y₀) (I shall ignore the fact that we can swap the values for X₀ and Y₀, 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 (X₀,Y₀) and we plug it back into equation (1) to find C₁, 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 X₀ and Y₀) are not zero. This equation may or may not have solutions and I will consider this in future blogs. However, consider the case when (X₀,Y₀) is (3,7) (so Z₀ is 1 and C₁ is 2) and suppose Z₁ 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 (X₀,Y₀) we can end up with 10 possibilities for (X₁,Y₁). Now we can again choose one of these solutions for (X₁,Y₁), substitute it into equation (2) and using our original values for (X₀,Y₀) and C₁ arrive at a value for C₂.

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 Y₀ and b is X₀. 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 (X₀,Y₀), (X₁,Y₁), (X₂,Y₂) and (X₃,Y₃), 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).

RSA Factoring Challenge (part 3)

Suppose you had two prime numbers p and q, both m digits long, and these were, respectively, X_m-1X_m-2...X₁X₀ and Y_m-1Y_m-2...Y₁Y₀ (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 Z_2m-1Z_2m-2Z_2m-3...Z₁Z₀ (where the subscripted Z's represent the decimal digits of n). This means that Z_2m-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 X₃Y₀ and X₀Y₃ have a multiple of 10 which is the same for each term. Since Z_i (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 C_i for each equation so that we can accommodate the multiples of 10 accumulated in the previous equation. We also know that Z₇ may be zero in which case so might be C₇ (via equation 8).

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 10^m-1 as 10^m 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 10^m-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.

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

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).

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.

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 z²=x²+y² 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 a₁, b₁, and a₂, b₂.

Firstly, we can show that a₁ and b₁ are coprime. Suppose that they are not then there exists a positive integer c (not equal to 1) that divides a₁ and b₁ such that a₁=cx₁ and b₁=cy₁. 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 p², but the only divisors of p² are 1, p or p². If c was p² this would imply

$$ x_{1}^{2}+y_{1}^{2}=1/p^{2}$$

and x₁ and y₁ would not be integers. If c was p then this would imply

$$ x_{1}^{2}+y_{1}^{2}=1$$

and so either x₁=0 and y₁=1 or x₁=1 and y₁=0 and these are not right-angled triangles. Hence c=1 and we have reached a contradiction. Thus a₁ and b₁ are coprime (as are a₂ and b₂).

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 u₁,v₁,u₂,v₂. 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=u²+v² (top of page 110) and so there is only one u, v such that p²=(u²+v²)². Thus, we have reached a contradiction. Hence the integer right-angled triangle with hypotenuse p must be unique.

Gaussian Integers and Fermat's two square theorem

I was trying to explain to someone recently what I thought mathematics was all about and why it interests me. I found it difficult to put into words some of the ideas and complexities I have seen over the last few years and I had trouble explaining why mathematics is such never-ending treasure chest of ideas. Sometimes you do get the odd glimpse of a fundamental principle and the topic I have just read about Gaussian integers seems to exemplify that.

What is a Gaussian integer? These are a generalization of the ordinary set of integers Z and can be defined as the set of complex numbers

$$ \mathbb{Z} \left[i\right]=\left\{a+bi:a,b\in  \mathbb{Z}\right\}$$

Is it possible to find similarities between this set and the set of ordinary integers and if so what do these common properties tell us about the nature of integers in general? Well it turns out that these two sets do have properties that are in common. For example, it is possible to show that there are Gaussian prime numbers much as there are ordinary prime numbers and you can go on to define properties such as division, greatest common divisor, unique prime factorisation etc which is all very interesting.

So how does this come about? Well, firstly you define the norm of an element of Z[i] to be

$$norm(a+bi)=|a+bi|^{2}=a^{2}+b^{2}$$

and from the properties of the modulus we know that

$$|z_{1}z_{2}|=|z_{1}||z_{2}|$$

and so norms multiply, that is

$$norm\left(z_{1}z_{2}\right)=norm\left(z_{1}\right)norm\left(z_{2}\right)$$

Now because the norm is a real natural number we can define a Gaussian prime to be a Gaussian integer that is not the product of Gaussian integers of smaller norm. For example, 3+2i is a Gaussian prime because norm(3+2i)=13 which is prime in Z and so not the product of Gaussian integers of smaller norm. On the other hand 3+i is not a Gaussian prime because norm(3+i)=10 and since 2 and 5 divide 10 then we might expect 3+i to be factorisable, which it is since 3+i=(1-i)(1+2i) and the norm of 1-i is 2 and that of 1+2i is 5.

When it comes to deciding whether ordinary primes are also Gaussian primes we come to an interesting property. For example, 2 is not a Gaussian prime because 2=(1+i)(1-i) and so can be divided by 1+i or 1-i. On the other hand 3 is a Gaussian prime. This is because norm(3)=9 and there are no Gaussian integers with norm 3 which divide 9 (the smallest non-trivial norms are 2, 5, 8...). Now 2 is the sum of two squares, whilst 3 is not and you can go on to show that ordinary prime p is a Gaussian prime if and only if p is not the sum of two squares (or alternatively ordinary prime p is the sum of two squares if and only if p is not a Gaussian prime).

This leads on to the proof of what I think is a fascinating theorem. Fermat's two square theorem states that if p=4n+1 is prime, then p=a²+b² for some a,b in Z. Since for p>2 every prime is either of the form 4n+1 or 4n+3, then this characterises half the primes as being the sum of two squares. The proof comes from the use of Lagrange's Lemma which states that a prime p=4n+1 divides m²+1 for some integer m (this comes from Wilson's theorem). Since m²+1=(m-i)(m+i) in Z[i] although p divides m²+1 it does not divide m-i or m+i as m/p - i/p and m/p + i/p are not Gaussian integers. By the Gaussian prime divisor property if a Gaussian prime divides the product of Gaussian numbers (m-i)(m+i) then it should divide either m-i or m+i and, as it doesn't, then p can't be a Gaussian prime. As we have seen from above this means that p is the sum of two squares.

Why I find this fascinating is that although prime numbers appear to be a random sequence of numbers we do have this structured form for half the set. It makes me wonder if there is any construction for primes of the form 4n+3? Also, are the a,b that are used to construct the primes of the form 4n+1 drawn from all of Z or are there numbers which are missing? All this gets me thinking!