In my previous post I detailed a program for obtaining the remainder when a number like 4593 is divided by 7. I now want to show how this works and how we can find remainders even when the numbers exceed the range of input of the fx-50F.
Let's start by finding the remainder when 4593 is divided by 7. On executing the program the display shows A? A is the divisor and so input 7 and press [EXE]. Next X? is displayed. The digits of 4593 are entered here and so begin with the digit furthest to the right and input 3 and press [EXE]. Continue by entering 9, then 5, and then 4 in a similar fashion. Once 4 has been processed X? will be displayed again and to notify the program that all the digits of the number have been entered, input -1 and press [EXE]. The program then displays the value of memory C which is the result, 1. This is as expected. The remainder on dividing 4593 by 7 is 1.
In an earlier post I also showed that the 21 digit number 122130132904968017083 leaves remainder 12 when divided by 41. To confirm this we can run the program again. Enter 41 for A and then process the digits from right to left starting with 3. We obtain the result that C displays 12 as expected. Note that 21 digits exceeds the limit of 15 digits that can be stored in the fx-50F.
Finally, I return to prove that Frank Cole's calculation that the Mersenne number 147573952589676412927 is the product 193707721 × 761838257287. First, we show that 193707721 divides this number. We run the program again with 193707721 entered for A and then the 21 digits of the number 147573952589676412927 entered from right to left, finishing with -1 to terminate the input. The result is remainder 0 which is as expected since 193707721 is a factor. Secondly we run the program again with 761838257287 entered for A and then the 21 digits of 147573952589676412927. Again the remainder is 0 which shows that 761838257287 does divide 147573952589676412927.
Tuesday, 17 March 2015
Tuesday, 3 March 2015
Remainder on division - 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:-
This program is 104 steps in length.
1→B:0→C:10→D:?→A:While D≥A:D-A→D:WhileEnd:Lbl
1:?→X:X=-1=>Goto 2:While X≥A:X-A→X:WhileEnd:C+BX→C:While C≥A:C-A→C:WhileEnd:DB→B:While B≥A:B-A→B:WhileEnd:Goto 1:Lbl 2:C▲
This program is 104 steps in length.
Friday, 27 February 2015
Remainder on division - comments on the logic
In my previous post I presented some logic for obtaining the remainder when a number like 4593 is divided by 7. I now want to go through how this logic works.
Some initial values are first stored in memory locations B, C and D and the use of these memories is explained as we go along. The divisor (in our example 7) is input in memory A and remains fixed. Memory D contains the common factor of 10 in our process and the first while loop finds the remainder when 10 is divided by 7 and the result, 3, is stored in D.
The first digit of our number (in our example this is 3) is input after label 1. Essentially this is the main loop of our program. The digits of 4593 are entered reading from right to left and when the last digit has been read, the process is terminated by entering -1 in X.
Each digit is processed as follows. Firstly, the initial while loop determines the remainder on dividing X by A. For the first digit in our example this is the remainder on dividing 3 by 7 (which is 3). Each time we process a new digit of our number 4593 we add to memory C the product of X (the remainder on dividing our digit by 7) and the remainder on dividing the power of 10 by 7 stored in B. For example, for the third digit 5, B at this stage would contain the remainder on dividing 100 by 7, namely 2. We then calculate the remainder on dividing C by A in the following while loop.
Finally, before going on to input the next digit we calculate the remainder on dividing the next power of 10 by A.
When the last digit has been processed, the required remainder in C is displayed.
Some initial values are first stored in memory locations B, C and D and the use of these memories is explained as we go along. The divisor (in our example 7) is input in memory A and remains fixed. Memory D contains the common factor of 10 in our process and the first while loop finds the remainder when 10 is divided by 7 and the result, 3, is stored in D.
The first digit of our number (in our example this is 3) is input after label 1. Essentially this is the main loop of our program. The digits of 4593 are entered reading from right to left and when the last digit has been read, the process is terminated by entering -1 in X.
Each digit is processed as follows. Firstly, the initial while loop determines the remainder on dividing X by A. For the first digit in our example this is the remainder on dividing 3 by 7 (which is 3). Each time we process a new digit of our number 4593 we add to memory C the product of X (the remainder on dividing our digit by 7) and the remainder on dividing the power of 10 by 7 stored in B. For example, for the third digit 5, B at this stage would contain the remainder on dividing 100 by 7, namely 2. We then calculate the remainder on dividing C by A in the following while loop.
Finally, before going on to input the next digit we calculate the remainder on dividing the next power of 10 by A.
When the last digit has been processed, the required remainder in C is displayed.
Wednesday, 25 February 2015
Remainder on division - the logic
In my previous post I described a method for calculating the remainder on dividing one integer by another. I now give the logic that can
be used to solve this problem on a programmable calculator.
Store 1 in B
Store 0 in C
Store 10 in D
Input A
While D ≥ A
Store D-A in D
WhileEnd
Label 1
Input X
If X=-1 then
Goto Label 2
EndIf
While X ≥ A
Store X-A in X
WhileEnd
Store C+BX in C
While C ≥ A
Store C-A in C
WhileEnd
Store DB in B
While B ≥ A
Store B-A in B
WhileEnd
Goto Label 1
Label 2
Display C
Store 1 in B
Store 0 in C
Store 10 in D
Input A
While D ≥ A
Store D-A in D
WhileEnd
Label 1
Input X
If X=-1 then
Goto Label 2
EndIf
While X ≥ A
Store X-A in X
WhileEnd
Store C+BX in C
While C ≥ A
Store C-A in C
WhileEnd
Store DB in B
While B ≥ A
Store B-A in B
WhileEnd
Goto Label 1
Label 2
Display C
Tuesday, 24 February 2015
Remainder on division - methodology
So how do we go about creating a program on the fx-50F which can calculate the remainder on dividing one integer by another? Let's go back to the example of dividing 4593 by 7. We can write this number as
4593=4000+500+90+3=4x1000+5x100+9x10+3x1
Suppose we want to calculate the remainder of 90 on division by 7. We find that 90=12x7+6 and so the remainder is 6. Alternatively we could have seen that 9=1x7+2 and 10=1x7+3 and 2x3=6. This means that we could have found the remainder we wanted by multiplying the remainders of dividing 9 and 10 by 7. A similar rule applies for addition. Suppose we want the remainder when 590 is divided by 7. This is 2 since 590=84x7+2. However, 500=71x7+3 and, as we have just seen, 90=12x7+6 and 3+6=9 and 9=1x7+2. The moral of this is that we don't have to divide the complete number 4593 by 7 but divide it in parts and work with remainders.
So how do we proceed in a way which makes it easy for a programmable calculator? Let's start with the right-most digit 3 and record the power of 10, namely 0, that goes with it. 10 to the power 0 is 1 and 1 divided by 7 leaves remainder 1 (since 1=0x7+1). 3 divided by 7 leaves remainder 3 (again since 3=0x7+3). Multiplying remainders gives 3x1=3.
Now before going on to the next digit to the left, 9, we note that the powers of 10 that go with each digit increase by 1 for each new digit we encounter. For example 1000=10x100. So rather than calculate the remainder of 1000 divided by 7 we multiply the remainder of 10 divided by 7 (i.e. 3) and the remainder of 100 divided by 7 (i.e. 2) that we calculated previously. So corresponding to the powers of 10 of 0, 1, 2, 3, ... the remainders are 1, 3, 3x3=9 which is 2, 3x2=6, etc.
Now going on to the next digit 9 we have 9 divided by 7 leaves remainder 2 and as, we have seen, the remainder for 10 divided by 7 is 3 and so 2x3=6. Adding this to the remainder for the first digit gives 6+3=9 and 9 divided by 7 leaves remainder 2.
The next digit is 5 and 5 divided by 7 leaves remainder 5. The factor of 100 divided by 7 leaves remainder 2 and 5x2=10. 10 divided by 7 leaves remainder 3 and adding this to the remainder for our first two digits gives 3+2=5.
Finally, the last digit is 4 and 4 divided by 7 leaves remainder 4. The factor of 1000 divided by 7 leaves remainder 6 (as we discussed above) and 4x6=24. 24 divided by 7 leaves remainder 3 and adding this to the remainder for our first three digits gives 5+3=8 and 8 divided by 7 leaves remainder 1. This is our final result, that is 4593 divided by 7 leaves remainder 1, as expected.
This may seem like a tedious way of going about things, but with a pocket programmable calculator the digits can be entered one by one and the time to compute the intermediate remainders is very quick and hardly interferes with the input process. The advantage is that this keeps the size of the computations down to manageable amounts and allows an integer of indeterminate length to be entered and divided (the limit being only how long before you get bored of keying in digits!).
4593=4000+500+90+3=4x1000+5x100+9x10+3x1
Suppose we want to calculate the remainder of 90 on division by 7. We find that 90=12x7+6 and so the remainder is 6. Alternatively we could have seen that 9=1x7+2 and 10=1x7+3 and 2x3=6. This means that we could have found the remainder we wanted by multiplying the remainders of dividing 9 and 10 by 7. A similar rule applies for addition. Suppose we want the remainder when 590 is divided by 7. This is 2 since 590=84x7+2. However, 500=71x7+3 and, as we have just seen, 90=12x7+6 and 3+6=9 and 9=1x7+2. The moral of this is that we don't have to divide the complete number 4593 by 7 but divide it in parts and work with remainders.
So how do we proceed in a way which makes it easy for a programmable calculator? Let's start with the right-most digit 3 and record the power of 10, namely 0, that goes with it. 10 to the power 0 is 1 and 1 divided by 7 leaves remainder 1 (since 1=0x7+1). 3 divided by 7 leaves remainder 3 (again since 3=0x7+3). Multiplying remainders gives 3x1=3.
Now before going on to the next digit to the left, 9, we note that the powers of 10 that go with each digit increase by 1 for each new digit we encounter. For example 1000=10x100. So rather than calculate the remainder of 1000 divided by 7 we multiply the remainder of 10 divided by 7 (i.e. 3) and the remainder of 100 divided by 7 (i.e. 2) that we calculated previously. So corresponding to the powers of 10 of 0, 1, 2, 3, ... the remainders are 1, 3, 3x3=9 which is 2, 3x2=6, etc.
Now going on to the next digit 9 we have 9 divided by 7 leaves remainder 2 and as, we have seen, the remainder for 10 divided by 7 is 3 and so 2x3=6. Adding this to the remainder for the first digit gives 6+3=9 and 9 divided by 7 leaves remainder 2.
The next digit is 5 and 5 divided by 7 leaves remainder 5. The factor of 100 divided by 7 leaves remainder 2 and 5x2=10. 10 divided by 7 leaves remainder 3 and adding this to the remainder for our first two digits gives 3+2=5.
Finally, the last digit is 4 and 4 divided by 7 leaves remainder 4. The factor of 1000 divided by 7 leaves remainder 6 (as we discussed above) and 4x6=24. 24 divided by 7 leaves remainder 3 and adding this to the remainder for our first three digits gives 5+3=8 and 8 divided by 7 leaves remainder 1. This is our final result, that is 4593 divided by 7 leaves remainder 1, as expected.
This may seem like a tedious way of going about things, but with a pocket programmable calculator the digits can be entered one by one and the time to compute the intermediate remainders is very quick and hardly interferes with the input process. The advantage is that this keeps the size of the computations down to manageable amounts and allows an integer of indeterminate length to be entered and divided (the limit being only how long before you get bored of keying in digits!).
Thursday, 19 February 2015
Remainder on division
One function that appears to be missing from the fx-50F Plus is finding the remainder when one integer is divided by another. For example, what is the remainder when 4593 is divided by 7, or putting this another way, what is 4593 congruent to modulo 7? The fx-50F does have the ability to calculate fractions and if you key in 4593 [a b/c] 7 [EXE] you obtain 656_1_7 which shows that 4593=656x7+1, that is the remainder when 4593 is divided by 7 is 1. Equivalently 4593 is congruent to 1 modulo 7. You have to be wary that if your divisor is not prime, then you may have to adjust the numerator of your fraction accordingly to obtain the correct remainder. For example, if you enter 4593 [a b/c] 21 [EXE] you obtain 218_5_7. Here the remainder is not 5 but 5x3=15 since the denominator is 7, not 21, in the resulting fraction. You need to multiply the fraction 5/7 top and bottom by 3 to get the correct result, that is 4593=218x21+15.
An alternative method is, of course, to carry out the division in decimals 4593/7=656.1428571. If you then take this number, subtract 656 and multiply by 7 you obtain remainder 1. This seems simple enough. But what happens if you want to do division on very large numbers? It all starts to get a bit messy and inaccurate, partly because of the number of digits that the fx-50F can accurately hold and partly because only ten digits are displayed on the screen.
For example, Edouard Lucas had shown in 1876 that the number 267-1 =147,573,952,589,676,412,927 is not prime but no one knew what its factors were. In 1903 Frank Nelson Cole (1861-1926) famously gave a presentation to the American Mathematical Society where he proceeded to calculate, in silence, 267-1 on side of the blackboard and then, on the other, the result, by hand, of 193,707,721 × 761,838,257,287. Cole, having demonstrated that the two numbers were equal, sat down, not uttering a word. He received a standing ovation!
What I would like to do is to demonstrate that we can show that either of these factors will divide this number by creating a program that will calculate that the remainder on division is zero. Furthermore, this program will cope with a natural number of any length (though, the divisor will have to less than the largest positive integer that the calculator can accurately hold).
An alternative method is, of course, to carry out the division in decimals 4593/7=656.1428571. If you then take this number, subtract 656 and multiply by 7 you obtain remainder 1. This seems simple enough. But what happens if you want to do division on very large numbers? It all starts to get a bit messy and inaccurate, partly because of the number of digits that the fx-50F can accurately hold and partly because only ten digits are displayed on the screen.
For example, Edouard Lucas had shown in 1876 that the number 267-1 =147,573,952,589,676,412,927 is not prime but no one knew what its factors were. In 1903 Frank Nelson Cole (1861-1926) famously gave a presentation to the American Mathematical Society where he proceeded to calculate, in silence, 267-1 on side of the blackboard and then, on the other, the result, by hand, of 193,707,721 × 761,838,257,287. Cole, having demonstrated that the two numbers were equal, sat down, not uttering a word. He received a standing ovation!
What I would like to do is to demonstrate that we can show that either of these factors will divide this number by creating a program that will calculate that the remainder on division is zero. Furthermore, this program will cope with a natural number of any length (though, the divisor will have to less than the largest positive integer that the calculator can accurately hold).
Monday, 5 January 2015
The largest known prime number
The largest known prime as of the 5th January 2015 is the 17,425,170 decimal digit Mersenne prime 257885161-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. M31 can be computed on the fx50F and is the number 231-1=2147483647. We can verify that the last digit is 7 by computing M31 modulo 10. What we actually do is compute 231 (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 231 (mod 10) is congruent to 8 (mod 10). Subtracting 1 (mod 10) from this gives us 7, which is the anticipated last digit of M31.
M127 is the number 2127-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 M57885161? 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 M57885161 (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 257885167-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!
Firstly, though, I will look at some Mersenne primes that we can write down relatively easily. M31 can be computed on the fx50F and is the number 231-1=2147483647. We can verify that the last digit is 7 by computing M31 modulo 10. What we actually do is compute 231 (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 231 (mod 10) is congruent to 8 (mod 10). Subtracting 1 (mod 10) from this gives us 7, which is the anticipated last digit of M31.
M127 is the number 2127-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 M57885161? 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 M57885161 (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 257885167-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!
Monday, 28 April 2014
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 25013 (mod 221). We get m'=133. But if we decrypt m'=133 by working out 133133 (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.
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 25013 (mod 221). We get m'=133. But if we decrypt m'=133 by working out 133133 (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.
Sunday, 27 April 2014
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)=(p1-1)(p2-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 113≡1 (mod 221). The letter l corresponds to 12 and so we need to calculate m'≡1213(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')133 (mod 221) which again you can use the Exponentiation mod n program to do.
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)=(p1-1)(p2-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 113≡1 (mod 221). The letter l corresponds to 12 and so we need to calculate m'≡1213(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')133 (mod 221) which again you can use the Exponentiation mod n program to do.
Saturday, 26 April 2014
RSA Encryption
Having written these four programs for the fx-50F:-
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 p1 and p2 are prime numbers 567451 and 368957 then it is relatively easy to calculate their product p1p2=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.
This is a public key encryption system. The receiver of encrypted messages makes n and e public but keeps p1 and p2 (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.
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 p1 and p2 are prime numbers 567451 and 368957 then it is relatively easy to calculate their product p1p2=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.
- Choose two prime numbers p1 and p2
- Calculate n=p1p2 and φ(n)=(p1-1)(p2-1)
- Choose a positive integer encryption exponent e such that e is less than φ(n) and the gcd(e,φ(n))=1
- Calculate the decryption exponent d which is the inverse of e modulo φ(n), that is ed≡1 (mod φ(n))
- To encrypt a positive integer message m calculate m' where m'≡me (mod n)
- To decrypt message m' calculate m≡(m')d (mod n)
This is a public key encryption system. The receiver of encrypted messages makes n and e public but keeps p1 and p2 (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.
Thursday, 24 April 2014
Exponentiation mod n - execution of the program
In my previous post I detailed a program for finding remainders when a number like 6711 is divided by 41. In my first post I showed that 6711 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 6711 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 67617 is the 1,127 digit number (from WolframAlpha)
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 67617mod 10).
If we didn't know what the number 6711 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 67617 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 67617mod 10).
Wednesday, 23 April 2014
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.
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.
Tuesday, 22 April 2014
Exponentiation mod n - comments on the logic
In my previous post I presented some logic for obtaining the remainder when a number like 6711 is divided by 41. I now want to go through how this logic works.
We are interested in dividing 6711 by 41 and these positive integers are input and stored in X, A and B in the 2nd, 3rd and 4th lines of the logic. The first 'while' loop determines the remainder on dividing 67 by 41 and the result, 26, is stored in X. Essentially, 67 is reduced by 41 on each iteration until X is less than 41. A copy of this remainder (26) is kept in Y.
Memory C holds the current 'squared power'. Memory D is used to store the required calculated remainder and is initialised with 1.
If the input power (stored in A) was 1 rather than 11, then there is no more work to do, so we jump to label 2 and display the result.
The main process of calculating the required remainder by repeated squaring begins after label 1. In our example X currently contains 26 (the remainder on dividing 67 by 41). We square this and then the next 'while' loop obtains the remainder (20) on division by 41 and stores it in X. C is then doubled to 4 and as this is less than 11 we jump back to label 1. We keep on repeating this squaring until C reaches 16. As 16 is greater than 11 we determine that 67 has currently been raised to the power 8 (C divided by 2). We subtract 8 from 11 and store this 'residual' power (3) in A. The calculated remainder 'so far' (18 held in X) is multiplied with D (1) and the result stored in D. We store 26 back in X and set the 'squared power' in C back to 2. As 2 is less than the residual power 3 we begin again by going back to label 1.
Eventually the 'residual power' ends up being 1 in A and we have to take the contents of D and multiply this once more by 26 to get the remainder of 2611 on division by 41. Note that if the power of 67 was even rather than odd, this last step isn't required.
The required remainder is in memory D and this is displayed. There is an option to return to the start of the logic again to enter a different set of numbers.
We are interested in dividing 6711 by 41 and these positive integers are input and stored in X, A and B in the 2nd, 3rd and 4th lines of the logic. The first 'while' loop determines the remainder on dividing 67 by 41 and the result, 26, is stored in X. Essentially, 67 is reduced by 41 on each iteration until X is less than 41. A copy of this remainder (26) is kept in Y.
Memory C holds the current 'squared power'. Memory D is used to store the required calculated remainder and is initialised with 1.
If the input power (stored in A) was 1 rather than 11, then there is no more work to do, so we jump to label 2 and display the result.
The main process of calculating the required remainder by repeated squaring begins after label 1. In our example X currently contains 26 (the remainder on dividing 67 by 41). We square this and then the next 'while' loop obtains the remainder (20) on division by 41 and stores it in X. C is then doubled to 4 and as this is less than 11 we jump back to label 1. We keep on repeating this squaring until C reaches 16. As 16 is greater than 11 we determine that 67 has currently been raised to the power 8 (C divided by 2). We subtract 8 from 11 and store this 'residual' power (3) in A. The calculated remainder 'so far' (18 held in X) is multiplied with D (1) and the result stored in D. We store 26 back in X and set the 'squared power' in C back to 2. As 2 is less than the residual power 3 we begin again by going back to label 1.
Eventually the 'residual power' ends up being 1 in A and we have to take the contents of D and multiply this once more by 26 to get the remainder of 2611 on division by 41. Note that if the power of 67 was even rather than odd, this last step isn't required.
The required remainder is in memory D and this is displayed. There is an option to return to the start of the logic again to enter a different set of numbers.
Exponentiation mod n - the logic
In a previous post I discussed how it is possible to use modular arithmetic to obtain information about the divisibility of a large number like 6711. I showed that the problem of whether 41 divides this number can be reduced to a sequence of manageable chunks by using the method of repeated squaring modulo 41. I now give an example of the logic that can be used to solve this problem on a programmable calculator.
Label 0
Input X (67 in our example)
Input A (11 in our example)
Input B (41 in our example)
While X ≥ B
Store X-B in X
WhileEnd
Store X in Y
Store 2 in C
Store 1 in D
If C>A then
Store X in D
Goto Label 2
EndIf
Label 1
Store X2 in X
While X ≥ B
Store X-B in X
WhileEnd
Store 2C in C
If C ≤A then
Goto Label 1
EndIf
Store C/2 in C
Store A-C in A
Store DX in D
While D ≥ B
Store D-B in D
WhileEnd
Store Y in X
Store 2 in C
If C ≤A then
Goto Label 1
EndIf
If A=1 then
Store DY in D
EndIf
While D ≥ B
Store D-B in D
WhileEnd
Label 2
Display D
Goto Label 0
Label 0
Input X (67 in our example)
Input A (11 in our example)
Input B (41 in our example)
While X ≥ B
Store X-B in X
WhileEnd
Store X in Y
Store 2 in C
Store 1 in D
If C>A then
Store X in D
Goto Label 2
EndIf
Label 1
Store X2 in X
While X ≥ B
Store X-B in X
WhileEnd
Store 2C in C
If C ≤A then
Goto Label 1
EndIf
Store C/2 in C
Store A-C in A
Store DX in D
While D ≥ B
Store D-B in D
WhileEnd
Store Y in X
Store 2 in C
If C ≤A then
Goto Label 1
EndIf
If A=1 then
Store DY in D
EndIf
While D ≥ B
Store D-B in D
WhileEnd
Label 2
Display D
Goto Label 0
Monday, 21 April 2014
Exponentiation mod n
Sometimes it can be hard to obtain information about large numbers because of the complexity of multiplication and division. For example 6711 is the 21 digit number 122130132904968017083 which can't be held accurately in a handheld calculator. If you wanted to determine whether 41 divided this number you would probably have to attempt this by long division. However, modular arithmetic offers a neat way round these problems.
Firstly we determine the remainder when 67 is divided by 41. We find that 67=1x41+26 and so the remainder is 26 and so we can write 67≡26 (mod 41). Now the neat trick of modular arithmetic is that the remainder on dividing 6711 by 41 is the same as the remainder on dividing 2611 by 41. However, rather than doing this in one go, we do it in bite-size chunks using repeated squaring to make the maths easier. So, 672≡262 (mod 41) and since 262 is 676 and 676=16x41+20 then 672≡20 (mod 41). Carrying on in a similar vein we have (672)2=674≡202 (mod 41) and as 202=400=9x41+31 then 674≡31 (mod 41). Further (674)2=678≡312 (mod 41) and as 312=961=23x41+18 then 678≡18 (mod 41).
Squaring any further doesn't help us as the index becomes 2x8=16 which is greater than 11. However as 6711=678x673 we can continue by working out the remainder when 673 is divided by 41 and multiplying this by the remainder when 678 is divided by 41, which we have just worked out. Previously we saw that 672≡20 (mod 41) and 67≡26 (mod 41) and so 673=672x67≡20x26 (mod 41). Now 20x26=520=12x41+28 and so 673≡28 (mod 41). Hence 6711≡18x28=504≡12 (mod 41) since 504=12x41+12.
Thus in answer to our original question 41 doesn't divide 122130132904968017083 as it leaves remainder 12.
This process of reducing a large division into a series of smaller steps using modular arithmetic lends itself well to computation on a programmable calculator. In particular, reducing the index by successive applications of repeated squaring is a fast way to obtain the remainder when a number can be expressed as a number raised to some power.
Firstly we determine the remainder when 67 is divided by 41. We find that 67=1x41+26 and so the remainder is 26 and so we can write 67≡26 (mod 41). Now the neat trick of modular arithmetic is that the remainder on dividing 6711 by 41 is the same as the remainder on dividing 2611 by 41. However, rather than doing this in one go, we do it in bite-size chunks using repeated squaring to make the maths easier. So, 672≡262 (mod 41) and since 262 is 676 and 676=16x41+20 then 672≡20 (mod 41). Carrying on in a similar vein we have (672)2=674≡202 (mod 41) and as 202=400=9x41+31 then 674≡31 (mod 41). Further (674)2=678≡312 (mod 41) and as 312=961=23x41+18 then 678≡18 (mod 41).
Squaring any further doesn't help us as the index becomes 2x8=16 which is greater than 11. However as 6711=678x673 we can continue by working out the remainder when 673 is divided by 41 and multiplying this by the remainder when 678 is divided by 41, which we have just worked out. Previously we saw that 672≡20 (mod 41) and 67≡26 (mod 41) and so 673=672x67≡20x26 (mod 41). Now 20x26=520=12x41+28 and so 673≡28 (mod 41). Hence 6711≡18x28=504≡12 (mod 41) since 504=12x41+12.
Thus in answer to our original question 41 doesn't divide 122130132904968017083 as it leaves remainder 12.
This process of reducing a large division into a series of smaller steps using modular arithmetic lends itself well to computation on a programmable calculator. In particular, reducing the index by successive applications of repeated squaring is a fast way to obtain the remainder when a number can be expressed as a number raised to some power.
Wednesday, 1 May 2013
gcd by subtraction - execution of the program
In a previous post I provided a program for determining the greatest common divisor (gcd) of two positive integers. Trying out this program with 15 and 72, the two numbers that I discussed before, we find that on executing the program the display shows A? Enter 15 and press [EXE]. The display then show B? Enter 72 and press [EXE]. The display then shows 3 and this is the gcd of 15 and 72 as 3 is the largest positive integer that divides these two numbers. Pressing [EXE] again, takes you to the start of the program and this time you can enter 72 first and then 15 and the result is still 3. Note also that if you run the program with two numbers the same, 15 and 15 say, you will get an answer of 15 since obviously 15 is the largest number that divides this same pair of numbers.
This program is quite quick even with larger numbers. For example, running the program with the pair of numbers 8076 and 6378 we find that the gcd is 6. If you were to try and work this out by finding the prime factors of each of the numbers first (8076=22x3x673 and 6378=2x3x1063) it would take quite a bit of time! If the difference between the two numbers is large then the program is a bit slower.
Note also that there aren't any checks in the code to ensure that the numbers entered are positive integers. This can be added if required to make the program more secure. If you do get into an infinite loop (as for example by entering a negative integer) you can just press [AC] to get out of it.
This program is quite quick even with larger numbers. For example, running the program with the pair of numbers 8076 and 6378 we find that the gcd is 6. If you were to try and work this out by finding the prime factors of each of the numbers first (8076=22x3x673 and 6378=2x3x1063) it would take quite a bit of time! If the difference between the two numbers is large then the program is a bit slower.
Note also that there aren't any checks in the code to ensure that the numbers entered are positive integers. This can be added if required to make the program more secure. If you do get into an infinite loop (as for example by entering a negative integer) you can just press [AC] to get out of it.
Tuesday, 23 April 2013
gcd by subtraction - 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:?→A:?→B:A=B=>Goto 2:If B>A:Then A→X:B→A:X→B:IfEnd:
Lbl 1:A-B→C:B→X:If X>C:Then B→A:C→B:Else C→A:IfEnd:A≠B=>Goto 1:Lbl 2:A▲Goto 0:
This program is 87 steps in length.
Lbl 0:?→A:?→B:A=B=>Goto 2:If B>A:Then A→X:B→A:X→B:IfEnd:
Lbl 1:A-B→C:B→X:If X>C:Then B→A:C→B:Else C→A:IfEnd:A≠B=>Goto 1:Lbl 2:A▲Goto 0:
This program is 87 steps in length.
Sunday, 16 December 2012
gcd by subtraction - the logic
I previously described how it is possible to find the greatest common divisor of two natural numbers by using Euclid's subtraction algorithm. The logic for that algorithm is as follows:-
Label 0
Input A
Input B
If A = B then
Goto Label 2
EndIf
If B>A then
Store A in X
Store B in A
Store X in B
EndIf
Label 1
Store A-B in C
Store B in X
If X>C then
Store B in A
Store C in B
Else
Store C in A
EndIf
If A is not equal to B then
Goto Label 1
EndIf
Label 2
Display A
Goto Label 0
This processing carries out the following. The two numbers whose gcd is sought are input as A and B. If A equals B then the gcd(A,B) is simply A (or B) and there is no more work to be done. If B is greater than A, then we swap the values of A and B. Euclid's subtraction algorithm then begins after Label 1. We calculate A-B. If B is greater than A-B then we store B in A and A-B in B otherwise B remains unchanged and we store A-B in A. We repeat the process until A equals B and then we display A and stop the processing. After A is displayed, we then have the otption of returning to the beginning to process another pair of numbers.
Label 0
Input A
Input B
If A = B then
Goto Label 2
EndIf
If B>A then
Store A in X
Store B in A
Store X in B
EndIf
Label 1
Store A-B in C
Store B in X
If X>C then
Store B in A
Store C in B
Else
Store C in A
EndIf
If A is not equal to B then
Goto Label 1
EndIf
Label 2
Display A
Goto Label 0
This processing carries out the following. The two numbers whose gcd is sought are input as A and B. If A equals B then the gcd(A,B) is simply A (or B) and there is no more work to be done. If B is greater than A, then we swap the values of A and B. Euclid's subtraction algorithm then begins after Label 1. We calculate A-B. If B is greater than A-B then we store B in A and A-B in B otherwise B remains unchanged and we store A-B in A. We repeat the process until A equals B and then we display A and stop the processing. After A is displayed, we then have the otption of returning to the beginning to process another pair of numbers.
Tuesday, 11 December 2012
gcd by subtraction
The greatest common divisor (gcd) of two natural numbers is the largest natural number that divides both. For example, the gcd of 72 and 15 is 3 since 3 is the largest number that divides both 72 and 15. We can see this more clearly if determine the prime factors of these two numbers. We have that 72=8x9=2x2x2x3x3 and 15=3x5 and we have only one prime factor, 3, that is common to both.
Euclid came up with a very neat algorithm for finding the gcd of two numbers that is based on subtraction and this algorithm is easy to implement on the fx-50F. Using the above example of 72 and 15 above, the method goes as follows.
Our first pair of numbers is (72, 15) and in each pair we want the first entry to be the larger of the two numbers. To form the next pair we subtract 15 from 72 to give 57 and form the pair (57, 15). We carry on in a similar way obtaining (42,15) and (27, 15). Then subtracting 15 from 27 we get 12 and this is smaller than 15, so they next pair is (15, 12). Then 15 minus 12 is 3 and so we get (12,3), then (9,3), then (6,3) and finally (3,3). When the two pairs of numbers are equal then either number is the gcd of 72 and 15, as we found out above.
I have described the method in more detail in my maths blog.
Euclid came up with a very neat algorithm for finding the gcd of two numbers that is based on subtraction and this algorithm is easy to implement on the fx-50F. Using the above example of 72 and 15 above, the method goes as follows.
Our first pair of numbers is (72, 15) and in each pair we want the first entry to be the larger of the two numbers. To form the next pair we subtract 15 from 72 to give 57 and form the pair (57, 15). We carry on in a similar way obtaining (42,15) and (27, 15). Then subtracting 15 from 27 we get 12 and this is smaller than 15, so they next pair is (15, 12). Then 15 minus 12 is 3 and so we get (12,3), then (9,3), then (6,3) and finally (3,3). When the two pairs of numbers are equal then either number is the gcd of 72 and 15, as we found out above.
I have described the method in more detail in my maths blog.
Subscribe to:
Posts (Atom)