ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Common Board

BigInteger.isProbablePrime
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.