Thread: Tell the Prime number

(1st question)
We need to guess a Prime number between 2 to 10^9(inclusive) in M questions.
Here's how it works:
- We can give the computer a number x(1 to 10^9).the computer replies with x^2%P.
- We need to tell the value of P.

(2nd question)
The modified question is:
- The computer could change the value of P, whenever it wants. But, the changed value also satisfies the Above asked queries and their results.

The number of queries of M, should be less than equal to 5. for first part, and 2 for 2nd question.

I know We need to apply fermat's little theorem on it. but due to the large range am getting lost most of the times. I can't really think how to really approach this. Please guide me a little.
Thank you.

If anyone could help even for 1st Question, it would be very helpful.

Originally Posted by stahta01

This is not an homework service; post what you are having trouble with an someone will likely help you.
I will not likely be that person; because I have no idea what fermat's little theorem is about.

Edit: It is possible that you gave enough info for the ones who knows fermat's little theorem; but, I doubt it.

Tim S.

I am not trying to get my homework done here. Just needed help in a topic which I am weak in. That's why I added in the end to guide me. I have been trying out this problem for quite a while now, and can't find enough information online to help me with this, that's why I posted it here.

Sorry for not providing info about the topic I mentioned. Fermat's little theorem - GeeksforGeeks Here's what I am talking about. Any help is appreciated.
Thank you.

but , that's not the issue, my problem is with guessing the prime number in such a huge range. I don't know which numbers to give the computer and then get x^2%P, I can ask this M times(less than equal to 5), but I don't understand how this will help me get P. or which numbers to ask the computer to get P.

I did this too . Maybe I am not getting it, but I tried and I picked up 997. Since M<=5, I don't know which primes to pick. the primes which have their squares less than 997 will give their squares as the remainder. what to do then ?? I have upto 10^9 and like if I start picking up from beginning, I will only see the squares of these primes only. Please help, It's frustrating.