과도한 무작위화 timer 20s memory 1024MB

Note: 이 설명에서 어떤 것이 무작위로 선택된다고 할 때마다, "가능한 모든 경우 중에서 균등한 확률로 선택되며, 다른 모든 선택들과 독립적으로 선택된다"는 뜻이다.

Banana Rocks Inc.라는 회사가 프리미엄 클라우드 기반 난수 생성 서비스를 막 만들었고, 이는 새로운 난수의 표준이 될 운명이다.

원래 설계는 이랬다: 서버들의 한 그룹이 최대 U자리의 양의 정수 M 하나로 이루어진 요청을 받으면, 1부터 M까지(포함) 범위의 정수를 무작위로 하나 골라 응답한다. 하지만 출력 숫자를 보통처럼 0부터 9까지의 숫자로 쓰는 대신, 서버들은 "과도하게 무작위화"(overrandomized)되었다. 각 서버는 숫자를 표현하는 데 사용할 10개의 서로 다른 영문 대문자 집합을 무작위로 고르고, 그 글자들을 0부터 9까지의 서로 다른 값에 대응시키는 무작위 매핑을 가진다.

현재 상황의 형식적 설명은 다음과 같다. 각 서버는 정확히 10개의 서로 다른 영문 대문자로 이루어진 숫자 문자열(digit string) D를 가진다. 이 숫자 문자열은 글자와 10진수 숫자 사이의 매핑을 정의한다. 왼쪽에서 j번째 문자(0부터 세었을 때)는 값이 j인 10진수 숫자를 나타낸다. 예를 들어 D가 CODEJAMFUN이라면 C는 숫자 0, O는 숫자 1, N은 숫자 9를 나타낸다. 숫자 379009는 그 숫자 문자열을 사용할 때 EFNCCN으로 인코딩된다.

정수 매개변수 M_i로 i번째 질의를 받으면, 서버는:

• 1부터 M_i까지(포함)에서 정수 N_i를 무작위로 하나 고르고,
• D의 왼쪽에서 j번째 문자(0부터 세었을 때)를 값이 j인 숫자로 사용하여 N_i를 (선행 0 없이) 10진수 문자열로 적은 뒤,
• 그 결과 문자열을 응답 R_i로 반환한다.

우리는 각 서버의 비밀 숫자 문자열 D를 복구하는 데 쓸 수 있다고 믿는 데이터를 수집했다. 각 서버에 10⁴번의 질의를 보냈다. 각 질의에서 우리는 1부터 10^U - 1까지(포함) 범위에서 M_i 값을 무작위로 선택했고, 응답으로 최대 U개의 영문 대문자로 이루어진 문자열 R_i를 받았다. 우리는 (M_i, R_i) 쌍들을 기록했다. 이 기록들을 새 저장 장치로 옮기는 과정에서, 일부 서버의 기록에 들어 있던 모든 정수 M_i 값이 손상되어 읽을 수 없게 되었다.

각 서버의 숫자 문자열 D를 찾아 줄 수 있겠는가?