Stigius's blog

By Stigius, 9 years ago, translation, In English

As many of you know, call to BigInteger.isProbablePrime in java solutions at accm.timus.ru 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", which has the following 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. All submits that had "Restricted Function" verdict were rejudged, 44 of them got Accepted.

Read more »

 
 
 
 
  • Vote: I like it
  • +50
  • Vote: I do not like it