1

Here is an algorithm problem that I am trying to solve(It's written in Korean.): https://www.acmicpc.net/problem/10944

If I simply translate the problem, I need to generate a number between 1 and 10,000. The resulting number must be the same as the random number which is generated by the server(a referee)

Is this possible? Can I guess what the system server would generate and Can I match it with my program's result?

I figured out that there are two kinds of way to make a random number in Java.

  1. Random
  2. Math.random()

And I can manipulate(or predefine) the result with Random. And I just think it might be possible to solve the problem.

For example: 

import java.io.IOException;
import java.util.Random;

public class Solution {
    public static void main(String[] args) throws IOException {
        Random rnd = new Random(1);
        System.out.println(rnd.nextInt(10000));

        rnd = new Random(1);
        System.out.println(rnd.nextInt(10000));
    }
}

It shows the same result because the parameter of Random is the same. And I tried with Random. But I couldn't solve that problem.

Like this:

import java.io.IOException;
import java.util.Random;

public class Solution {
    public static void main(String[] args) throws IOException {
        Random rnd = new Random(1);
        System.out.println(rnd.nextInt(10000));
    }
}

And as I remember, Math.random() is generated by system time. But I can't find any information for that. If that's true and it may be possible to solve the problem. Because I can program with the system time and the result will always correspond.

c-an
  • 3,543
  • 5
  • 35
  • 82
  • 6
    Just create a `Random` with a shared seed. – shmosel Jun 26 '18 at 04:10
  • you beat me to it @shmosel ;) – Ilan Keshet Jun 26 '18 at 04:10
  • 1
    I guess I used the shared seed thing. However, I can't solve that problem. Some document says I need to take advantage of the computer’s built-in clock or its entropy. But I have no idea how to do that with Java. The doc is here: https://cdsmith.wordpress.com/2011/10/10/build-your-own-simple-random-numbers/ – c-an Jun 27 '18 at 10:19
  • You can't take "advantage" of the built-in clock, or of any kind of entropy, simply because there's no advantage to be taken from entropy, in the context of this task. The reason why you could pull such a trick at all is because there's no real entropy in a pseudo-random sequence, modulo the initial seed. To the extent to which there would be any entropy to the sequence, you wouldn't be able to guess it reliably. – shinobi Jun 27 '18 at 12:22
  • 1
    As a result, All I can do is submitting my solution and just hope the answer is the same with the result of the server system? – c-an Jun 27 '18 at 12:49
  • Hope is beside the point :) As already proposed more than once, in order for the client to be able to follow the server's sequence, you need server and client to 1) calculate the sequence starting from the same seed and 2) be looking at the same sequence member at any given time. – shinobi Jun 27 '18 at 19:09

1 Answers1

0

Your question has the same basis as the google authenticator implementation. Most RSA tokens or 2factor authentications use this method to authenticate the user. As mentioned in the comments use a common seed to solve the problem

Garun
  • 22
  • 6
  • 1
    Could you explain in detail? I am trying to figure out what the seed is. I guess it is the parameter of Random constructor, isn't it? What are common seeds and shared seed? Isn't that meaning of taking advantage of the parameter? https://stackoverflow.com/questions/22530702/what-is-seed-in-util-random?lq=1 – c-an Jun 26 '18 at 05:57
  • Here is a detail on the seed you were looking for https://cdsmith.wordpress.com/2011/10/10/build-your-own-simple-random-numbers/ – Garun Jun 27 '18 at 05:24
  • 1
    Thanks, but It doesn't show how to use the common or shared seed. I don't know how to take advantage of the computer’s built-in clock or its entropy with Java. @Garun – c-an Jun 27 '18 at 10:16