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!

AWOL

As you can see I haven't posted anything here for six months and some of you may be wondering what has happened. Well, to cut a long story short I abandoned my OU studies in February and, at present, I am not sure if I will be continuing on with them. Though I was reluctant to stop working on these courses, in the end I had to because they were taking up far too much of my time. On reflection it would have been better for me to have started just one of these courses instead of both of them and if I had I would probably have kept going. However, due to the changes that the OU made to the time limits for the degree I was taking and the fact that these courses were going to be discontinued, it wasn't possible for me to do this and so eventually I sort of gave in and didn't have the will power to continue. It is a pity but it isn't the end of the world. I feel it is a shame that the OU made these wholesale changes to their degree structure that left people like myself, who like to take things at a considered pace, high and dry. It's their loss as well as mine.

So what now? I have gone back to reading Elements of Number Theory by John Stillwell and have nearly got half way through the book. I am both reading and understanding the text as well as answering the exercises. It is a well written book and the exercises bring out what is in the text without being overly difficult. I have just finished the chapter on the Pell Equation and I liked the visual approach of Conway which is described. I also went through the previous chapter on the RSA cryptosystem and this enhances what we learnt at the OU. I have written some programs for coding and decoding messages on my other calculator blog.

As for the future I am not really sure what direction I should now take. I suspect I will continue on with the personal study until I get that desire to study more formally again. There are plenty of courses that are appearing online as Chris has been pointing out.

Slogging on

I am still slogging on with the number theory and groups courses. Regularly I ask myself why I am doing this, but then I know that I like having something to focus on that keeps me busy. But sometimes it is just so blooming difficult!

At the moment I am trying to cram in some work on TMA03 of the numbers course. I sort of dread it in advance because these TMAs are really quite difficult. Often the questions don't relate directly to the course material. They use the ideas but in a way that you haven't seen before, so it really makes you think. There is, however, the feeling of huge elation when you do manage to conquer a problem. I take these questions a small chunk at a time. Often I will read the next part of a question and start mulling it over in my head. At first it seems impossible, but after a few glints of ideas, you get an idea of the framework for an answer and then you can flesh the whole thing out. I often go to bed thinking about a knotty problem. It is a good time to give a problem your undevoted attention without distraction, but I can't say it is a good way to get to sleep!

I have now finished NT6 on quadratic reciprocity. One more book and I would have the third block finished for M381. The groups course is going ok. The problem is that the ideas are increasingly complicated and although I tenuously understand a book when I have read it, it rapidly gets forgotten after a few weeks. I have finished GE3 and am currently on GR4 which is investigating finite groups and what we know about them.