ENG  RUSTimus Online Judge
Online Judge
О системе
Часто задаваемые вопросы
Новости сайта
Архив задач
Отправить на проверку
Состояние проверки
Исправить данные
Рейтинг авторов
Текущее соревнование
Прошедшие соревнования
вернуться в форум

Общий форум

Послано ...†.†.†... Stigius ...†.†.†... 23 июл 2012 22:45
As many of you know, call to BigInteger.IsProbablePrime in java lead to "Restricted Function" verdict. Today I decided to resolve this problem.
When I started reading BigInteger.java, I found that "isProbablePrime" method calls "primeToCertainty" method and passes null as "random" parameter. This null is passed to "passesMillerRabin".
"passesMillerRabin" has the following lines of code:

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

Since "rnd" is actually null, getSecureRandom is called. It has following logic:

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

That is when called for the first time, it initializes staticRandom with java.security.SecureRandom, in all the following calls - returns cached object.
Call to java.security.SecureRandom is the source of all problems. Since it is "secure", it uses a lot of information to initialize, including current time and ip address of machine it is run at. Of course, all attempts to get information about network configuration are blocked, so this caused "Restricted Function" verdict. Moreover, when we tried to allow all required calls, we found out that due to some strange problems such initializing took about five seconds. So we decided to change BigInteger class a bit to use usual Random with some predefined seed instead of SecureRandom. It solved all problems and now isProbablePrime works as it should. Rejudge of all submits that had "Restricted Function" verdict is now in progress and will be finished in few hours.

tl;dr: BigInteger.isProbablePrime now works. Be happy.