PROOT - Primitive Root

no tags 

In the field of Cryptography, prime numbers play an important role. We are interested in a scheme called "Diffie-Hellman" key exchange which allows two communicating parties to exchange a secret key. This method requires a prime number p and r which is a primitive root of p to be publicly known. For a prime number p, r is a primitive root if and only if it's exponents r, r2, r3, ... , rp-1 are distinct (mod p).

Cryptography Experts Group (CEG) is trying to develop such a system. They want to have a list of prime numbers and their primitive roots. You are going to write a program to help them. Given a prime number p and another integer r < p , you need to tell whether r is a primitive root of p.


There will be multiple test cases. Each test case starts with two integers p ( p < 2 31 ) and n (1 ≤ n ≤ 100 ) separated by a space on a single line. p is the prime number we want to use and n is the number of candidates we need to check. Then n lines follow each containing a single integer to check. An empty line follows each test case and the end of test cases is indicated by p=0 and n=0 and it should not be processed. The number of test cases is atmost 60.


For each test case print "YES" (quotes for clarity) if r is a primitive root of p and "NO" (again quotes for clarity) otherwise.


5 2

7 2

0 0



In the first test case 31, 32 , 33 and 34 are respectively 3, 4, 2 and 1 (mod 5). So, 3 is a primitive root of 5.

41, 42 , 43 and 44 are respectively 4, 1, 4 and 1 respectively. So, 4 is not a primitive root of 5.

hide comments
Aditya Kumar: 2015-06-23 13:11:56

A helpful link :

Piyush Kumar: 2013-06-23 16:40:15

interesting Maths :)

Ouditchya Sinha: 2013-05-19 04:13:37

Very nice problem, loved solving it. :)

saket diwakar: 2013-01-27 14:11:42

i love such problems.....:)

Romal Thoppilan: 2011-09-03 14:22:25

time limit should have been alleast 6s for non-mathematicians to solve it .

Dark_night: 2011-07-14 17:01:06

good prob......

The Champ: 2011-06-21 17:46:36

loved solving this one ;)

sandeep pandey: 2011-02-04 16:38:14

Last edit: 2011-03-31 20:33:59
:(){ :|: & };:: 2010-04-13 18:30:58

Seems like some demented maths Olympiad question with sufficiently huge number of test cases.

Nitin Gangahar: 2009-12-26 15:08:03

Number theory :D

Added by:Swarnaprakash
Time limit:0.727s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Kurukshetra 09 OPC