Thread: Tell the Prime number

  1. #1
    Registered User
    Join Date
    Nov 2018
    Posts
    32

    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.

  2. #2
    Registered User
    Join Date
    Nov 2018
    Posts
    32
    If anyone could help even for 1st Question, it would be very helpful.

  3. #3
    Registered User
    Join Date
    May 2009
    Posts
    3,629
    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.
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

  4. #4
    Registered User
    Join Date
    Nov 2018
    Posts
    32
    Quote Originally Posted by stahta01 View Post
    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.

  5. #5
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,325
    > 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.
    So practice with smaller numbers to begin with.

    The thing about mathematical theorems is that they do not care at all about how big the numbers are.

    However, real machines have very finite ranges on the numbers they can represent.

    You need to recognise the possibility that your only real difficulty is "overflow" not "algorithm".

    Oh, and your link has source code, and also a comment about overflow.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  6. #6
    Registered User
    Join Date
    Nov 2018
    Posts
    32
    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.

  7. #7
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,325
    So it's a maths question then.

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

    So you start with a paper exercise with a few chosen prime numbers (https://primes.utm.edu/lists/small/10000.txt)

    Pick a P from that list.
    Pick up to 5 numbers less than P, each one is x
    Calculate x^2%P

    Spot the pattern which emerges.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  8. #8
    Registered User
    Join Date
    Nov 2018
    Posts
    32
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. calculating if a number is a prime number or not
    By cooper1200 in forum C Programming
    Replies: 23
    Last Post: 06-08-2019, 11:58 AM
  2. Replies: 3
    Last Post: 12-02-2014, 10:11 AM
  3. Is a number Prime or not prime?
    By ImaCnoob in forum C Programming
    Replies: 27
    Last Post: 10-08-2012, 11:47 PM
  4. largest number prime number that can be produced...
    By ElemenT.usha in forum C Programming
    Replies: 8
    Last Post: 02-17-2008, 01:44 AM
  5. Replies: 3
    Last Post: 03-29-2005, 04:24 PM

Tags for this Thread