Encryption Validity
Goldman Sachs● EasyFULLTIMEINTERNOAProblem statement
Encryption is the process of converting information algorithmically so that a valid recipient can read the information before it is no longer a valuable secret.
This is its validity period. An attacker has limited processing power and can only test a certain number of keys per second.
This is the instruction count. The size of the universe of keys divided by the instruction count gives the average time to find a message key.
To achieve a balance between the processing power for encryption/ decryption and the strength of the encryption, the validity period of the message must be taken into consideration.
Given the number of keys, a hijacker can test per second, determine if the encrypted information should remain confidential throughout its validity period. Each test will return two items of information as integers:
- Can a hijacker crack the code within the period? (1 if true, 0 if false)
- The strength of the encryption, that is, the number of keys that must be tested to break the encryption.
The strength of the encryption is determined as follows:
- Keys is a list of positive integers,
keys[i], that act as keys. - The
degree of divisibilityof an element is the number of elements in the set keys that are greater than1and are divisors of the element, i.eelement modulo divisor = 0. - The element m that has the maximum number of divisors (or degree of divisibility) in keys is used to determine the strength of the encryption.
- The strength of the encryption is defined as
(the degree of divisibility of m)* 10^5
Function
encryptionValididy(instructionCount: int, validityPeriod: int, keys: int[]) → int[] Complete the function encryptionValidity.
encryptionValidity has the following parameter(s):
int instructionCount: the number of keys the hijacker can test per secondint validityPeriod: the number of seconds the message must be protected.int keys[n]: the keys for encryption/decryption
Examples
Example 1
instructionCount = 1000validityPeriod = 10000keys = [2, 4, 8, 2]return = [1, 400000]The element m that has the maximum number of divisors is 8 ad its degree of divisibility is 4. The encryption strength is 4 * 10^5 = 400,000. The hijacker can perform instructionCount = 1,000 calculations per second. During the total validityPeriod = 10,000 seconds, the hijacker can test 1000 * 1000 = 1000000 = 10^7 keys. Thus, there is sufficient time for the key to be determined and the message decrypted before its validity expires. The first value in the return array is 1 because the message can be decrypted. The return array is [1, 400000] because the hijacker can decrypt the message in time, and the strength of the encryption is 400000.
Constraints
1 <= instructionCount, validityPeriod <= 10^81 <= 1 <= n <= 1051 <= 1<= keys[i] <= 105