The largest known prime number

The largest known prime as of the 5th January 2015 is the 17,425,170 decimal digit Mersenne prime 2^57885161-1. Assuming that you could write at one digit a second, it would take you about six and a half months even to write this number down. I want to demonstrate the power of the exponentiation modulo n program that I wrote for the Casio fx-50F by calculating some of the last digits of this number.

Firstly, though, I will look at some Mersenne primes that we can write down relatively easily. M₃₁ can be computed on the fx50F and is the number 2³¹-1=2147483647. We can verify that the last digit is 7 by computing M₃₁ modulo 10. What we actually do is compute 2³¹ (mod 10) and subtract 1 (mod 10) which comes to the same thing. Running the exponentiation program with X=2, A=31 and B=10 gives the result D=8. That is 2³¹ (mod 10) is congruent to 8 (mod 10). Subtracting 1 (mod 10) from this gives us 7, which is the anticipated last digit of M₃₁.

M₁₂₇ is the number 2¹²⁷-1=170141183460469231731687303715884105727. Running the program with X=2, A=127 and B=10 gives the result D=8 from which we again deduce that the last digit is 7.

So what about M_57885161? Can the program compute the last decimal digit of such a large number? Running the program with X=2, A=57885161 and B=10 gives D=2 after 27 seconds of processing. This means that the last digit of this number is 1. We can also find the last two digits by computing M_57885161 (mod 100) and after 2 minutes 47 seconds the program calculates these to be 51. A further calculation (mod 1000) lasting 23 minutes shows that the last three digits are 951.

So what's the next largest Mersenne number? The next largest prime after 57885161 is 57885167 and so 2^57885167-1 may or may not be a prime. If it isn't prime then it will have a factor which is a number of the form 115770334n+1 where n is a positive integer. Good luck with trying out your long division!

RSA encryption - a warning!

I should perhaps at this point warn people not to try to use any of what I have described in my last few blogs about this subject to actually encrypt anything of value. This is all for demonstration purposes to illustrate the mathematics and computing of RSA. It is not for real world situations! If you need to encrypt anything please use a reputable program!

RSA Encryption - another example and discussion

Following on from my previous blog I thought I would encrypt a message that you out there can have a go at decrypting. Here it is: 331, 230, 230, 311, 392, 507, 180, 221, 187, 466, 283, 392, 442, 230, 127. The key information is n=551 and e=41. This should be enough for you to decrypt this message.

Of course with a programmable calculator there is a limit to what you can usefully do with RSA. One of the problems of the fx-50F is that there isn't a function which can do modulo arithmetic and nor  is there a way to find integer parts and remainders on division, and so the ways round this (the while loops in my exponentiation mod n program) make processing much too slow when n becomes larger than a 1000 or so. Hence, this doesn't make the encryption viable unless the keys are hidden.

In reality there is also the issue of finding two primes for n. You don't want to choose one of the primes to be large and the other small, as the small prime will easily be found as a factor in n. However, you also don't want to choose two primes that are very close in value because, as we shall see, n can again be factored quite quickly. So we need two similarly large primes that are not too close in value to make RSA work.

There are other issues as well. We don't want to have the message number m larger than n. Suppose we have the system as set up in my previous example and encrypt m=250, that is we want 250¹³ (mod 221). We get m'=133. But if we decrypt m'=133 by working out 133¹³³ (mod 221) we find m=29. That's because 250 is congruent to 29 modulo 221. So we don't get a one-to-one relationship.

If we choose much bigger primes, n becomes sufficiently large that we can start encrypting blocks of text. For example, in the message 'all aliens are friendly' we could take the word 'all' and convert it into a single number 11212. The next three characters ' al' would be 270112 etc.

Finally, in some situations we find that the encrypted message number m' and the message number m end up being the same and this may be something to avoid.

RSA Encryption - an example

Following my previous blog about RSA encryption let's now try and encrypt the message 'all aliens are friendly'.

Using the Is it prime? program, we can choose a couple of prime numbers. We try some relatively small numbers 13 and 17 which you can easily verify are both prime. Run the Is it prime? program. X? is displayed. Enter 13 and press [EXE]. 1 is returned (1 - number is prime, 0 - number is not prime). So our number n=13x17=221 and φ(221)=(p₁-1)(p₂-1)=12x16=192.

Next we choose e. We choose e=13 and using the program gcd by subtraction you can verify that gcd(13,192)=1. Run the program. A? is displayed. Enter 13 and press [EXE]. B? is displayed. Enter 192 and press [EXE]. The result 1 is displayed indicating that the gcd(13,192)=1.

Next we calculate d which is the inverse of e modulo 192. Run the program Multiplicative inverses in Zn. A? is displayed. Enter 13 and press [EXE]. B? is displayed so enter 192 and press [EXE]. After a bit of a wait the result of 133 is displayed. So d=133.

So now we can encrypt the message 'all aliens are friendly'. The letter a corresponds to 1 and we can see immediately that m'=1 since 1¹³≡1 (mod 221). The letter l corresponds to 12 and so we need to calculate m'≡12¹³(mod 221). Run the Exponentiation mod n program. X? is displayed. Enter 12 and press [EXE]. A? is displayed. Enter 13 and press [EXE]. B? is displayed, so enter 221 and press [EXE]. The result is 116 and this is m'. Thus so far the encrypted message is in numbers 1, 116, 116 for the word 'all'.

Continuing in this way we can obtain the full encrypted message 1, 116, 116, 79, 1, 116, 178, 122, 209, 32, 79, 1, 18, 122, 79, 214, 18, 122, 209, 4, 116, 77.

To decrypt the message we need to take each number m' in the encrypted message and calculate m≡(m')¹³³ (mod 221) which again you can use the Exponentiation mod n program to do.

RSA Encryption

Having written these four programs for the fx-50F:-

1. Multiplicative inverses in Zn
2. Is it prime?
3. gcd by subtraction
4. Exponentiation mod n

I am now in a position to be able to demonstrate one of the most widely used encryption methods on the web, RSA. The RSA cryptosystem was first described by Ron Rivest, Adi Shamir and Leonard Adleman in 1978. The complexity of decrypting, i.e. reading an encrypted message using RSA relies heavily on the difficulty of finding the prime factors of very large numbers. For example, if p₁ and p₂ are prime numbers 567451 and 368957 then it is relatively easy to calculate their product p₁p₂=209365018607 but it would be relatively difficult to find their original factors if only the product was known. In the actual implementation of this system prime numbers of typically hundreds of decimal digits are used.

Here is a prescription for using RSA.

1. Choose two prime numbers p₁ and p₂
2. Calculate n=p₁p₂ and φ(n)=(p₁-1)(p₂-1)
3. Choose a positive integer encryption exponent e such that e is less than φ(n) and the gcd(e,φ(n))=1
4. Calculate the decryption exponent d which is the inverse of e modulo φ(n), that is ed≡1 (mod φ(n))
5. To encrypt a positive integer message m calculate m' where m'≡m^e (mod n)
6. To decrypt message m' calculate m≡(m')^d (mod n)

φ(n) is Euler's phi function and is the number of positive integers less than n that are coprime to n. If we have some plaintext message such as 'all aliens are friendly' then one method for encryption using RSA is to take each letter at a time, and encrypt it's numeric position in the alphabet (where 1=a, 2=b, etc). A space ' ' could be given designation 27.

This is a public key encryption system. The receiver of encrypted messages makes n and e public but keeps p₁ and p₂ (and hence φ(n) and d) private. By doing so anyone can send an encrypted message to the receiver but only the receiver (hopefully) can decrypt the messages.

Exponentiation mod n - execution of the program

In my previous post I detailed a program for finding remainders when a number like 67¹¹ is divided by 41. In my first post I showed that 67¹¹ is the 21 digit number 122130132904968017083 and the remainder on dividing by 41 is 12. On executing the program the display shows X? Enter 67 and press [EXE]. Next A? is displayed and this is the index, so enter 11 and press [EXE]. Then enter the divisor 41 when B? is displayed. On pressing [EXE] again the calculator computes the remainder D and this is shown as 12, which is as expected. Pressing [EXE] again allows another set of numbers to be entered.

If we didn't know what the number 67¹¹ looks like we could at least determine what its last two digits were by replacing the divisor B in the above with 100. When we do this the program calculates the remainder as 83 as expected.

The program is surprisingly fast even for what are very large numbers. For example 67⁶¹⁷ is the 1,127 digit number (from WolframAlpha)

48770057363439563967134348355325038065481286153662007642823470550486

71980560027835524800048781488164580806474123084454431777128171666866

18607377904496236891798400886042117666614291800426648265371610864835

40929572898386140596732260223574328368309073158031647754279482918284

65663724881612657390133487402742747112192939724971784183405095503257

69918877553469511522677242675385108662437741711997020059606722804142

09675268052772569724085754968798539106891583795237329222561781805522

85062589820240643630480393850097329533051647302120862011637881575053

71309698184194685080288379701970330799370917504675997998122640686686

98423317552437389277363219335647530610628399241914162225364781445082

70644504402991235669883493855155234017024331172877674569648340943127

70360444117552920156878524196353157664201104105212692362637491637938

54079014668035647988158392840059044333758548155163870985659977545610

52000559917423988628809593315580421167977682921477636773152575740312

22156667453352073011960706603866023551139632454252812187342672444656

55949111316392732278972914732349074457742403565481714331119758806068

559399641911405354923544154126627269027

However, using the fx-50F program we can determine that the last digit of this number is 7 in only a few seconds (this is 67⁶¹⁷mod 10).

Exponentiation mod n - the program

I discussed the logic for this program in a previous blog. Here is the logic converted into a program for the fx-50F:-

Lbl 0:?→X:?→A:?→B:While X≥B:X-B→X:WhileEnd:X→Y:2→C:1→D:
If C>A:Then X→D:Goto 2:IfEnd:Lbl 1:X²→X:While X≥B:X-B→X:
WhileEnd:2C→C:C≤A=>Goto 1:C÷2→C:A-C→A:DX→D:While D≥B:
D-B→D:WhileEnd:Y→X:2→C:C≤A=>Goto 1:A=1=>DY→D:While D≥B:
D-B→D:WhileEnd:Lbl 2:D▲Goto 0:

This program is 163 steps in length.