Created
January 26, 2018 04:51
-
-
Save jianminchen/f4c054feeecc2d4d0925f7dee6187dd7 to your computer and use it in GitHub Desktop.
Encryption and decryption analysis, correction on unknow X sum analysis
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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