Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created January 26, 2018 04:51
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jianminchen/f4c054feeecc2d4d0925f7dee6187dd7 to your computer and use it in GitHub Desktop.
Save jianminchen/f4c054feeecc2d4d0925f7dee6187dd7 to your computer and use it in GitHub Desktop.
Encryption and decryption analysis, correction on unknow X sum analysis
Constraints:
string s with length length, s[0] = 'c', s[1] = 'r'
Encryption(s[0]) = (char)s[0] + 1 - refer to line 56
Encryption(s[1]) = s[1] + Encryption(s[0]) - x1 * 26
Encryption(s[2]) = s[2] + Encryption(s[1]) - x2 * 26
Encryption(s[i]) = s[i] + Encryption(s[i - 1]) - xi * 26 -> a - z, a ascii value 97
= 1 + s[0] + s[1] +...+ s[i] - (x0 + x1 + x2 +...+ xi) * 26 --- formula, need to find s[i]
we denote sumSource = s[0] + s[1] + ...+ s[i] -> SumOfSource
sumUnknownX = x0 + x1 + x2 + ... + xi -> it will O(n)
s[i] = Encryption(s[i]) - 1 - SumOfSource(0->i - 1) + sumUnknownX * 26
Time complexity: for each char, one addition, one subtraction, sumUnknownX * 26 ->
while loop each time add 26 -> sumUnknownX -> n * 3, O(n^2) -> O(n)
-1000 -> 97 - a, number + (97 - number)/ 26 * 26
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment