3. КТО. Применение к открытию сейфа в банке

Бенджамен Франклин (Franklin) однажды сказал: «Трое могут хранить тайну, если двое из них мертвы». В этом параграфе мы изучаем безопасную систему допуска живых к секретным сведениям, основанную на китайской теореме об остатках. Представьте себе следующую ситуацию

Пусть -попарно взаимно простые числа, такие, что .Пусть S- произвольное целое число с условием M<S<N и - остатки от деления S на .

Предположим, далее, что в некотором банке работают n кассиров. Кассир с номером i знает пару чисел .Для открытия сейфа необходимо знать ключевое число S. Докажем, что любые k кассиров смогут открыть сейф, но никакие (k-1) кассиров не смогут это сделать. Действительно, пусть собрались кассиры с номерами , тогда им известен набор чисел По КТО можно найти такое число , что . Так как, то a=S (ввиду единственности решения этой системы сравнений по модулю) и ключевое число найдено, т.е. сейф можно открыть. Если собрались (k-1) кассиров, то они знают пары чисел. По КТО они могут найти такое целое число b, что и , т. е. b?S. Таким образом, b не является искомым ключом к открытию сейфа.

В качестве конкретного примера можно рассмотреть числа : и,например, S=4001. Каждый из пяти кассиров знает одну из пар чисел (5,9), (1.10), (32,49), (32,53),(48,59).

Из предыдущего следует, что любые три кассира смогут найти ключ (равный S=4001) и открыть сейф, но никакие два не смогут этого сделать.