A few days ago I took the plunge and finally saw "The Imitation Game", a Hollywood movie that is supposed to be about the mathematicians who broke The Enigma, which the German military used to communicate with evil axis troops during WWII.
The movie was loosely based on a biographical novel called The Enigma about one of these Mathematicians: an Englishman named Alan Turing, who is also known as the father of artificial intelligence, and the father of computing in general.
In a true Hollywood manner, the movie gave all credits for the breaking of the Enigma to the English Mathematicians without mentioning the enormous accomplishment of the Polish Mathematician Marian Rejewski.
Marian Rejewski was the first person to apply Pure Mathematics to cryptanalysis according to Simon Singh's The Code Book. In this sense Marian Rejewski is the father of mathematical cryptanalysis.
For centuries before Marian Rejewski, the most reliable way of breaking an encrypted text was by analyzing the frequency of the occurrence of certain letters in the encrypted texts and comparing these to the most frequently occurring letters in plain texts, which was a purely linguistic approach.
The purely linguistic approach did not work when it was applied to messages encrypted with the Enigma, and this gave the Germans a head start in the war. The Enigma was deemed unbreakable.
Marian Rejewski applied a fairly new-ish branch of Mathematics to decipher messages composed through the Enigma. This branch of Mathematics, namely Group Theory, is still used today in cryptography and cryptanalysis, and in particular, Group Theory is at the heart of the RSA problem.
The main goal of Group Theory, as I was once told by a prominent researcher, is to classify the various different types of mathematical structures called groups, and the field itself is highly abstract so applying results from it to real life problems back then was rather revolutionary.
In other words, Marian Rejewski was a creative genius who risked his own life to save the lives of others. When Germany took over Poland he went to France and brought his work with him, and when Germany took over France, he fled to Britain and gave his work to the British Intelligence, who passed it on to The Bletchley Park crew.
After the war Rejewski returned to the family that he left in order to save the families of others and worked in sales.
Apparently, cryptanalysis is a lonely, ungrateful field especially for those cryptanalysts who are not from the right kind of a background.
25.12.15
19.12.15
A Few More Observations
The following is a continuation of the post A Few Observations that I wrote a few weeks ago.
Claim 4: The elements [1^{2}, 2^{2}, 3^{2}, ..., ((n-1)/2)^{2}] mod n when n is the product of two distinct odd primes p and q can be generated using the following relation:
If a_{i} = 0 then all elements [1^{2}, 2^{2}, 3^{2}, ..., ((n-1)/2)^{2 }mod n] have been generated
Example: n = 35 so a_{0} = ((35-1)/2)^{2} mod 35 = 9 then
a_{1} = a_{0} + 2*1 mod 35 = 9 + 2 = 11,
a_{2} = a_{1} + 2*2 mod 35 = 11 + 4 = 15,
a_{3} = 15 + 2*3 mod 35 = 21,
a_{4} = 21 + 2*4 mod 35 = 29,
a_{5} = 29 + 2*5 mod 35 = 4,
a_{6} = 4 + 2*6 mod 35 = 16,
a_{7} = 16 + 14 mod 35 = 30,
a_{8} = 30 + 16 mod 35 = 11,
a_{9} = 11 + 18 mod 35 = 29,
a_{10} = 29 + 20 mod 35 = 14.
a_{11} = 14 + 22 mod 35 = 1,
a_{12} = 1 + 24 mod 35 = 25,
a_{13} = 25 + 26 mod 35 = 16,
a_{14} = 16 + 28 mod 35 = 9,
a_{15} = 9 + 30 mod 35 = 4,
a_{16} = 4 + 32 mod 35 = 1,
a_{17} = 1 + 34 mod 35 = 0
Note: In this example the set [a_{0}, a_{1}, a_{2}, a_{3}, ..., a_{16]} is equivalent to the set [18^{2} mod 35,19^{2} mod 35, 20^{2} mod 35, 21^{2} mod 35 ..., 34^{2} mod 35], or the set [17^{2} mod 35, 16^{2} mod 35, 15^{2} mod 35, 14^{2} mod 35 ..., 1^{2} mod 35], which is the inverse of the first half of the column at 2 in the exponentiation table of Z_{35} w. In general, if Corollary 2 described here is true then this is the case for all n in Z where n is the product of two distinct odd primes.
Claim 5: There is an element a < (n-1)/2 in Z_{n} where n is the product of two distinct odd primes p and q such that:
Claim 4: The elements [1^{2}, 2^{2}, 3^{2}, ..., ((n-1)/2)^{2}] mod n when n is the product of two distinct odd primes p and q can be generated using the following relation:
a_{0} = ((n-1)/2)^{2} mod n
a_{1} = (a_{0} + 2*1) mod n
a_{2} = (a_{1} + 2*2) mod n
a_{3} = (a_{3} + 2*3) mod n
.
.
.
a_{i} = (a_{i-1} + 2*i) mod n
If a_{i} = 0 then all elements [1^{2}, 2^{2}, 3^{2}, ..., ((n-1)/2)^{2 }mod n] have been generated
Example: n = 35 so a_{0} = ((35-1)/2)^{2} mod 35 = 9 then
a_{1} = a_{0} + 2*1 mod 35 = 9 + 2 = 11,
a_{2} = a_{1} + 2*2 mod 35 = 11 + 4 = 15,
a_{3} = 15 + 2*3 mod 35 = 21,
a_{4} = 21 + 2*4 mod 35 = 29,
a_{5} = 29 + 2*5 mod 35 = 4,
a_{6} = 4 + 2*6 mod 35 = 16,
a_{7} = 16 + 14 mod 35 = 30,
a_{8} = 30 + 16 mod 35 = 11,
a_{9} = 11 + 18 mod 35 = 29,
a_{10} = 29 + 20 mod 35 = 14.
a_{11} = 14 + 22 mod 35 = 1,
a_{12} = 1 + 24 mod 35 = 25,
a_{13} = 25 + 26 mod 35 = 16,
a_{14} = 16 + 28 mod 35 = 9,
a_{15} = 9 + 30 mod 35 = 4,
a_{16} = 4 + 32 mod 35 = 1,
a_{17} = 1 + 34 mod 35 = 0
Claim 5: There is an element a < (n-1)/2 in Z_{n} where n is the product of two distinct odd primes p and q such that:
a^{2 }= a mod n and a is either equal to p or q, or a is a small multiple of p or q
Example:
i) n = 35 a = 15 since 15^{2 }= 15 mod 35
ii) n = 77 a = 22 since 22^{2 }= 22 mod 35
iii) n = 55 a = 11 since 11^{2 }= 11 mod 35
cur = (n-1)/2;
squared = (((n-1)/2)*((n-1)/2))%n;
while( squared != cur && squared != 0)
{
index = index + 1;
squared = (squared + 2*index)%n;
cur = cur - 1;
}
return squared;
}
These two claims can be combined in the following function:
a_equal_to_a_squared_mod(n)
{
index = 0;cur = (n-1)/2;
squared = (((n-1)/2)*((n-1)/2))%n;
while( squared != cur && squared != 0)
{
index = index + 1;
squared = (squared + 2*index)%n;
cur = cur - 1;
}
return squared;
}
//WARNING! Writing functions based on unproven claims may lead to restless nights and infinite loops.
The implementation in Javascript of the above function is iFramed below.
Labels:
Abstract Algebra
,
exponent
,
Mathematics
,
RSA Problem
10.12.15
12.11.15
A Few Observations
So far I've proven most of the claims I made in the Mathematics section of this blog, and the most important claim I made was independently proven by a Group Theory researcher as well after a Computing Science researcher scoffed at it.
However, there are a few very important results that I have not yet been able to prove or disprove. I already talked about one such claim here. And here are some of the other ones that are closely related to the one in the Exponentiation Tables From Another Perspective post:
Claim 2: The order of 2 mod n is equal to the order of (((n-1)/2) + 1) mod n. In other words, if
Corollary 1: The row at (((n-1)/2) + 1) of the exponentiation table of Z_{n} is equivalent to the row at 2 in reverse order
Corollary 2: The row at (((n-1)/2) + 1) of the exponentiation table of Z_{n} can be generated using the following recurrence relation:
Claim 3: The order of (n-1)/2 mod n is equal to the order of (n-2) mod n. In other words, if
However, there are a few very important results that I have not yet been able to prove or disprove. I already talked about one such claim here. And here are some of the other ones that are closely related to the one in the Exponentiation Tables From Another Perspective post:
Claim 2: The order of 2 mod n is equal to the order of (((n-1)/2) + 1) mod n. In other words, if
2^{a }≡ 1 mod n and a is the smallest such integer then:
(((n-1)/2) + 1)^{b }≡ 1 mod n and b is the smallest such integer
Then a = b
Corollary 1: The row at (((n-1)/2) + 1) of the exponentiation table of Z_{n} is equivalent to the row at 2 in reverse order
Corollary 2: The row at (((n-1)/2) + 1) of the exponentiation table of Z_{n} can be generated using the following recurrence relation:
a_{n} = (a_{(n-1)})/2 mod n
Claim 3: The order of (n-1)/2 mod n is equal to the order of (n-2) mod n. In other words, if
((n-1)/2)^{k} ≡ 1 mod n and k is the smallest such integer then:
(n-2)^{k} ≡ 1 mod n and k is the smallest such integer
Corollary 3: The row at (n-1)/2 of the exponentiation table of Z_{n} is equivalent to the row at (n-2) in reverse order.
Corollary 4: The row at (n-1)/2 of the exponentiation table of Z_{n} is can be generated from the row at (((n-1)/2) + 1 in the following manner:
Let a_{i} be an element at the row of (((n-1)/2) + 1 and let b_{i} be an element at the row of (n-1)/2 then:
Corollary 4: The row at (n-1)/2 of the exponentiation table of Z_{n} is can be generated from the row at (((n-1)/2) + 1 in the following manner:
Let a_{i} be an element at the row of (((n-1)/2) + 1 and let b_{i} be an element at the row of (n-1)/2 then:
b_{i} = a_{i} if i is even
b_{i} = a_{i} - a_{i-1} if i is odd
Example: Take Z_{35} for example. Then n = 35 and (((n-1)/2) = 17 and (((n-1)/2) + 1 = 18. Below are the row at 17 and 18 of the exponentiation table of Z_{35} .
The row at 18 can be generated by dividing each element by 2 mod n. The Euclidean algorithm can be used to compute each term since dividing by 2 in modular arithmetic requires solving the following equation for x:
The row at 18 can be generated by dividing each element by 2 mod n. The Euclidean algorithm can be used to compute each term since dividing by 2 in modular arithmetic requires solving the following equation for x:
a ≡ 2x mod n
In other words, 9 ≡ 2*22 mod 35, 22 ≡ 2*11 mod 35, 11 ≡ 2*23 mod 35 and so on
The row at 17 then can be generated entirely from the row at 18 by subtracting the previous element from the current one if the index is odd and by repeating the same integer if the index is even.
In other words, 17^2 mod 35 is simply equal to 18^2 = 18/2 mod n;
Since 18^2 = 18/2 = 9 mod n and 18^3 = 9/2 = 22 mod n then 17^3 mod n = 22 - 9 = 13
17^4 = 18^4 = (18^3)/2 = 11
and so on.
Remarks: In the full exponentiation table of Z_{35} the row at 18 is the row at 2 in reverse order and the row at 17 is the row at 33 in reverse order and this is the case for all exponentiation tables I've looked at so far.
All of these claims have been tested out with a few different integers and so far I've found no counter example.
Labels:
exponent
,
Mathematics
,
Order of An Element
,
RSA Problem
25.10.15
The RSA Problem
Back in university I stumbled upon a problem that sparked my curiosity, which lead to the Mathematics section of this blog. The problem was a part of my last assignment for one of my favourite Computing Science classes. Here's the problem:
Bob wants to send Alice a secret message using the RSA encryption algorithm. Bob's message m is 88 and he encrypts it using Alice's public key, which is (n, e) = (4699, 1171), to obtain a ciphertext c. If the ciphertext is c = 3908, then what is Bob's message m?
The plaintext can be obtained by obtaining Alice's private key, which is easy to obtain because it is possible to factor 4699 in polynomial time to find phi(n). Let's assume though that only Alice knows the two primes p and q that 4699 is made of and 4699 can't be factored in polynomial time.
Alice 's private key d₁ can be computed using phi(n)
Alice computes phi(n) = phi(p)*phi(q) = (127-1)*(37-1) = 4536
Alice's private key d₁ is ed₁ ≡ 1 mod 4536 which is 1171d₁ ≡ 1 mod 4536
because 1171d₁ + 4536y₁ = 1 for some d₁, y₁ in Z
=> d₁ = 1747 because 1171*1747+4536*(-451) = 1 in Z
Since c = 3908 then m ≡ 3908¹⁷⁴⁷ mod 4699 ≡ 88 mod 4699
This was the answer that the TA was expecting to see, which is why he was blown away when he saw this instead:
Eve computes a private key d₂ by overcounting exactly 3 times
d₂ = 235 because 1171*235+3276*(-84) = 1 in Z
Since c = 3908 then m ≡ 3908²³⁵ mod 4699 ≡ 88 mod 4699
The second key d₂ is a number that's 7 times less than the TA's key! As far as the TA was concerned there is only one decryption key, namely d₁ = 1747, and he naturally had a marking meltdown on my assignment.
But there are even more keys that decrypt the cipher text. For example, 504, 546, 702, 756 also decrypt the message in this example and so a pattern emerges. It can be verified that all combinations of 2Ê³ x 3Ë¢ x 7áµ— , 2Ê³ x 3Ë¢ x 13áµ˜, 2Ê³ x 3Ë¢ x 7áµ— x 13áµ˜ where 0 < r, s, t < 5 and u = 1 among others produce private keys, which can be used to decrypt the ciphertext c in this example even though these keys are not the same as the one generated with phi(n).
Generally speaking, when n is the product of 2 distinct odd primes, then there will always be at least 1 extra private key, other than the private key generated using phi(n)
So how can one find d₂, or rather, how can one find the other keys that decrypt c?'
Bob wants to send Alice a secret message using the RSA encryption algorithm. Bob's message m is 88 and he encrypts it using Alice's public key, which is (n, e) = (4699, 1171), to obtain a ciphertext c. If the ciphertext is c = 3908, then what is Bob's message m?
The plaintext can be obtained by obtaining Alice's private key, which is easy to obtain because it is possible to factor 4699 in polynomial time to find phi(n). Let's assume though that only Alice knows the two primes p and q that 4699 is made of and 4699 can't be factored in polynomial time.
Alice 's private key d₁ can be computed using phi(n)
Alice computes phi(n) = phi(p)*phi(q) = (127-1)*(37-1) = 4536
Alice's private key d₁ is ed₁ ≡ 1 mod 4536 which is 1171d₁ ≡ 1 mod 4536
because 1171d₁ + 4536y₁ = 1 for some d₁, y₁ in Z
=> d₁ = 1747 because 1171*1747+4536*(-451) = 1 in Z
Since c = 3908 then m ≡ 3908¹⁷⁴⁷ mod 4699 ≡ 88 mod 4699
This was the answer that the TA was expecting to see, which is why he was blown away when he saw this instead:
Eve computes a private key d₂ by overcounting exactly 3 times
d₂ = 235 because 1171*235+3276*(-84) = 1 in Z
Since c = 3908 then m ≡ 3908²³⁵ mod 4699 ≡ 88 mod 4699
The second key d₂ is a number that's 7 times less than the TA's key! As far as the TA was concerned there is only one decryption key, namely d₁ = 1747, and he naturally had a marking meltdown on my assignment.
But there are even more keys that decrypt the cipher text. For example, 504, 546, 702, 756 also decrypt the message in this example and so a pattern emerges. It can be verified that all combinations of 2Ê³ x 3Ë¢ x 7áµ— , 2Ê³ x 3Ë¢ x 13áµ˜, 2Ê³ x 3Ë¢ x 7áµ— x 13áµ˜ where 0 < r, s, t < 5 and u = 1 among others produce private keys, which can be used to decrypt the ciphertext c in this example even though these keys are not the same as the one generated with phi(n).
Generally speaking, when n is the product of 2 distinct odd primes, then there will always be at least 1 extra private key, other than the private key generated using phi(n)
So how can one find d₂, or rather, how can one find the other keys that decrypt c?'
21.10.15
Exponentiation Tables From Another Perspective
So far I’ve only looked at generating exponentiation tables by generating the first phi(n)/2 elements of each row. However, this can also be done by generating the first phi(n)/2 columns instead. At first it seems like a task that will take the same amount of effort but there are a few results that can be used to minimize this effort.
Theorem 1: Given two positive integers n and x such that x < n then either
(n-1)^{x} = 1 mod n if x is even
or
(n-1)^{x} = n-1 mod n if x is odd
Proof: Direct proof from elementary algebra.
Case 1: If x is even then x = 2k for some positive integer k
(n-1)^{x} = (n-1)^{2k} mod n
= (n-1)*(n-1)*(n-1)*...*(n-1) mod n 2k factors
= (n^{2k} - 2kn^{2k} + ... - 2kn + 1) mod n where ... represents decreasing powers of n
= (0 - 0 + ... - 0 + 1) mod n since any multiple of n is divisible by n
= 1 mod n
Case 2: If x is odd then x = 2k + 1, so
(n-1)^{x} = (n-1)^{2k+1} mod n
= [(n-1)^{2k}]*[(n-1)^{1}] mod n
= [1 * (n-1)] mod n by Case 1
=(n-1) mod n
.'.
= (0 - 0 + ... - 0 + 1) mod n since any multiple of n is divisible by n
= 1 mod n
Case 2: If x is odd then x = 2k + 1, so
(n-1)^{x} = (n-1)^{2k+1} mod n
= [(n-1)^{2k}]*[(n-1)^{1}] mod n
= [1 * (n-1)] mod n by Case 1
=(n-1) mod n
.'.
This result proves that the last row of any exponentiation table mod n is a consecutive sequence of 1 and n-1.
It also suggests that in every even column (a column underneath an even exponent) there will be at least one repetitive element since the last entry in the column is equivalent to the first non-zero entry, namely 1.
Second half of even columns lists the first half in reverse order |
Claim: The second half of any even column of the exponentiation table of Z_{n} when n is the product of two distinct odd primes is equivalent to the first half in reverse order.
Since the column is even, then by Theorem 1 the element at (n-1) is equal to 1, which is equivalent to the element at 1
What remains to be proven is that the element at (n-2) is equal to the element at 2, the element at (n-3) is equal to the element at 3, the element at (n-4) is equal to the element at 4, and so on until the element at (n-1)/2 is reached, which needs to be shown is equal to the element at ((n-1)/2)+1
The proof for this builds upon Claim 2 from Types of Exponents:
(n-1)^{2} = [(n-1)*(n-1)] mod n
Since the column is even, then by Theorem 1 the element at (n-1) is equal to 1, which is equivalent to the element at 1
What remains to be proven is that the element at (n-2) is equal to the element at 2, the element at (n-3) is equal to the element at 3, the element at (n-4) is equal to the element at 4, and so on until the element at (n-1)/2 is reached, which needs to be shown is equal to the element at ((n-1)/2)+1
The proof for this builds upon Claim 2 from Types of Exponents:
(n-1)^{2} = 1 mod n
(n-1)^{2} = [(n-1)*(n-1)] mod n
= (n^{2} - 2n + 1) mod n
= (n^{2} mod n) - (2n mod n) + (1 mod n)
since any multiple of n is divisible by n
= (0 mod n) - (0 mod n) + (1 mod n)
= 1 mod n
More generally, for any integer k such that 1 < k < n
(n-k)^{2} = k^{2} mod n since (n-k)^{2 }= n^{2 }- 2nk + k^{2 }= 0 + 0 + k^{2 }^{ }= k^{2 }since any multiple of n is divisible by n so therefore it is 0 mod n
In particular, the second half of the column at 2 in the exponentiation table will simply list the first half of the column in reverse order because:
(n-2)^{2} = 4 mod n , (n-3)^{2} = 9 mod n, (n-4)^{2} = 16 mod n ,..., and so on up to (n - (n-1)/2))^{2} = ((n-1)/2) = (n - (n-1)/2) + 1 for column 2.
Similar logic applies for other columns r where r is an integer such that r = 2s for some other integer s since
In particular, the second half of the column at 2 in the exponentiation table will simply list the first half of the column in reverse order because:
(n-2)^{2} = 4 mod n , (n-3)^{2} = 9 mod n, (n-4)^{2} = 16 mod n ,..., and so on up to (n - (n-1)/2))^{2} = ((n-1)/2) = (n - (n-1)/2) + 1 for column 2.
Similar logic applies for other columns r where r is an integer such that r = 2s for some other integer s since
(n-k)^{r }= n^{r }- rn^{r}nk^{ } + ... - rnk^{r} + k^{r } = 0 ^{ }- 0^{ } + ... - 0 + k^{r} = k^{r} mod n
To be continued...
What remains to be shown is that the element at (n-1)/2 is equal to the element at ((n-1)/2)+1
To be continued...
Labels:
Abstract Algebra
,
Mathematics
,
Number Theory
,
RSA Problem
21.9.15
A Proper Vintage Filter
After reading the book I talked about here I realized that the vast majority of modern camera filters that claim to make photos look vintage do not quite capture the essence of photos from the early days of photography, not even the vintage filter that I made for Coloroid Pro, as much as it pains me to admit.
In the early days of film photography capturing light accurately was a very tricky business and therefore the skies in many original vintage landscape photographs are always overexposed.
Photographers had to take a separate image of the sky and add it to the photograph during processing, which was time consuming and expensive.
In other words, clouds in photographs were a luxury item back then and most photographs didn't have any or had the same ones as other photographs.
The situation was so bad that some photography studios had negatives of the same clouds that they generously slapped onto different photographs claiming total authenticity, resulting in awkward family gatherings.
So to accurately capture the essence of photos from the early days of photography, the skies must be overexposed: no clouds for anyone!
There's no need for any fancy cloud detection algorithms because it can all be done with colour.
Here's a shot of some boisterous clouds at the Buzludzha peak that I took earlier this year.
If I simply crank up the exposure levels in some fancy photo editing software and then desaturate, I am still left with clouds.
If I crank up the brightness, then cautiously turn down the contrast, and finally desaturate the whole image, I achieve this
And finally, if tint it slightly, then I can turn any modern digital landscape photo into a believable vintage photograph, no special effects required.
Below is a Javascript demo of the algorithm for proper vintage photo:
In the early days of film photography capturing light accurately was a very tricky business and therefore the skies in many original vintage landscape photographs are always overexposed.
Photographers had to take a separate image of the sky and add it to the photograph during processing, which was time consuming and expensive.
In other words, clouds in photographs were a luxury item back then and most photographs didn't have any or had the same ones as other photographs.
The situation was so bad that some photography studios had negatives of the same clouds that they generously slapped onto different photographs claiming total authenticity, resulting in awkward family gatherings.
So to accurately capture the essence of photos from the early days of photography, the skies must be overexposed: no clouds for anyone!
There's no need for any fancy cloud detection algorithms because it can all be done with colour.
Here's a shot of some boisterous clouds at the Buzludzha peak that I took earlier this year.
If I simply crank up the exposure levels in some fancy photo editing software and then desaturate, I am still left with clouds.
If I crank up the brightness, then cautiously turn down the contrast, and finally desaturate the whole image, I achieve this
And finally, if tint it slightly, then I can turn any modern digital landscape photo into a believable vintage photograph, no special effects required.
Below is a Javascript demo of the algorithm for proper vintage photo:
Labels:
digital image processing
,
Javascript
15.9.15
Finding The Order Of An Element Much Faster
In my previous post I talked about finding the order of an element mod n using what I call skips, the logic for which was first described in the last few paragraphs of Exponentiation Tables in Z sub n. I don't have to stop at 4 skips so long as I account for the overcount and keep the initial element a small and divisible by only itself and 1
The following expression aaa%cur !== 0 replaces the endless logical expressions that are needed to ensure the skipping algorithm stops after encountering the order of a mod n exactly once.
aaa = some_small_power_of_a;
cur = aaa;
do
{
cur = (aaa * cur)%n;
index = length_of_jump + index;
} while ( cur !== 1 && aaa%cur !== 0);
//account for overcounting
In order for this expression to replace the endless logical statements and work correctly, a must be a small prime, and the last power of a before the while loop must be the highest power of a such that it is smaller than n without modulo. Otherwise a different, strict divide operator must be used.
This is easy to see.
Example: let a = 2 and n = 35
aaaaa = a*a*a*a*a = 32
the only integers that divide aaaaa with 0 remainder are 2, 4, 8, 16, 32
therefore if the jump lands on one of these integers then the order of 2 has been reached exactly once already
The 18-skip uses this expression and here's how it stacks up to the algorithm presented earlier here and the algorithm from my previous post:
Example: n = 62303*164999 = 10279932697
The 18-skip algorithm finds the order of 2 mod n in 6 seconds; find_order_even_faster finds the order of 2 mod n in 25 seconds, and find_order_faster in 41 seconds.
18-skip implementation, which works best for large n (n that's at least 9 digits or more) and small a:
The 4-skip implementation of the algorithm described earlier in this post with Javascript:
The 2-skip algorithm described in Finding The Order Of An Element Faster with Javascript:
The various ways of finding the order of 2 mod n described here so far from slowest to fastest where the last 3 ways can be used for finding the order of any element mod n:
The following expression aaa%cur !== 0 replaces the endless logical expressions that are needed to ensure the skipping algorithm stops after encountering the order of a mod n exactly once.
aaa = some_small_power_of_a;
cur = aaa;
do
{
cur = (aaa * cur)%n;
index = length_of_jump + index;
} while ( cur !== 1 && aaa%cur !== 0);
//account for overcounting
In order for this expression to replace the endless logical statements and work correctly, a must be a small prime, and the last power of a before the while loop must be the highest power of a such that it is smaller than n without modulo. Otherwise a different, strict divide operator must be used.
This is easy to see.
Example: let a = 2 and n = 35
aaaaa = a*a*a*a*a = 32
the only integers that divide aaaaa with 0 remainder are 2, 4, 8, 16, 32
therefore if the jump lands on one of these integers then the order of 2 has been reached exactly once already
The 18-skip uses this expression and here's how it stacks up to the algorithm presented earlier here and the algorithm from my previous post:
Example: n = 62303*164999 = 10279932697
The 18-skip algorithm finds the order of 2 mod n in 6 seconds; find_order_even_faster finds the order of 2 mod n in 25 seconds, and find_order_faster in 41 seconds.
18-skip implementation, which works best for large n (n that's at least 9 digits or more) and small a:
The 4-skip implementation of the algorithm described earlier in this post with Javascript:
The 2-skip algorithm described in Finding The Order Of An Element Faster with Javascript:
The various ways of finding the order of 2 mod n described here so far from slowest to fastest where the last 3 ways can be used for finding the order of any element mod n:
Labels:
Abstract Algebra
,
Mathematics
,
Order of An Element
,
RSA Problem
,
strict division
11.9.15
Finding The Order Of An Element Even Faster
The following algorithm is an optimized version of the algorithm presented here. Like the earlier
version, this algorithm also finds the order of an element by successively jumping over several elements at a time but this one jumps over 4 instead of just 2, which means it needs to iterate through only half the elements of find_order_faster(n, a) described in Finding The Order Of An Element Faster.
The logic behind this and the previous algorithm was first described in the last few paragraphs of Exponentiation Tables in Z sub n. I don't have to stop at 4 skips so long as I account for the overcount and keep the initial element a small and divisible by only itself and 1: in other words a big n requires a big jump but the result can be found in the same number of iterations as a smaller n.
For example, finding the order of a mod n for a 10 digit n can be reduced from 40 minutes to a few seconds simply by adjusting the length of the jump.
And below is the older algorithm, with cleaner variable names for reference. Looking at the two algorithms one might think of recursion to speed things up even more but I will not talk about this here.
In the while loop of these algorithms there are 3 things happening, namely: finding the product of the current element times a predefined constant; finding the remainder of the two; counting the number of jumps.
Standard multiplication of two n-bit integers takes O(n^{2}) but there is an algorithm that uses only
O(n log_{2} n log_{2} log_{2} n) bit operations.
Finding the quotient of two integers can be done in the same number of bit operations as the number of bit operations needed to multiply two n-bit integers.
Counting the number of jumps is fairly trivial.
By the way, it is easy to see that standard multiplication of one n-bit integer and one m-bit integer takes O(mn)
The implementation below is in Javascript because I am a computational masochist.
The 4-skip implementation of the algorithm described earlier in this post with Javascript:
The 2-skip algorithm described in Finding The Order Of An Element Faster with Javascript:
The various ways of finding the order of 2 mod n described here so far from slowest to fastest where the last 3 ways can be used for finding the order of any element mod n:
Note that in the last two algorithms if n is large and a is less than 1/4 of n with non-trivial order then aa and aaaa will be relatively small as well. Both algorithms will overcount trivial orders up to the jump length.
version, this algorithm also finds the order of an element by successively jumping over several elements at a time but this one jumps over 4 instead of just 2, which means it needs to iterate through only half the elements of find_order_faster(n, a) described in Finding The Order Of An Element Faster.
The logic behind this and the previous algorithm was first described in the last few paragraphs of Exponentiation Tables in Z sub n. I don't have to stop at 4 skips so long as I account for the overcount and keep the initial element a small and divisible by only itself and 1: in other words a big n requires a big jump but the result can be found in the same number of iterations as a smaller n.
For example, finding the order of a mod n for a 10 digit n can be reduced from 40 minutes to a few seconds simply by adjusting the length of the jump.
/* -------------------------------------------------
This content is released under the GNU License
http://www.gnu.org/copyleft/gpl.html
Author: Marina Ibrishimova
Version: 1.0
Purpose: Find the order of any a mod n for n = p*q where p,q > 2
---------------------------------------------------- */
function find_order_even_faster(n, a)
{
int aa = (a*a);
int aaa = (a*a*a);
int aaaa = (a*a*a*a);
int cur = aaaa;
//length of the jump
int index = 4;
while ( cur !== 1 && cur !== a && cur !== aa && cur !== aaa)
{
cur = (aaaa * cur)%n;
index = 4 + index;
}
if(cur === a){index = index-1;}
else if(cur === aa){index = index-2;}
else if(cur === aaa){index = index-3;}
return index;
}
Someone might be tempted to use a ternary operator to replace the if-else statements at the end but a ternary operator will be too costly in this case. Especially for bigger jumps where the number of if-else statements might exceed 100 million. And below is the older algorithm, with cleaner variable names for reference. Looking at the two algorithms one might think of recursion to speed things up even more but I will not talk about this here.
/* -------------------------------------------------
This content is released under the GNU License
http://www.gnu.org/copyleft/gpl.html
Author: Marina Ibrishimova
Version: 1.0
Purpose: Find the order of any a mod n for n = p*q where p,q > 2
---------------------------------------------------- */
function find_order_faster(n, a)
{
int aa = a*a;
int cur = aa;
int index = 2;
while( cur != a && cur != 1)
{
cur = (aa * cur)%n;
index = 2 + index;
}
if(cur == a){
index = index - 1;}
return
index;
}
Outside of the while loop of both algorithms there is a number of primitive operations, and this number is proportional to the length of the jump.In the while loop of these algorithms there are 3 things happening, namely: finding the product of the current element times a predefined constant; finding the remainder of the two; counting the number of jumps.
Standard multiplication of two n-bit integers takes O(n^{2}) but there is an algorithm that uses only
O(n log_{2} n log_{2} log_{2} n) bit operations.
Finding the quotient of two integers can be done in the same number of bit operations as the number of bit operations needed to multiply two n-bit integers.
Counting the number of jumps is fairly trivial.
By the way, it is easy to see that standard multiplication of one n-bit integer and one m-bit integer takes O(mn)
The implementation below is in Javascript because I am a computational masochist.
The 4-skip implementation of the algorithm described earlier in this post with Javascript:
The 2-skip algorithm described in Finding The Order Of An Element Faster with Javascript:
The various ways of finding the order of 2 mod n described here so far from slowest to fastest where the last 3 ways can be used for finding the order of any element mod n:
- Using a cyclic permutation
- Using an algebraic expression
- Using simple addition
- Using double skips
- Using quadruple skips
Note that in the last two algorithms if n is large and a is less than 1/4 of n with non-trivial order then aa and aaaa will be relatively small as well. Both algorithms will overcount trivial orders up to the jump length.
Labels:
Abstract Algebra
,
Discrete Mathematics
,
Javascript
,
Mathematics
,
Order of An Element
,
RSA Problem
9.9.15
Photoshop Before Photoshop
Serious digital photographers often sneer at mobile photography with its tap-to-apply filters and unrealistic colours much like film camera photographers used to scoff at digital photography with its click-to-apply Photoshop adjustments and unrealistic colours.
The argument is always the same: the latest methodology of capturing reality does not capture reality accurately.
I admit that I am one of the hipster scoffers who claim that none of the reality capturing devices invented so far capture reality accurately but that is another subject matter that I've covered already.
What I did find surprising after reading a book titled Faking It: Manipulated Photography Before Photoshop is that people have been combatting the imperfections of reality capturing devices by tampering with photos after they were taken pretty much since such devices were first introduced.
As early as 1846, only 5 years after the first calotype process was introduced allowing an unlimited number of photographs to be generated from a single negative, a man named Calvert Richards Jones altered a photograph he shot by painting over a figure in the negative in order to remove it from the processed photo because it didn't fit the scene.
Even the most hipster purists of all photographers who preached about the dangers of creating reality distortion fields by editing photographs would occasionally retouch their masterpieces. Such was the case with P. H. Emerson who would occasionally add clouds to the overexposed skies on his photographs when nobody was looking yet condoned anyone else who openly did so as well.
The skies in P. H. Emerson's works were overexposed not because he was secretly a lousy photographer but because the reality capturing devices at the time had a hard time processing certain types of light.
In those early days of photography colour had to be added after taking the photograph using gum bichromate, which was first introduced in 1855 but was not used until 1890.
The following photograph of my great great great grandfather, or great^{3 }grandfather was taken in 1888 in Bulgaria and gum bichromate was used to allow the photographer to introduce colour and brushwork to it after it was taken. On a personal note, it looks like I've inherited his arched eyebrows but hopefully not the bushy moustache.
The argument is always the same: the latest methodology of capturing reality does not capture reality accurately.
I admit that I am one of the hipster scoffers who claim that none of the reality capturing devices invented so far capture reality accurately but that is another subject matter that I've covered already.
What I did find surprising after reading a book titled Faking It: Manipulated Photography Before Photoshop is that people have been combatting the imperfections of reality capturing devices by tampering with photos after they were taken pretty much since such devices were first introduced.
As early as 1846, only 5 years after the first calotype process was introduced allowing an unlimited number of photographs to be generated from a single negative, a man named Calvert Richards Jones altered a photograph he shot by painting over a figure in the negative in order to remove it from the processed photo because it didn't fit the scene.
Even the most hipster purists of all photographers who preached about the dangers of creating reality distortion fields by editing photographs would occasionally retouch their masterpieces. Such was the case with P. H. Emerson who would occasionally add clouds to the overexposed skies on his photographs when nobody was looking yet condoned anyone else who openly did so as well.
P.H. Emerson's A Stiff Pull retouched |
The skies in P. H. Emerson's works were overexposed not because he was secretly a lousy photographer but because the reality capturing devices at the time had a hard time processing certain types of light.
A Stiff Pull original |
In those early days of photography colour had to be added after taking the photograph using gum bichromate, which was first introduced in 1855 but was not used until 1890.
The following photograph of my great great great grandfather, or great^{3 }grandfather was taken in 1888 in Bulgaria and gum bichromate was used to allow the photographer to introduce colour and brushwork to it after it was taken. On a personal note, it looks like I've inherited his arched eyebrows but hopefully not the bushy moustache.
Ivan Danchovsky c. 1888 |
Labels:
digital image processing
4.9.15
Finding Phi Much Faster
So far I've come up with 4* different ways of finding the order of 2 mod n and 2 different ways of finding the order of any element a mod n such that GCD(a,n) = 1, all of which can be used to find phi(n).
Here's the implementation for the above algorithm using a worker that is not overworked now that it is only dealing with integers.
*The various ways of finding the order of 2 mod n described here so far from slowest to fastest where the last 2 ways can be used for finding the order of any element mod n:
The order of an element can be used to find phi(n) as I already showed in the first few Finding Phi posts.
Here's the latest, fastest so far algorithm for finding phi(n) when n is the product of two distinct odd primes, which uses the algorithm described in here and the overcounting find_phi(n) function, but it doesn't use Discrete Fourier Transform for faster multiplication.
/* -------------------------------------------------
This content is released under the GNU License
http://www.gnu.org/copyleft/gpl.html
Author: Marina Ibrishimova
Version: 1.0
Purpose: Find the order of 2 mod n for n = p*q where p,q > 2
and use it to find phi(n)
---------------------------------------------------- */
function find_order_faster(n, 2)
{
int next = a*a;
int cur = next;
int order = 2;
while( cur != a && cur != 1)
{
cur = (next * cur)%n;
order = 2 + order;
}
if(cur == a){order = order - 1;}
return order;
}
function find_phi(n)
{
int cycle_length = find_order(n);
int phi_length = 0;
while(phi_length < n)
{
phi_length = phi_length + cycle_length;
}
return phi_length - cycle_length;
}
By the way, this is why it is important to enforce strict types in Javascript even though it supposedly takes care of things in the background with magic: in programming there's no such thing as magic and if someone claims the opposite, then beware.
*The various ways of finding the order of 2 mod n described here so far from slowest to fastest where the last 2 ways can be used for finding the order of any element mod n:
1.9.15
Finding The Order Of An Element Faster
So far I've described and implemented one way of finding the order of any element mod n when n is the product of two distinct odd primes but there is another, even faster algorithm that takes half the number of computations of the previous algorithm described in Generating Exponentiation Tables.
This new algorithm takes advantage of the fact that every second element after the element at index 2 is simply a multiple mod n, which can be used to arrive at the element's order roughly two times faster than the algorithm previously described.
For example, in row j of the exponentiation table of Z sub n, the element at column 2 is s_{0}=j*j, the element at column 4 is s_{1} = t*j and so on until either s_{i} = 1 or s_{i} = j. A count of the number of "jumps" reveals the order of the element and furthermore if s_{i} = j, then the order of the element is odd and if s_{i} = 1 then the order of the element is even.
Below is the new algorithm:
And for reference, below is the algorithm described in Generating Exponentiation Tables:
The worst case scenario in the number of iterations for this new algorithm find_order_faster(n,a) is phi(n)/4 since the algorithm makes jumps to every second element starting from a*a for a given element a such that GCD(a,n)=1.
Although technically speaking only 1 of these two integers can potentially be large, the "next" integer is always going to be the integer at index 2, which for small a is very negligible.
find_order_faster(n,a) is guaranteed to hit either 1 or a in phi(n)/4 iterations since the starting point of the algorithm is the element at index 2 of any row j so therefore the elements are shifted by 2, which is a phenomenon I first discussed in Exponentiation Tables in Z sub n.
In contrast, the starting point of for the old algorithm find_order(n,a) is 1 and so in the worst case scenario it must visit every element up to phi(n)/2 since phi(n)/2 is a universal exponent as shown in Finding Phi.
Example: find_order_faster(35,3) returns 12 and visits only 9, 11, 29, 16, 4, 1:
find_order(35,3), on the other hand, visits 3, 9, 27, 11, 33, 29, 17, 16, 13, 4, 12, 1
The above example shows the find_order_faster function's behaviour when the order of a is even: namely it terminates when it hits the first 1. If the order is odd find_order_faster(n,a) will terminate as soon as it hits a and hence the if(cur == a){order = order - 1;} statement in the end but the number of iterations in this case will still be nearly half the number of iterations of find_order(n,a).
find_order(n,a) will behave the same way regardless of whether the order is even or odd.
The implementations of both algorithms with worker.js are shown below, and both of them are much faster now that strict types have been forced. Who knew Javascript isn't just some magical place where types just figure themselves out, slowing down everything else in the process.
Example: n = 3340291861
The find_order_faster(n) algorithm returns the order of 2 mod 3340291861 in 36 seconds and the algorithm find_order(n) returns it in 57 seconds using worker.js
The algorithm described in this post with a worker:
The algorithm described in Generating Exponentiation Tables with a worker:
The various ways of finding the order of 2 mod n described here so far from slowest to fastest where the last 2 ways can be used for finding the order of any element mod n:
This new algorithm takes advantage of the fact that every second element after the element at index 2 is simply a multiple mod n, which can be used to arrive at the element's order roughly two times faster than the algorithm previously described.
For example, in row j of the exponentiation table of Z sub n, the element at column 2 is s_{0}=j*j, the element at column 4 is s_{1} = t*j and so on until either s_{i} = 1 or s_{i} = j. A count of the number of "jumps" reveals the order of the element and furthermore if s_{i} = j, then the order of the element is odd and if s_{i} = 1 then the order of the element is even.
Below is the new algorithm:
/* -------------------------------------------------
This content is released under the GNU License
http://www.gnu.org/copyleft/gpl.html
Author: Marina Ibrishimova
Version: 1.0
Purpose: Find the order of any a mod n for n = p*q where p,q > 2
---------------------------------------------------- */
function find_order_faster(n, a)
{
int next = a*a;
int cur = next;
int order = 2;
while( cur != a && cur != 1)
{
cur = (next * cur)%n;
order = 2 + order;
}
if(cur == a){order = order - 1;}
return order;
}
And for reference, below is the algorithm described in Generating Exponentiation Tables:
/* -------------------------------------------------
This content is released under the GNU License
http://www.gnu.org/copyleft/gpl.html
Author: Marina Ibrishimova
Version: 1.0
Purpose: Find the order of any a mod n for n = p*q where p,q > 2
---------------------------------------------------- */
function find_order(n, a)
{
int anot = 1;
int aa = a;
int aaa = a*a;
int coef = a - 1;
int index = 0;
int order = 2;
while(index != 1)
{
index = (coef*(anot + aa + aaa) + anot) % n;
anot = aa;
aa = aaa;
aaa = index;
order = order + 1;
}
return order;
}
Note: both of these algorithms will run into an infinite loop if GCD(n,a) is not equal to 1 so a simple check must be added at the beginning of each function to find if GCD(n,a) is not equal to 1, in which case n can easily be factored.The worst case scenario in the number of iterations for this new algorithm find_order_faster(n,a) is phi(n)/4 since the algorithm makes jumps to every second element starting from a*a for a given element a such that GCD(a,n)=1.
For very large input n this should be used to speed up the following part of find_order_faster(n,a):
cur = (next * cur)
Although technically speaking only 1 of these two integers can potentially be large, the "next" integer is always going to be the integer at index 2, which for small a is very negligible.
find_order_faster(n,a) is guaranteed to hit either 1 or a in phi(n)/4 iterations since the starting point of the algorithm is the element at index 2 of any row j so therefore the elements are shifted by 2, which is a phenomenon I first discussed in Exponentiation Tables in Z sub n.
In contrast, the starting point of for the old algorithm find_order(n,a) is 1 and so in the worst case scenario it must visit every element up to phi(n)/2 since phi(n)/2 is a universal exponent as shown in Finding Phi.
Example: find_order_faster(35,3) returns 12 and visits only 9, 11, 29, 16, 4, 1:
The iterations that find_order_faster(35, 3) makes |
find_order(35,3), on the other hand, visits 3, 9, 27, 11, 33, 29, 17, 16, 13, 4, 12, 1
The above example shows the find_order_faster function's behaviour when the order of a is even: namely it terminates when it hits the first 1. If the order is odd find_order_faster(n,a) will terminate as soon as it hits a and hence the if(cur == a){order = order - 1;} statement in the end but the number of iterations in this case will still be nearly half the number of iterations of find_order(n,a).
find_order(n,a) will behave the same way regardless of whether the order is even or odd.
The implementations of both algorithms with worker.js are shown below, and both of them are much faster now that strict types have been forced. Who knew Javascript isn't just some magical place where types just figure themselves out, slowing down everything else in the process.
Example: n = 3340291861
The find_order_faster(n) algorithm returns the order of 2 mod 3340291861 in 36 seconds and the algorithm find_order(n) returns it in 57 seconds using worker.js
The algorithm described in Generating Exponentiation Tables with a worker:
The various ways of finding the order of 2 mod n described here so far from slowest to fastest where the last 2 ways can be used for finding the order of any element mod n:
Labels:
Abstract Algebra
,
Group Theory
,
Javascript
,
Mathematics
,
Order of An Element
,
RSA Problem
31.8.15
The Art Of Overcounting
The function find_phi(n) pops up in almost all of my algorithms for finding phi of n, and almost always I point out that it is a function that may overcount.
Here's what I mean by that: if the order k of an element a mod n is less than the difference between n and phi(n) then the result from find_phi(n) will be a higher multiple of k than phi(n). In other words:
If k < (n - phi(n)) where a^{k} = 1 mod n and k is the smallest such integer for a, then find_phi(n) returns r such that r > phi(n) and (r-k)= phi(n)
Example: Let p = 7 and q = 13 then n = p*q = 91 and let a = 2. Since n is the product of 2 distinct odd primes, then any of my functions for finding the order of 2 mod n described in Generating Exponentiation Tables and Phi Not Pi (neither of which uses exponentiation) will return k = 12
Since phi(n) = (p-1)(q-1) then in this case phi(91) = 72 but find_phi(91) returns 84 so r = 84, and as predicted (r-k) = 84 - 12 = 72 = phi(n)
In such a case where the order k of an element a mod n is less than the difference between n and phi(n) some manual poking will be required to retrieve phi(n) using find_phi(n), namely the order of 2 mod n must be returned along with the result of find_phi(n) so that it can be subtracted until phi(n) is reached but there are other functions for finding phi of n once the order of a particular element is known.
The most crucial piece of the puzzle in finding phi(n) is finding the order of an element mod n fast enough where "fast enough" is a relative concept.
Here's what I mean by that: if the order k of an element a mod n is less than the difference between n and phi(n) then the result from find_phi(n) will be a higher multiple of k than phi(n). In other words:
If k < (n - phi(n)) where a^{k} = 1 mod n and k is the smallest such integer for a, then find_phi(n) returns r such that r > phi(n) and (r-k)= phi(n)
Example: Let p = 7 and q = 13 then n = p*q = 91 and let a = 2. Since n is the product of 2 distinct odd primes, then any of my functions for finding the order of 2 mod n described in Generating Exponentiation Tables and Phi Not Pi (neither of which uses exponentiation) will return k = 12
Since phi(n) = (p-1)(q-1) then in this case phi(91) = 72 but find_phi(91) returns 84 so r = 84, and as predicted (r-k) = 84 - 12 = 72 = phi(n)
In such a case where the order k of an element a mod n is less than the difference between n and phi(n) some manual poking will be required to retrieve phi(n) using find_phi(n), namely the order of 2 mod n must be returned along with the result of find_phi(n) so that it can be subtracted until phi(n) is reached but there are other functions for finding phi of n once the order of a particular element is known.
The most crucial piece of the puzzle in finding phi(n) is finding the order of an element mod n fast enough where "fast enough" is a relative concept.
8.8.15
Optimizing Life Of Phi Function
In Life of Phi I wrote a function for finding the order of 2 mod n when n is the product of two distinct odd primes then I uncovered a faster way of doing this here, and a couple of slower ones described here, and here.
Using Javascript's remainder operator, which does not act as a modulus operator unless all expressions and values involved are always positive, I can speed up the function findO2(n) described in Life of Phi because the expression (a + a) is always positive given a positive starting a.
Below is the optimized version of findO2(n), which finds the order of 2 mod n in approximately the same amount of time as find_order(n) described in Generating Exponentiation Tables (or slightly faster).
Using Javascript's remainder operator, which does not act as a modulus operator unless all expressions and values involved are always positive, I can speed up the function findO2(n) described in Life of Phi because the expression (a + a) is always positive given a positive starting a.
Below is the optimized version of findO2(n), which finds the order of 2 mod n in approximately the same amount of time as find_order(n) described in Generating Exponentiation Tables (or slightly faster).
/* -------------------------------------------------
This content is released under the GNU License
http://www.gnu.org/copyleft/gpl.html
Author: Marina Ibrishimova
Version: 1.0
Purpose: Find the order of 2 mod n for n = p*q | p,q > 2
---------------------------------------------------- */
function findoO2(n)
{
var a = 2;
var i = 1;
while(a != 1)
{
a = (a + a)%n;
i = i + 1;
}
return i;
}
Labels:
Euler's Phi Function
,
Javascript
,
Mathematics
25.7.15
Finding Phi Even Faster
Renote: phi(n) is the number of integers that are coprime with n; phi(n) = (p-1)(q-1) when n is the product of two distinct odd primes p and q. In Types of Exponents I showed that phi(n)/2 is a universal exponent when n is the product of two distinct odd primes.
In Life of Phi I came up with one way of finding the order of 2 mod n when n is the product of two distinct odd primes, and then I used it in Finding Phi Faster to find phi(n).
A few days ago I uncovered a new way of finding the order of 2 mod n when n is the product of two distinct odd primes.
This means that there's yet another way of finding phi(n) that is even faster than the way described in
Finding Phi Faster using the new algorithm described in Generating Exponentiation Tables.
The algorithm below re-uses the same overcounting find_phi(n) function from Finding Phi Faster but the entire algorithm in this post finds phi(n) even faster because find_order(n) is faster than findO2(n).
Example: n = 8767703359 where n = p*q and p = 137483, q = 63773
Without worker.js the new algorithm finds phi(n) in less than 30 seconds whereas the old algorithm takes a couple of minutes.
With worker.js the new algorithm finds phi(n) in 18 : 58 whereas the old algorithm takes 25 : 7 !
Clearly worker.js is overworked and underpaid but that's not the point.
A few more examples below:
The algorithm described in this post with a worker:
The algorithm described in Finding Phi Faster with a worker:
In Life of Phi I came up with one way of finding the order of 2 mod n when n is the product of two distinct odd primes, and then I used it in Finding Phi Faster to find phi(n).
A few days ago I uncovered a new way of finding the order of 2 mod n when n is the product of two distinct odd primes.
This means that there's yet another way of finding phi(n) that is even faster than the way described in
Finding Phi Faster using the new algorithm described in Generating Exponentiation Tables.
The algorithm below re-uses the same overcounting find_phi(n) function from Finding Phi Faster but the entire algorithm in this post finds phi(n) even faster because find_order(n) is faster than findO2(n).
/* -------------------------------------------------
This content is released under the GNU License
http://www.gnu.org/copyleft/gpl.html
Author: Marina Ibrishimova
Version: 1.0
Purpose: Find the order of 2 mod n for n = p*q where p,q > 2
and use it to find phi(n)
---------------------------------------------------- */
function find_order(n)
{
var a = 1;
var aa = 2;
var aaa = 4;
var index = 0;
var order = 2;
while(index != 1)
{
index = (a + aa + aaa + a) % n;
a = aa;
aa = aaa;
aaa = index;
order = order + 1;
}
return order;
}
function find_phi(n)
{
var cycle_length = find_order(n);
var phi_length = 0;
while(phi_length < n)
{
phi_length = phi_length + cycle_length;
}
return phi_length - cycle_length;
}
Example: n = 8767703359 where n = p*q and p = 137483, q = 63773
Without worker.js the new algorithm finds phi(n) in less than 30 seconds whereas the old algorithm takes a couple of minutes.
With worker.js the new algorithm finds phi(n) in 18 : 58 whereas the old algorithm takes 25 : 7 !
Clearly worker.js is overworked and underpaid but that's not the point.
A few more examples below:
n = 12899*11483 = 148119217
n = 17327*34703 = 601298881
n = 55103*42767 = 2356590001
n = 83243*40127 = 3340291861
n = 62303*164999 = 10279932697
n = 547357*195971 = 107266098647
Below is an implementation of this new algorithm with worker.js followed by an implementation of the old algorithm with worker.js.The algorithm described in this post with a worker:
The algorithm described in Finding Phi Faster with a worker:
Labels:
Euler's Phi Function
,
Mathematics
,
RSA Problem
23.7.15
Generating Exponentiation Tables
I hinted at one way of generating exponentiation tables in the last post of the Life of Phi trilogy, which involved dealing with permutations but there's another interesting way of generating exponentiation tables that relies on the following observation:
Each entry a_{ij} in the exponentiation table with i rows and j columns of Z_{n} when n is the product of 2 distinct primes can be generated as follows:
Below is an algorithm for finding the order of any element of the exponentiation table of Z_{n} when n is the product of 2 distinct primes. It can easily be modified to generate the entire table recursively.
It's also fast.
Example: The algorithm described in this post here and implemented with a worker finds it in 1:49 min whereas the algorithm implemented in Life of Phi and featured in Finding Phi Faster finds the order of 2 mod 915313319 in 2:20 min. The worker slows things down a bit, like quite a bit.
The above algorithm returns the correct answer for the order of 2 mod 915313319 in less than 20 seconds and only one "unresponsive script" nudge in the ribs required to return the correct result! What's more impressive is that find_order(n, a) can find the order of any element a of Z_{n} if GCD(a, n) = 1 or find a zero divisor of Z_{n} , and in particular it can find the order of 4 mod n much faster.
Indeed, in a web console find_order(n, a) returns the order of 4 mod 915313319 in less than 10 seconds!
Each entry a_{ij} in the exponentiation table with i rows and j columns of Z_{n} when n is the product of 2 distinct primes can be generated as follows:
a_{ij} = [(j - 1)(a_{i-1} + a_{i-2} + a_{i-3})] + a_{i-3 } mod n
Below is an algorithm for finding the order of any element of the exponentiation table of Z_{n} when n is the product of 2 distinct primes. It can easily be modified to generate the entire table recursively.
It's also fast.
/* -------------------------------------------------
This content is released under the GNU License
http://www.gnu.org/copyleft/gpl.html
Author: Marina Ibrishimova
Version: 1.0
Purpose: Find the order of any a mod n for n = p*q where p,q > 2
---------------------------------------------------- */
function find_order(n, a)
{
var anot = 1;
var aa = a;
var aaa = a*a;
var coef = a - 1;
var index = 0;
var order = 2;
//added bonus
var bingo = "a divides n";
while(index != 1)
{
if (index === a) {return bingo;}
index = (coef*(anot + aa + aaa) + anot) % n;
anot = aa;
aa = aaa;
aaa = index;
order = order + 1;
}
return order;
}
Example: The algorithm described in this post here and implemented with a worker finds it in 1:49 min whereas the algorithm implemented in Life of Phi and featured in Finding Phi Faster finds the order of 2 mod 915313319 in 2:20 min. The worker slows things down a bit, like quite a bit.
The above algorithm returns the correct answer for the order of 2 mod 915313319 in less than 20 seconds and only one "unresponsive script" nudge in the ribs required to return the correct result! What's more impressive is that find_order(n, a) can find the order of any element a of Z_{n} if GCD(a, n) = 1 or find a zero divisor of Z_{n} , and in particular it can find the order of 4 mod n much faster.
Indeed, in a web console find_order(n, a) returns the order of 4 mod 915313319 in less than 10 seconds!
Labels:
Euler's Phi Function
,
Mathematics
,
RSA Problem
11.7.15
Pompeii
I didn't really know what to expect from the ancient city of Pompeii. I didn't know much about it other than the fact that it is the most well-preserved city of the ancient Roman Empire.
The fact that in those 17 years almost nothing was rebuilt suggests that many of the wealthy inhabitants abandoned the area and left behind the poor and the handicapped who were unable to restore the city to its former glory as a direct result of the lack of funds.
The entrance to Pompeii |
The entire city was well-preserved because it was buried under ~4 meters of ash for nearly 2000 years after a major eruption of Mount Vesuvius in 79 AD.
Mount Vesuvius has erupted many times in the past and it is likely to erupt again in the future. It is not the largest volcano in the world but it is one of the most dangerous ones because the area surrounding it is still very densely populated, which is why alerting people who live nearby when seismic activity is first recorded is crucial to saving their lives.
Earthquakes and small tremors are an indicator that a nearby volcano is about to erupt violently and it was volcanoes like Mount Vesuvius that gave me the idea of using people within a social network in different time zones to alert other people if a violent natural event in their area is likely to occur before it actually occurs in order to save more lives
Volcanoes are mainly unpredictable because it is uncertain at which point after the last seismic activity is recorded the volcano will erupt, and this is why it is important to notify people of any seismic activity, even of tremors that would not normally awaken anyone in the middle of the night.
Mount Vesuvius has erupted many times in the past and it is likely to erupt again in the future. It is not the largest volcano in the world but it is one of the most dangerous ones because the area surrounding it is still very densely populated, which is why alerting people who live nearby when seismic activity is first recorded is crucial to saving their lives.
Earthquakes and small tremors are an indicator that a nearby volcano is about to erupt violently and it was volcanoes like Mount Vesuvius that gave me the idea of using people within a social network in different time zones to alert other people if a violent natural event in their area is likely to occur before it actually occurs in order to save more lives
Volcanoes are mainly unpredictable because it is uncertain at which point after the last seismic activity is recorded the volcano will erupt, and this is why it is important to notify people of any seismic activity, even of tremors that would not normally awaken anyone in the middle of the night.
The rear view of the entrance with Mount Vesuvius in the back |
From a scientific point of view Pompeii is very interesting because of the erupting volcano nearby and because it contains a very large number of well-preserved artifacts from the Roman Empire.
From a humanitarian point of view the site is horrifying because it contains a large number of remains of poor people preserved in the position in which they died, and if you don't feel anger, or frustration, or even just a little bit of sadness there then I have bad news for you.
17 years before the eruption of Mount Vesuvius in 79 AD there was a massive earthquake that destroyed many buildings in the city of Pompeii, and affected every aspect of life in the area.
17 years before the eruption of Mount Vesuvius in 79 AD there was a massive earthquake that destroyed many buildings in the city of Pompeii, and affected every aspect of life in the area.
The fact that in those 17 years almost nothing was rebuilt suggests that many of the wealthy inhabitants abandoned the area and left behind the poor and the handicapped who were unable to restore the city to its former glory as a direct result of the lack of funds.
The site has been exposed to the elements for several hundred years and it has started to decay. Many people feel that more should be done to preserve it.
But then again, if people haven't learned the moral behind the story of the site, then what's the point in preserving it anyway?
But then again, if people haven't learned the moral behind the story of the site, then what's the point in preserving it anyway?
Labels:
Travelling
3.7.15
Varna Necropolis
Last year at a developers' conference in San Francisco I met a man who bragged about how he visited every continent. When I asked him where the oldest processed golden artifacts were discovered he was quick to point to Egypt.
He didn't know that this is wrong, most likely because no selfies are allowed at the museum where the oldest processed golden artifacts are.
Most people who were not born and raised in Bulgaria don't know that thousands of years before the pyramids in Egypt were built, there existed a culture, which utilized gold, copper, and pottery long before the Egyptian culture.
Unfortunately, not much is known about this culture because its rulers did not invest in a written language. They seemed to be more concerned about taking their golden artifacts to their graves than educating people and investing in future generations. Empires rise and empires fall.
In a number of graves found in the area of present day Varna, Bulgaria, there were many intricate gold artifacts dating to 3000 years before the pyramids. The area is now known as Varna Necropolis. While these artifacts are beautiful pieces of art showcasing great craftsmanship in their intricate designs, some of them could be representing something much more than just the beauty of art.
Within one grave, likely belonging to a prominent citizen of the community because of the large number of gold artifacts (but not the grave with the most golden artifacts) in it, was found a rectangular gold plate.
In another nearby grave that contained no human remains, were found two golden bulls, one larger than the other.
Looked at in isolation from other artifacts, these bulls and this plate seem to have little function, however, thanks to the investigations of Professor Hristo Smolenov in cooperation with many other European scholars from several different disciplines, an interesting story unfolds.
It appears that the two bulls and the gold plate are actually precise tools of measurement that were used by the ancient Varna and Zagora area cultures. In his book Zagora-Varna the Hidden Superculture, Smolenov shows how the dimensions of these three artifacts are all related to each other, and how they might have been used as measurement tools in the construction of many other artifacts, including other gold pieces, tools, and pottery.
For example, the height of the gold plate is equal to the height of two large bulls plus two small bulls, and the width of the gold plate is equal to the width of one large bull plus one small bull.
There are bone artifacts whose heights and widths correspond to multiples of large and small bulls. There are many pieces of pottery whose height, opening radius, middle radius, and base radius all correspond to multiples of the dimensions of the bulls or the golden plate, indicating that these were most likely measuring devices and not simply pieces of art.
Even more interesting is that there are pieces of pottery predating the graves where the bulls and plate were found by 1000 years that also can be measured precisely in terms of the bulls and plates! This suggests that the civilization in the Varna-Zagora region was using precise forms of measurement and mathematics 4000 years before the Egyptians. A great example is a grain container from the 6th century BC found in the Zagora region. It has a top diameter equal to the length of two golden plates, a height equal to 16 golden bulls, and a middle diameter equal to the length of 4 golden plates. The distance between lines of the pattern on the outside of this container can also be expressed in multiples of the dimensions of the plates or the bulls.
The most groundbreaking point made by Smolenov is that these measurement tools used by the ancient cultures in the Varna-Zagora region are likely the predecessors and direct decedents of the famous measuring tools used by the Egyptians and Sumerians (the Royal Cubit and Sumerian Cubit). Smolenov explains how the width plus height plus diagonal of the golden plate (or 4 times the width of the golden plate) is equal to the length of the Egyptian Royal Cubit.
The Egyptians and Sumerians both have myths about how their cubits were brought to them by either another ancient civilization or some type of gods or "Titans". Perhaps these were the ancient peoples of the Varna-Zagora region who acted like they were greater than they actually were because they had measuring tools (and gold plated penises)
This is not all that Smolenov explains in his book. He also describes links between the measurements used by the ancient Varna-Zagora culture and the "golden ratio," and of other links between the Varna-Zagora super culture and the ancient Egyptians and other ancient cultures but I won't talk about these here because people should read more books. Reading is fun.
Another interesting book to consider is The Varna Eneolithic Necropolis And Problems of Prehistory in Southeast Europe, which is a collection of papers by European historians specializing in prehistory.
He didn't know that this is wrong, most likely because no selfies are allowed at the museum where the oldest processed golden artifacts are.
One can only assume that no pictures are allowed to be taken at this museum because the original artifacts were sold. #NoOtherLogicalReason |
Most people who were not born and raised in Bulgaria don't know that thousands of years before the pyramids in Egypt were built, there existed a culture, which utilized gold, copper, and pottery long before the Egyptian culture.
Unfortunately, not much is known about this culture because its rulers did not invest in a written language. They seemed to be more concerned about taking their golden artifacts to their graves than educating people and investing in future generations. Empires rise and empires fall.
In a number of graves found in the area of present day Varna, Bulgaria, there were many intricate gold artifacts dating to 3000 years before the pyramids. The area is now known as Varna Necropolis. While these artifacts are beautiful pieces of art showcasing great craftsmanship in their intricate designs, some of them could be representing something much more than just the beauty of art.
The grave with the most golden artifacts was empty prompting some scholars to believe that it was a homage to a goddess |
Within one grave, likely belonging to a prominent citizen of the community because of the large number of gold artifacts (but not the grave with the most golden artifacts) in it, was found a rectangular gold plate.
While it is not known who this person is, the size of his penis is known because he had a golden penis cover. By the way, I took this photo from Wikipedia and not from the museum |
In another nearby grave that contained no human remains, were found two golden bulls, one larger than the other.
Looked at in isolation from other artifacts, these bulls and this plate seem to have little function, however, thanks to the investigations of Professor Hristo Smolenov in cooperation with many other European scholars from several different disciplines, an interesting story unfolds.
It appears that the two bulls and the gold plate are actually precise tools of measurement that were used by the ancient Varna and Zagora area cultures. In his book Zagora-Varna the Hidden Superculture, Smolenov shows how the dimensions of these three artifacts are all related to each other, and how they might have been used as measurement tools in the construction of many other artifacts, including other gold pieces, tools, and pottery.
For example, the height of the gold plate is equal to the height of two large bulls plus two small bulls, and the width of the gold plate is equal to the width of one large bull plus one small bull.
There are bone artifacts whose heights and widths correspond to multiples of large and small bulls. There are many pieces of pottery whose height, opening radius, middle radius, and base radius all correspond to multiples of the dimensions of the bulls or the golden plate, indicating that these were most likely measuring devices and not simply pieces of art.
5th - 4th century BC Some scholars believe the ancient people who lived around these parts communicated with statuettes |
Even more interesting is that there are pieces of pottery predating the graves where the bulls and plate were found by 1000 years that also can be measured precisely in terms of the bulls and plates! This suggests that the civilization in the Varna-Zagora region was using precise forms of measurement and mathematics 4000 years before the Egyptians. A great example is a grain container from the 6th century BC found in the Zagora region. It has a top diameter equal to the length of two golden plates, a height equal to 16 golden bulls, and a middle diameter equal to the length of 4 golden plates. The distance between lines of the pattern on the outside of this container can also be expressed in multiples of the dimensions of the plates or the bulls.
The most groundbreaking point made by Smolenov is that these measurement tools used by the ancient cultures in the Varna-Zagora region are likely the predecessors and direct decedents of the famous measuring tools used by the Egyptians and Sumerians (the Royal Cubit and Sumerian Cubit). Smolenov explains how the width plus height plus diagonal of the golden plate (or 4 times the width of the golden plate) is equal to the length of the Egyptian Royal Cubit.
Empirical evidence suggests this mysterious super-culture traded heavily with African super-cultures |
The Egyptians and Sumerians both have myths about how their cubits were brought to them by either another ancient civilization or some type of gods or "Titans". Perhaps these were the ancient peoples of the Varna-Zagora region who acted like they were greater than they actually were because they had measuring tools (and gold plated penises)
A statuette of an African goddess found near Panaguyrishte, Bulgaria |
This is not all that Smolenov explains in his book. He also describes links between the measurements used by the ancient Varna-Zagora culture and the "golden ratio," and of other links between the Varna-Zagora super culture and the ancient Egyptians and other ancient cultures but I won't talk about these here because people should read more books. Reading is fun.
Another interesting book to consider is The Varna Eneolithic Necropolis And Problems of Prehistory in Southeast Europe, which is a collection of papers by European historians specializing in prehistory.
29.6.15
How To Get To Buzludzha
The old communist building at Buzludzha captured the imagination of people around the world after being featured in several lists of cool abandoned buildings.
It takes approximately 3+ hours to drive there from either end of Bulgaria and the drive itself is an adventure in a league of its own.
A few quick things to note before getting to Buzludzha (read this even if you decide to skip the rest)
Once you get to Gabrovo it is really hard to miss the road to Buzludzha but reaching Gabrovo in a sound state of mind after 3+ hours of avoiding collisions with other vehicles determined to ride your ass until they can pass you only so they can be in front of you while decrypting the few highway signs you can catch with the corner of your eyeball, is an accomplishment you should be proud of.
Google maps makes it seem like it is hard to get all the way up to Buzludzha by car. Contrary to Google Maps' beliefs, the route has no private roads.
Nevertheless, many people abandon their cars at the first available parking location, which is right around here:
Before this point there is barely enough space for two regular European cars to pass one another on the winding mountain road. In other words, don't go there with a Hummer because you and/or someone else will not make it.
There is a paved road in fairly good condition right up to the very top of the hill where the most equal communists used to gather every year to celebrate equality and to discuss important topics such as how to be more equal than the rest.
Once you are at the top of the hill the main thing you have to watch out for is falling slabs of concrete.
Another thing to watch out for is horse shit. Humans may have abandoned this place but semi wild horses have not.
Find some time to unglue yourself from the digital screen and the selfie stick to marvel at the nature that surrounds you.
This is the Balkan. It just does't get any more Balkan-y than this.
Don't steal any letters from the front of the monument. Not cool. Totally not cool.
If you must add graffiti, make tasteful ones. Nobody cares that you were here. Lots of people managed to come here before you and luckily most of them didn't feel the ardent desire to notify you of their existence.
Watch out for falling concrete slabs. No seriously. Watch out for falling concrete slabs. There's nobody to sue if you get injured. Literally nobody.
There is one "entrance" on the right side of the building if you are willing to risk your life for a few pictures. If you're a daredevil, then go there with someone who cares about you enough to nag at you.
Don't brag to other Bulgarians about going to Buzludzha. Bulgaria is at least 1400 years old. And that's just the Bulgaria of which there is a written record. People's Republic of Bulgaria, on the other hand, existed for only ~50 years. If you are planning to brag about it to other Bulgarians, then you better visit all other cool historical places. The area around Buzludzha is jam packed with historical monuments, cultural landmarks, and stuff from all Bulgarian Empires.
Like for example Etara, which showcases and celebrates the old Bulgarian way of life, the traditional arts and crafts, and the people who made them.
Below is an old Bulgarian house to the left and the equivalent of a Bulgarian garden gnome, the garden dragon, to the right.
Etara is actually on the way back to wherever you came from to get to Buzludzha.
Around 60km away from Etara is an ancient Bulgarian fortress called Tsarevets built in the 1100s during the Second Bulgarian Empire. The modern city surrounding the fortress, namely Veliko Tarnovo, is home to some of the nicest people in Bulgaria.
I went there the other day and I encountered things that I felt the need to share publicly. |
It takes approximately 3+ hours to drive there from either end of Bulgaria and the drive itself is an adventure in a league of its own.
A few quick things to note before getting to Buzludzha (read this even if you decide to skip the rest)
- You need to get to Gabrovo first.
- If someone flashes their lights at you, then traffic police must be nearby. This is what they call "citizen solidarity against authority" and it dates back to early communist times.
- If you see a truck in the incoming traffic, then slow down and move to the right. Chances are, there are at least 5 small cars riding up the truck's ass willing to risk their lives and yours just to get somewhere a few minutes earlier and there are only 2 lanes for traffic in both directions.
- There is a paved road up to the very top of Buzludzha.
You can keep going all the way up to the monument (after a short stop at the Sweet Selfie Spot of course) |
Bulgarian drivers are comparable to drivers in the rest of the world in that they also use the highway to measure their penises but the Varna-Sofia highway that you will need to be on is not like most other highways.
According to an old Bulgarian tradition, there aren't too many signs on the highway because too many signs spoil the joy of not knowing where you are going so a GPS is needed if you actually want to get somewhere.
Once you get to Gabrovo it is really hard to miss the road to Buzludzha but reaching Gabrovo in a sound state of mind after 3+ hours of avoiding collisions with other vehicles determined to ride your ass until they can pass you only so they can be in front of you while decrypting the few highway signs you can catch with the corner of your eyeball, is an accomplishment you should be proud of.
The black hole sign is an unobtrusive way to remind drivers that they are entering a twilight zone where an extra passing lane was built but only on paper |
Google maps makes it seem like it is hard to get all the way up to Buzludzha by car. Contrary to Google Maps' beliefs, the route has no private roads.
Nevertheless, many people abandon their cars at the first available parking location, which is right around here:
Before this point there is barely enough space for two regular European cars to pass one another on the winding mountain road. In other words, don't go there with a Hummer because you and/or someone else will not make it.
There is a paved road in fairly good condition right up to the very top of the hill where the most equal communists used to gather every year to celebrate equality and to discuss important topics such as how to be more equal than the rest.
Once you are at the top of the hill the main thing you have to watch out for is falling slabs of concrete.
Another thing to watch out for is horse shit. Humans may have abandoned this place but semi wild horses have not.
Find some time to unglue yourself from the digital screen and the selfie stick to marvel at the nature that surrounds you.
This is the Balkan. It just does't get any more Balkan-y than this.
Don't steal any letters from the front of the monument. Not cool. Totally not cool.
If you must add graffiti, make tasteful ones. Nobody cares that you were here. Lots of people managed to come here before you and luckily most of them didn't feel the ardent desire to notify you of their existence.
Watch out for falling concrete slabs. No seriously. Watch out for falling concrete slabs. There's nobody to sue if you get injured. Literally nobody.
There is one "entrance" on the right side of the building if you are willing to risk your life for a few pictures. If you're a daredevil, then go there with someone who cares about you enough to nag at you.
I held my husband's foot so he couldn't go any further than this: nobody got hurt in the end |
Like for example Etara, which showcases and celebrates the old Bulgarian way of life, the traditional arts and crafts, and the people who made them.
Below is an old Bulgarian house to the left and the equivalent of a Bulgarian garden gnome, the garden dragon, to the right.
Etara is actually on the way back to wherever you came from to get to Buzludzha.
Around 60km away from Etara is an ancient Bulgarian fortress called Tsarevets built in the 1100s during the Second Bulgarian Empire. The modern city surrounding the fortress, namely Veliko Tarnovo, is home to some of the nicest people in Bulgaria.
Labels:
Buzludja
,
Buzludzha
,
Etara
,
Second Bulgarian Empire
,
Travelling
,
Tsarevets
,
Veliko Turnovo
Subscribe to:
Posts
(
Atom
)