Friday, June 24, 2016
RSA Encryption
RSA Encryption has been with us since 1987 securing our commercial transactions so that no one steals our private information and thus protects our bank accounts, our ICBM missiles tipped with nuclear warheads pointed at each other (be sure and see the movie: War Games - with Matthew Broderick, from the 1980s), and a whole bunch of other secrets we find so precious to keep in today's world.
Needless to say, I'm not a big fan of this scheme. I'd rather be poor (I am already, having lost my son to extreme honesty), then to have several nuclear warheads pointed at me and elsewhere. Without secrets, where would we be?
The first step in defrocking these secrets is to familiarize our self with how some of the more simpler encryption schemes operate. To this end, I present to you this description I gleaned from watching the following video on YouTube...
To aid us in studying his presentation, I have collected a few slides acting as reminders of Jordan's main points. Here is the first slide to help us encode and decode a secret message, "Hi"...
To help us understand the mechanics of how this encryption/decryption can actually happen, I've prepared a demonstration in JavaScript which is capable of performing all of the calculations on a scale small enough for it to handle, but not large enough to actually be secure...
All's well, that ends well....
Needless to say, I'm not a big fan of this scheme. I'd rather be poor (I am already, having lost my son to extreme honesty), then to have several nuclear warheads pointed at me and elsewhere. Without secrets, where would we be?
The first step in defrocking these secrets is to familiarize our self with how some of the more simpler encryption schemes operate. To this end, I present to you this description I gleaned from watching the following video on YouTube...
To aid us in studying his presentation, I have collected a few slides acting as reminders of Jordan's main points. Here is the first slide to help us encode and decode a secret message, "Hi"...
All's well, that ends well....
Tuesday, June 21, 2016
The Euclidean Algorithm in Expanded Format
The Euclidean Algorithm for finding the Greatest Common Denominator has always been a linear phenomenon repetitively subtracting the smaller - of a pair of integers - from the larger until a non-negative remainder smaller than the original subtrahend results. With each repetition, the remainder replaces the former subtrahend. This replacement scheme is what makes this style of computation a linear style incapable of breaking out of its limited view of the Golden Number series upon which it is built. This is not surprising, since the protocol for incrementing the Fibonacci series (of: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, etc upon which it is built) is also a linear phenomenon of adding the last number in the series with the integer immediately preceding it. So, the next number after 89 is found by adding it to 55 resulting in 144. To break out of this narrow definition of both Golden Numbers and the Euclidean Algorithm - with no offense intended toward Master Euclid, we must think in terms of a tablature of integers and take an integrated approach towards their computation. Let's begin with the Fibonacci series....
Instead of defining the Fibonacci series in terms of a series of integers, let's assume two series which increment in parallel with each other. It just so happens that these two parallel series are copies of each other but offset by one position. This is probably why we ignore their uniqueness and assume, for all intents and purposes, that there is only one series of numbers.
So, series 'a' got a head start over series 'b'. Now, how do we approximate the Golden Ratios of 1.618 and 0.618? Do we use the traditional method of dividing the smaller integer, among two neighboring integers, with its larger neighbor to its right? Or, do we integrate these two parallel series by dividing 'b' into 'a' for one ratio and 'a' into 'b' for another? Let's inspect the following regular pentagon of equal sides and equal angles (each angle is 108°)...
The answer is, yes we do integrate these two parallel series of integers, but it's not entirely obvious that there isn't only one series. For that premise to my hypothesis, we'll have to wait a little bit.
This Fibonacci series produces two roots, 1.618 and −0.618, which satisfy the following polynomial...
X2 − X1 − 1 = 0
Now, we'll move on to the next order of Phi, whose ratios satisfy a third-order polynomial in one unknown, also known as a cubic polynomial.
Now, we can approximate the three Golden Ratios of this 3rd order Fibonacci series by taking the following proportionate approximations among the diagonals of 'a', 'b', and 'c' of this regular septagon, or seven-sided polygon....
This progressive convergence upon a more accurate approximation results in the following three proportions...
It's four ratios can be found among the following diagonals of a nonagon, or nine-sided, regular polygon...
This progressive convergence upon a more accurate approximation results in the following three proportions...
R1 = a/c = 2.24697960372
R2 = b/a = −0.801937735805
R3 = c/b = 0.554958132087
R2 = b/a = −0.801937735805
R3 = c/b = 0.554958132087
...which satisfy the following polynomial...
X3 − 2X2 − X1 + 1 = 0
Moving on to the fourth order of Golden Series...
It's four approximate roots of a fifth order polynomial in one unknown are...
X1 = a/d = 2.87938524157
X2 = b/b = 1
X3 = c/a = 0.652703644666
X4 = d/c = 0.532088886238
X2 = b/b = 1
X3 = c/a = 0.652703644666
X4 = d/c = 0.532088886238
To be able to make a 4th order polynomial in one unknown out of these four numbers will require that two of them are given a negative sign value:
−1 and
−0.532088886238
We can form this polynomial by multiplying these four values together.
But first, we have to turn them into linear expressions in one
unknown...
X1 = 2.87938524157
Subtract 2.87938524157 from both sides of the equal sign...
X1 − 2.87938524157 = 2.87938524157 − 2.87938524157
Yields...
(X − 2.87938524157) = 0
X2 = −1
Add 1 to both sides of the equal sign...
X2 + 1 = −1 + 1
Yields...
(X + 1) = 0
X3 = 0.652703644666
Subtract 0.652703644666 from both sides of the equal sign...
X3 − 0.652703644666 = 0.652703644666 − 0.652703644666
Yields...
(X − 0.652703644666) = 0
X4 = −0.532088886238
Add 0.532088886238 to both sides of the equal sign...
X4 + 0.532088886238 = −0.532088886238 + 0.532088886238
Yields...
(X + 0.532088886238) = 0
Multiplying these four roots together...
(X − 2.87938524157) × (X + 1) × (X − 0.652703644666) × (X + 0.532088886238) = 0
Yields...
X4 − 2.87938524157X3 + 1X3 − 0.652703644666X3 + 0.532088886238X3 − 2.87938524157X2 + 1.87938524157X2 − 1.53208888624X2 − 0.652703644666X2 + 0.532088886238X2 − 0.347296355334X2 + 1.87938524157X1 − 1.53208888624X1 + 1X1 − 0.347296355334X1 + 1 = 0
Simplifying further, yields a 4th order polynomial in one unknown...
X1 = 2.87938524157
Subtract 2.87938524157 from both sides of the equal sign...
X1 − 2.87938524157 = 2.87938524157 − 2.87938524157
Yields...
(X − 2.87938524157) = 0
X2 = −1
Add 1 to both sides of the equal sign...
X2 + 1 = −1 + 1
Yields...
(X + 1) = 0
X3 = 0.652703644666
Subtract 0.652703644666 from both sides of the equal sign...
X3 − 0.652703644666 = 0.652703644666 − 0.652703644666
Yields...
(X − 0.652703644666) = 0
X4 = −0.532088886238
Add 0.532088886238 to both sides of the equal sign...
X4 + 0.532088886238 = −0.532088886238 + 0.532088886238
Yields...
(X + 0.532088886238) = 0
Multiplying these four roots together...
(X − 2.87938524157) × (X + 1) × (X − 0.652703644666) × (X + 0.532088886238) = 0
Yields...
X4 − 2.87938524157X3 + 1X3 − 0.652703644666X3 + 0.532088886238X3 − 2.87938524157X2 + 1.87938524157X2 − 1.53208888624X2 − 0.652703644666X2 + 0.532088886238X2 − 0.347296355334X2 + 1.87938524157X1 − 1.53208888624X1 + 1X1 − 0.347296355334X1 + 1 = 0
Simplifying further, yields a 4th order polynomial in one unknown...
X4 − 2X3 − 3X2 − X1 + 1 = 0
I hope these few examples have convinced you of a progressive tendency towards repeating a basic pattern to a higher and higher degree of Golden Ratios?
I'm going to move on, now, to explain how my expanded hypothesis of the Euclidean Algorithm is deduced from these prior examples...
Let's begin with the first diagram...
If we were to take the last two numbers in column 11, namely: 144 and 89, we could take the Greatest Common Divisor of these two integers, couldn't we? But how would the operation look the traditional way?
144 ÷ 89 = 1, with 55 remaining.
89 ÷ 55 = 1, with 34 remaining.
55 ÷ 34 = 1, with 21 remaining.
34 ÷ 21 = 1, with 13 remaining.
21 ÷ 13 = 1, with 8 remaining.
13 ÷ 8 = 1, with 5 remaining.
8 ÷ 5 = 1, with 3 remaining.
5 ÷ 3 = 1, with 2 remaining.
3 ÷ 2 = 1, with 1 remaining.
2 ÷ 1 = 2, with 0 remaining.
1 is the Greatest Common Divisor of 144 and 89.
Nobody would want to complicate this simple approach. It's so elegant as it is. But we'll have to in order to prepare ourselves for its subsequent expansion to higher ordered Golden Series of Numbers. Actually, we should have used the modulo operator, rather than division, since we're ignoring the quotient and only paying attention to the remainder...
144 % 89 = 1, with 55 remaining.
89 % 55 = 1, with 34 remaining.
55 % 34 = 1, with 21 remaining.
34 % 21 = 1, with 13 remaining.
21 % 13 = 1, with 8 remaining.
13 % 8 = 1, with 5 remaining.
8 % 5 = 1, with 3 remaining.
5 % 3 = 1, with 2 remaining.
3 % 2 = 1, with 1 remaining.
2 % 1 = 2, with 0 remaining.
1 is the Greatest Common Divisor of 144 and 89.
Here's a demonstration of Euclid's Algorithm from YouTube done in the usual way...
Now it's time for my method...
Now it's time for my method...
two integers | 144 | 89 |
---|---|---|
sort from left to right | 89 | 144 |
shift to the right | * | 89 |
replace * with a zero | 0 | 89 |
stack the two rows of integers,
the 'sort' on top of 'replace', and take their modulo | 89
%0 89 | 144
%89 55 |
sort from left to right | 55 | 89 |
shift to the right | * | 55 |
replace * with a zero | 0 | 55 |
stack the two rows of integers,
the 'sort' on top of 'replace', and take their modulo | 55
%0 55 | 89
%55 34 |
sort from left to right | 34 | 55 |
shift to the right | * | 34 |
replace * with a zero | 0 | 34 |
stack the two rows of integers,
the 'sort' on top of 'replace', and take their modulo | 34
%0 34 | 55
%34 21 |
sort from left to right | 21 | 34 |
shift to the right | * | 21 |
replace * with a zero | 0 | 21 |
stack the two rows of integers,
the 'sort' on top of 'replace', and take their modulo | 21
%0 21 | 34
%21 13 |
sort from left to right | 13 | 21 |
shift to the right | * | 13 |
replace * with a zero | 0 | 13 |
stack the two rows of integers,
the 'sort' on top of 'replace', and take their modulo | 13
%0 13 | 21
%13 8 |
sort from left to right | 8 | 13 |
shift to the right | * | 8 |
replace * with a zero | 0 | 8 |
stack the two rows of integers,
the 'sort' on top of 'replace', and take their modulo | 8
%0 8 | 13
%8 5 |
sort from left to right | 5 | 8 |
shift to the right | * | 5 |
replace * with a zero | 0 | 5 |
stack the two rows of integers,
the 'sort' on top of 'replace', and take their modulo | 5
%0 5 | 8
%5 3 |
sort from left to right | 3 | 5 |
shift to the right | * | 3 |
replace * with a zero | 0 | 3 |
stack the two rows of integers,
the 'sort' on top of 'replace', and take their modulo | 3
%0 3 | 5
%3 2 |
sort from left to right | 2 | 3 |
shift to the right | * | 2 |
replace * with a zero | 0 | 2 |
stack the two rows of integers,
the 'sort' on top of 'replace', and take their modulo | 2
%0 2 | 3
%2 1 |
sort from left to right | 1 | 2 |
shift to the right | * | 1 |
replace * with a zero | 0 | 1 |
stack the two rows of integers,
the 'sort' on top of 'replace', and take their modulo | 1
%0 1 | 2
%1 0 |
1 is the Greatest Common Divisor of 144 and 89.
I call this process unzipping, because I'm reducing 144 and 89 in the same manner that created them in the first place...
By analyzing the manner in which these golden numbers zip themselves up and unzip themselves back down, we see that they have a very unique identity in that their collective quotients are always 1 and their remainders yield the prior set of Fibonacci numbers. Try and do that with non-Golden numbers!
We'll move on to the cubic order of Golden Numbers and see this same pattern repeat itself. And since the standardized, conventional method of performing the Euclidean Algorithm won't apply to this scenario, I must dispense with it and use my own...
Summary,
It can be said of Golden Numbers, of any degree Golden Polynomial for which their Golden Ratios are the solutions, that their unique property is that they close themselves. Only a Golden Number can be added to another Golden Number, from the same set, to build up a Golden Series. And only a Golden Number from the same set can be subtracted from another Golden Number to produce another smaller Golden Number from the same set.
It must also be emphasized that division is not occuring here, only repetitive subtraction, since we're not interested in the quotient – we're only interested in the remainder. Since the modulo operator is equivalent to repetitive subtraction, we use it to reduce integers during performance of the Euclidean Algorithm.
But we're engaging a special case, here, of using only Golden Numbers – not any integer – in the performance of the Euclidean Algorithm to find the Greatest Common Divisor among them. So, we need not utilize the services of the modulo operator. We may replace it with subtraction since we'll only be performing repetitive subtraction once yielding a quotient of one.
1 is the Greatest Common Divisor of 636, 793 and 353.
In conclusion,
The study of the Infinite Range of Golden Ratios, and the Golden Numbers which spawn them, yields a fuller appreciation for the Euclidean Algorithm and a more efficient method for discovering the Greatest Common Divisor among any quantity of integers.
Here are some JavaScripts to bring my method to life! This first one generates a few integers at random and multiplies them against another small integer to find their Greatest Common Divisor.
We'll move on to the cubic order of Golden Numbers and see this same pattern repeat itself. And since the standardized, conventional method of performing the Euclidean Algorithm won't apply to this scenario, I must dispense with it and use my own...
Summary,
It can be said of Golden Numbers, of any degree Golden Polynomial for which their Golden Ratios are the solutions, that their unique property is that they close themselves. Only a Golden Number can be added to another Golden Number, from the same set, to build up a Golden Series. And only a Golden Number from the same set can be subtracted from another Golden Number to produce another smaller Golden Number from the same set.
It must also be emphasized that division is not occuring here, only repetitive subtraction, since we're not interested in the quotient – we're only interested in the remainder. Since the modulo operator is equivalent to repetitive subtraction, we use it to reduce integers during performance of the Euclidean Algorithm.
But we're engaging a special case, here, of using only Golden Numbers – not any integer – in the performance of the Euclidean Algorithm to find the Greatest Common Divisor among them. So, we need not utilize the services of the modulo operator. We may replace it with subtraction since we'll only be performing repetitive subtraction once yielding a quotient of one.
three integers | 636 | 793 | 353 |
---|---|---|---|
sort from left to right | 353 | 636 | 793 |
shift to the right | * | 353 | 636 |
replace * with a zero | 0 | 353 | 636 |
stack the two rows of integers,
the 'sort' on top of 'replace', and perform subtraction | 353
− 0 353 | 636
−353 283 | 793
−636 157 |
sort from left to right | 157 | 283 | 353 |
shift to the right | * | 157 | 283 |
replace * with a zero | 0 | 157 | 283 |
stack the two rows of integers,
the 'sort' on top of 'replace', and perform subtraction | 157
− 0 157 | 283
−157 126 | 353
−283 70 |
sort from left to right | 70 | 126 | 157 |
shift to the right | * | 70 | 126 |
replace * with a zero | 0 | 70 | 126 |
stack the two rows of integers,
the 'sort' on top of 'replace', and perform subtraction | 70
− 0 70 | 126
− 70 56 | 157
−126 31 |
sort from left to right | 31 | 56 | 70 |
shift to the right | * | 31 | 56 |
replace * with a zero | 0 | 31 | 56 |
stack the two rows of integers,
the 'sort' on top of 'replace', and perform subtraction | 31
− 0 31 | 56
− 31 25 | 70
− 56 14 |
sort from left to right | 14 | 25 | 31 |
shift to the right | * | 14 | 25 |
replace * with a zero | 0 | 14 | 25 |
stack the two rows of integers,
the 'sort' on top of 'replace', and perform subtraction | 14
− 0 14 | 25
− 14 11 | 31
− 25 6 |
sort from left to right | 6 | 11 | 14 |
shift to the right | * | 6 | 11 |
replace * with a zero | 0 | 6 | 11 |
stack the two rows of integers,
the 'sort' on top of 'replace', and perform subtraction | 6
− 0 6 | 11
− 6 5 | 14
− 11 3 |
sort from left to right | 3 | 5 | 6 |
shift to the right | * | 3 | 5 |
replace * with a zero | 0 | 3 | 5 |
stack the two rows of integers,
the 'sort' on top of 'replace', and perform subtraction | 3
− 0 3 | 5
− 3 2 | 6
− 5 1 |
sort from left to right | 1 | 2 | 3 |
shift to the right | * | 1 | 2 |
replace * with a zero | 0 | 1 | 2 |
stack the two rows of integers,
the 'sort' on top of 'replace', and perform subtraction | 1
− 0 1 | 2
− 1 1 | 3
− 2 1 |
sort from left to right | 1 | 1 | 1 |
shift to the right | * | 1 | 1 |
replace * with a zero | 0 | 1 | 1 |
stack the two rows of integers,
the 'sort' on top of 'replace', and perform subtraction | 1
− 0 1 | 1
− 1 0 | 1
− 1 0 |
In conclusion,
The study of the Infinite Range of Golden Ratios, and the Golden Numbers which spawn them, yields a fuller appreciation for the Euclidean Algorithm and a more efficient method for discovering the Greatest Common Divisor among any quantity of integers.
Here are some JavaScripts to bring my method to life! This first one generates a few integers at random and multiplies them against another small integer to find their Greatest Common Divisor.
This next JavaScript will accept any quantity of non-zero integers so long as they are not equal each other...
Thursday, June 2, 2016
Introduction to the Infinite Range of Golden Ratio
Unbeknownst to all mathematicians, the Golden Ratio is infinite in scope
Introduction to the Infinite Range of Golden Ratio
Introduction to the Infinite Range of Golden Ratio
Saturday, April 21, 2012
A Few References...
- The Irrationality of the Pentagon and the Pentagram, by Michael Lahanas
Subscribe to:
Posts (Atom)