До начала четвертьфинала в Екатеринбурге остаётся менее суток. Многие команды уже приехали, зарегистрировались и ждут пробного тура, который у нас по традиции нестандартный и в этом году снова немного поменял формат. Ну а я в свою очередь приглашаю всех желающих отыграть завтра на Тимусе зеркало контеста. Контест будет в стандартном уральском стиле, то есть с долбанутыми графоманскими сказками не совсем шаблонными задачами, где помогает не столько умение кодить стандартные вещи, сколько умение придумывать нестандартные и хитрые подходы к задачам. Начало контеста в 11 утра московского времени, предварительной регистрации не требуется, только наличие аккаунта на тимусе. Монитор онсайта будет как обычно выложен на сайте четвертьфинала.

Как многие знают, вызов BigInteger.isProbablePrime в решениях на java на тимусе приводил к вердикту "Restricted Function". Сегодня я решил разобраться с этой проблемой.

Когда я начал читать исходник BigInteger.java, я обнаружил, что метод "isProbablePrime" вызывает "primeToCertainty" со значением null в качестве параметра "random". Этот null передаётся дальше в метод "passesMillerRabin", который содержит следующий код:

if (rnd == null) {
    rnd = getSecureRandom();
}

То есть, если "rnd" был null, а в нашем случае это именно так, то вызывается "getSecureRandom". У него логика следующая:

private static volatile Random staticRandom;
private static Random getSecureRandom() {
	if (staticRandom == null) {
		staticRandom = new java.security.SecureRandom();
	}
	return staticRandom;
}

То есть когда он вызывается в первый раз, он инициализирует статический объект "staticRandom" с помощью "java.security.SecureRandom", а дальше уже использует этот объект для последующих использований.

Вызов "java.security.SecureRandom" и является корнем всех зол. Поскольку он является "безопасным", то для инициализации он собирает кучу разной информации, включая текущее время и ip-адрес машины, на которой вызван. Это создаёт две больших проблемы. Во-первых, поведение становится недетерминированным. Т.е. при двух запусках программы из-за разной инициализации рандома isProbablePrime может возвращать разные результаты, и, как следствие, меняется весь вывод программы. Это создаёт определённые проблемы при реджаджах. Во-вторых, все вызовы к сетевой подсистеме заблокированы из соображений безопасности, что, собственно говоря, и приводило к получаемому вердикту. Более того, когда мы попробовали разрешить эти вызовы, по непонятным причинам такая инициализация рандома занимала чуть более 5 секунд. Поэтому мы решили пойти по немного другому пути. А именно — вызов SecureRandom мы заменили на обычный Random с некоторым константным сидом и подменили BigInteger.class новым, пропатченным. Это успешно решило обе проблемы и теперь BigInteger.isProbablePrime работает как положено. Все пострадавшие решения уже перепроверены, 44 решения получили Accepted.