help me in primmitive root

[feda]

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 : ";
cin>>a;
long int k ;
int s=1 ;
int i=1;
while (s>0 && s<q && i<q )
 {
	k=pow(a,i);
	cout<<"k="<<k<<endl;
	s=k%q;
	cout<<"s="<<s<<endl;
	i++;
	}

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

	}

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

so if one can help me , i will be thankx

[prog-bman]

Code Tags!

[murschech]

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.