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

3
Contributors
2
Replies
3
Views
13 Years
Discussion Span
Last Post by 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.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.