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) и открыть сейф, но никакие два не смогут этого сделать.
- 4.3. Применения китайской теоремы об остатках.
- 4.2. Система сравнений первой степени. Китайская теорема об остатках.
- Тема 28. Греко-китайская теорема об остатках
- 5.1.4 Китайская теорема об остатках
- 2.2.2. Китайская теорема об остатках
- 4.2. Китайская теорема об остатках
- Теорема Безу и её следствие
- Китайская теорема об остатках (теория)
- Китайская теорема об остатках