25.12.15

Marian Rejewski: A Forgotten Hero

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, or the German encryption machine during WWII, which the German military used to communicate with evil axis troops.

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. In that 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 and Alan Turing and his team.

After the war Rejewski returned to the family that he left in order to save the families of others and became an accountant.

Even I only heard of Rejewski a few years ago when an Australian friend of mine with Polish background posted about Rejewski on his Facebook timeline. Then I took a course called Codebreakers & Codemakers: An Introduction to Cryptography, and I learned more about this remarkable man who appears to be forgotten by the masses he saved.

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 [12, 22, 32, ..., ((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:

a0 = ((n-1)/2)2 mod n
a1 = (a0 + 2*1) mod n
a2 = (a1 + 2*2) mod n
a3 = (a3 + 2*3) mod n
.
.
.
ai = (ai-1 + 2*i) mod n

If ai = 0 then all elements [12, 22, 32, ..., ((n-1)/2)mod n] have been generated

Example: n = 35 so a0 = ((35-1)/2)2 mod 35 = 9 then 
a1 = a0 + 2*1 mod 35 = 9 + 2 = 11, 
a2 = a1 + 2*2 mod 35 = 11 + 4 = 15, 
a3 = 15 + 2*3 mod 35  = 21, 
a4 = 21 + 2*4 mod 35 = 29,
a5 = 29 + 2*5 mod 35 = 4,
a6 = 4 + 2*6 mod 35 = 16, 
a7 = 16 + 14 mod 35  = 30, 
a8 = 30 + 16 mod 35 = 11, 
a9 = 11 + 18 mod 35  = 29, 
a10 = 29 + 20 mod 35 = 14.
a11 = 14 + 22 mod 35 = 1,
a12 = 1 + 24 mod 35  = 25,
a13 = 25 + 26 mod 35 = 16,
a14 = 16 + 28 mod 35 = 9,
a15 = 9 + 30 mod 35 =  4,
a16 = 4 + 32 mod 35 = 1,
a17 = 1 + 34 mod 35 = 0





Note: In this example the set [a0, a1, a2, a3, ..., a16] is equivalent to the set [182 mod 35,192 mod 35, 202 mod 35, 212 mod 35 ..., 342 mod 35], or the set [172 mod 35, 162 mod 35, 152 mod 35, 142 mod 35 ..., 12 mod 35], which is the inverse of the first half of the column at 2 in the exponentiation table of  Z35 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 Zn where n is the product of two distinct odd primes p and q  such that:

a2 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 1515 mod 35
ii) n = 77 a = 22 since 2222 mod 35
iii) n = 55 a = 11 since 1111 mod 35

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. 




10.12.15

2.12.15

Fun With Steganography

I first learned about steganography a long time ago but I never actually played with it in any way until a few days ago when I realized how nice it would be if I could watermark my photographs.

Steganography is defined as "the practice of concealing messages or information within other nonsecret text or data" and in this blog post I intend to show how to hide data in an image at the pixel level, and retrieve it afterwards.

If I want to hide a piece of text in an image I can convert each character of the text into an integer from 0 to however many characters there are in the chosen alphabet, as long as the alphabet consists of less than 255 characters.


For example, the English alphabet has 26 characters and if each character is represented by a digit from 0 to 25 where a is represented by 0, b is represented by 1 and so on, and space is represented by 26, then the phrase "hello world" becomes the array of integers 7, 4, 11, 11, 14, 26, 22, 14, 17, 11, 3


Then I can replace just one channel of particular pixels chosen through a secret key with each integer in the array thus concealing a retrievable text message in a digital format within plain sight!

The pseudo code for the en-steganograph and de-steganograph or ensteg and desteg are as follows:



Ensteg Function
  1. Grab image data
  2. Loop through each pixel until a certain pixel at a certain location is reached according to a given key that specifies the location in a consecutive manner (key must expand and contract and must be smaller than image height/2 and image width/2)
  3. Replace the r channel value in this designated location with the first integer of the message
  4. Point to next integer of the message array
  5. Add a certain specified amount to key 
  6. Repeat 3-5 until the rest of the image
Desteg Function
  1. Loop through each pixel until a certain location is reached according to a decoding key
  2. Grab r value of that pixel and add it to an array
  3. Add a certain specified amount to key
  4. Repeat 1 through 3 until the end of the image
  5. Return array

Hiding and retrieving hidden data from an image at the pixel level is not as easy as it may sound because many image formats use lossy compression systems, which means that the values of the pixel's channels do not remain the same.


For example, the most widely used compression system for JPEG is lossy, and it was "designed to give results acceptably accurate to the human eye whilst providing many-to-one compression"[p.626, S. G. Hoggard, Mathematics of Digital Images]


PHP's GD function imagecreate() uses many-to-one compression that significantly alters the RGB values of each pixel even if the quality option is set to 100. According to S.G. Hoggard, JPEG does include "a system of lossless compression". However, a quick search through stackoverflow suggests that none of the other PHP image libraries include jpeg creation function with lossless compression.


Therefore, jpegs are not the best choice for what I'd like to do. I could still accept any image format and grab the image data from it but upon piecing it all together I must use a format that preserves pixel values. I choose png


Below are the ensteg/desteg functions in PHP.



/* -------------------------------------------------  
 This content is released under the GNU License  
 http://www.gnu.org/copyleft/gpl.html 
 Author: Marina Ibrishimova 
 Version: 1.0
 Purpose: Hide a secret message in an image  
 ---------------------------------------------------- */ 

function ensteg($path, $message, $key, $amount) 
 { 
  if(file_exists($path_to)_img))
  { 
   $im = $path_to_img;
  }
  else{
   return "Image does not exist at specified location";
  }
  $type = strtolower(substr(strrchr($path_to_img,"."),1));
    if($type == 'jpeg') $type = 'jpg';
    switch($type){
     
       case 'gif': $im = imagecreatefromgif($path_to_img); break;
       case 'jpg': $im = imagecreatefromjpeg($path_to_img); break;
       case 'png': $im = imagecreatefrompng($path_to_img); break;
       default : return "Unsupported imagetype!";
    }
            $width = imagesx($im);  
            $height = imagesy($im);
            $i = 0;
            $counter = count($message);
            //loop through each pixel
            for($x = 0; $x < $width; $x++)   
            {  
                 for($y = 0; $y < $height; $y++)   
                 {  
                       $rgb = imagecolorat($im, $x, $y);  
                       $r = ($rgb >> 16) & 0xFF;  
                       $g = ($rgb >> 8) & 0xFF;  
                       $b = $rgb & 0xFF;  
                       $alpha = ($rgb & 0xFF000000) >> 24;  
                        //pixel is of certain height and width according to secret key
                       if($x === ($width - $key) && $y === ($height - $key))
                       {
                        //reset and start repeating msg
                        if($i == $counter){$i = 0;}
                        //add portion of message to r value and move on
                        $r = $message[$i];
                        $i = $i + 1;
                        $key = $key - $amount; 
                        imagesetpixel($im, $x, $y, imagecolorallocate($im, $r, $g, $b));
                       }    
                 }  
             } 
   //lossless even though compression is set to 9
   imagepng($im, 'new_path_to_new_file.png', 9); 
   imagedestroy($im);
   
   $img_url = "new_path_to_new_file.png";    
  
   return $img_url;
   
 }




Original image sans secret message


And the image below has a hidden, retrievable text message in a digital format repeated throughout the image but this is not obvious to the naked human eye.



Image with secret message


To retrieve the hidden data from the message, the following de-steganograph function is required, along with key = 127 and amount = 3


/* -------------------------------------------------  
 This content is released under the GNU License  
 http://www.gnu.org/copyleft/gpl.html 
 Author: Marina Ibrishimova 
 Version: 1.0
 Purpose: Retrieve a secret message hidden with ensteg() 
 ---------------------------------------------------- */ 
function desteg($path, $key, $amount) //bright and sunny
 {
  //path to image generated with ensteg
  if(file_exists($path))
  { 
   $im = "new_path_to_new_file.png";

  }
  else{
   return "Image does not exist at specified location";
  }
  $im = imagecreatefrompng($im);
  $thelong = array();
  
  $width = imagesx($im);  
            $height = imagesy($im);  
        
            //loop through each pixel  
            for($x = 0; $x < $width; $x++)   
            {  
                 for($y = 0; $y < $height; $y++)   
                 {  
                       $rgb = imagecolorat($im, $x, $y);  
                       $r = ($rgb >> 16) & 0xFF;  
                       $g = ($rgb >> 8) & 0xFF;  
                       $b = $rgb & 0xFF;  
                       $alpha = ($rgb & 0xFF000000) >> 24;  
                        //pixel is of certain height and width according to secret key
                       if($x === ($width - $key) && $y === ($height - $key))
                       {
                        $thelong[] = $r;
                        
                        $key = $key - $amount;
                       } 
                 }  
               }
   imagedestroy($im); 
  //returns an array with the message repeated within specified location
  return $thelong; 
 }

29.11.15

Decrypting Abbreviations

I usually post about serious stuff in here but every now and then I like to break the awkwardness with a dick joke or two.

Recently I made the shocking observation that the vast majority of secret agencies have the letter "S" in their names. The "S" typically stands for security but lets just pretend it actually stands for sex.

With this in mind here's a list of decrypted abbreviations of secret agencies:


NSA (USA) - National Sex Agency

CSIS (Canada) - Canadian Sex Is Scheduled (from 8AM to 4PM)

FSB (Russia) - Federal Sex Bureau

MOSSAD (Israel) - Masters Of Sadistic Sex And Domination

ASIS (Australia) - Anal Sex Information Services

MSS (China) - More Sadistic Sex

MOIS (Iran) - More Obstacles In Sex



It would be interesting to compare these agencies to other intelligence agencies that don't have the letter S in their names and see who gets more done.

I suspect that agencies where the number of mathematicians is higher than the number of psychologists probably get more done as well.

p.s. I just like to point out that I feel the same way about all secret service agencies. I have no favourites but I don't expect anyone to believe me since my name ends in -ova.

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


2≡ 1 mod n          and a is the smallest such integer then:
(((n-1)/2) + 1)≡ 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 Zn  is equivalent to the row at 2 in reverse order

Corollary 2: The row at (((n-1)/2) + 1) of the exponentiation table of Zn  can be generated using the following recurrence relation:

an = (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 Zn is equivalent to the row at (n-2) in reverse order.

Corollary 4: The row at (n-1)/2 of the exponentiation table of Zn is can be generated from the row at (((n-1)/2) + 1 in the following manner:

Let ai be an element at the row of (((n-1)/2) + 1 and let bi be an element at the row of (n-1)/2 then:

bi = ai         if i is even
bi = ai - ai-1  if i is odd

Example: Take Z35 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 Z35 .


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:
≡ 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  Z35 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.

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?'

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.

The following theorem, which I first claimed and proved in Types of Exponents suggests something very interesting regarding two types of exponents that can be useful in generating exponentiation tables faster: namely even exponents and odd exponents.

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
= (n2k - 2kn2k + ... - 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

.'.


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 Zn 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 = 1 mod n

(n-1)2 = [(n-1)*(n-1)] mod n
= (n2 - 2n + 1) mod n 
= (n2 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 k2 mod n   since  (n-k)n- 2nk + k2   = 0 + 0 + k2  ksince 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


  (n-k)=  nr  -  rnrnk  + ... - rnkr  + kr  = 0  -  0  + ... -  0 + kr = kr mod n

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...

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:

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:
  1.  Using a cyclic permutation
  2.  Using an algebraic expression
  3.  Using simple addition
  4.  Using double skips
  5.  Using quadruple skips
  6.  Using 18-tuple skips

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.

/* -------------------------------------------------  
 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){indexindex - 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(n2) but there is an algorithm that uses only
O(n log2 n log2 log2 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:
  1.  Using a cyclic permutation
  2.  Using an algebraic expression
  3.  Using simple addition
  4.  Using double skips
  5.  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.

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.


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 greatgrandfather 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


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).

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;
}

Here's the implementation for the above algorithm using a worker that is not overworked now that it is only dealing with integers.

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.  Using a cyclic permutation
  2.  Using an algebraic expression
  3.  Using simple addition
  4.  Using double skips

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 s0=j*j, the element at column 4 is s1 = t*j and so on until either si = 1 or si = j.  A count of the number of "jumps" reveals the order of the element and furthermore if si = j, then the order of the element is odd and if si = 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 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:
  1.  Using a cyclic permutation
  2.  Using an algebraic expression
  3.  Using simple addition
  4.  Using double skips

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 ak = 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).

/* -------------------------------------------------  
 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;
}

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).


/* -------------------------------------------------  
 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:


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 aij in the exponentiation table with i rows and j columns  of Zn when n is the product of 2 distinct primes can be generated as follows:

aij = [(j - 1)(ai-1 + ai-2 + ai-3)] + ai-3  mod n

Below is an algorithm for finding the order of any element of the exponentiation table of Zn 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 Zn if GCD(a, n) = 1 or find a zero divisor of Zn , 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!


19.7.15

Selfie Sticked

Hating on the selfie stick is so cool right now that I decided to show some love and warmth towards this symbol of modern society.

Selfie sticks are an ingenious invention that frees locals from the burden of having to take pictures of tourists while going about their daily lives.

Selfie stick haters don't know what it is like to have to go out of their usual way to avoid rosy cheeked and picture perfect tourists without selfie sticks who beg to have their pictures taken at randomly chosen locations.

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 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.


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.


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?