hi ,
i need function to calculate primitive root for prime q
that if i choose prime number q
then a which is primitive must satisfy that
a%q ,(a pow 2 )%q , ...... (a pow i )%q = distinct integers betwwen 1 & q-1
that 1<i < q-1

and i wrote this code but it does not work correctly

#include <iostream.h>
#include <math.h>

 main () {

int q ;   int a;
cout<<"q : ";
cin>> q ;
cout<<"a : ";
long int k ;
int s=1 ;
int i=1;
while (s>0 && s<q && i<q )

	if ( i==( q))
	cout<<"it is primitive "<<endl;
	cout<<"it is not primitive ";


<< moderator edit: added [code][/code] tags >>

so if one can help me , i will be thankx

There are a number of problems with your program. The main one is that, while it prints out a lot of stuff that you don't need to see, it never performs the tests it's supposed to. Where do you test to see whether the i numbers a, a^2, a^3...a^i are distinct mod q? A seconary point is that the pow function here is not a good idea. Also, you should compute powers mod q, that is, instead of a^i you should work with (a%q)^i. This will avoid overflow for large values of q and a.

Actually, I'd guess that your problem is with the algorithm rather than the code. Why don't you try some small cases, like q=3 or q=5 by hand? When you can do those I think you'll be able to write the code.

This article has been dead for over six months. Start a new discussion instead.