help me in primmitive root

•

What is DaniWeb IT Discussion Community?

You're currently browsing the C++ section within the Software Development category of DaniWeb, a massive community of 423,880 software developers, web developers, Internet marketers, and tech gurus who are all enthusiastic about making contacts, networking, and learning from each other. In fact, there are 4,185 IT professionals currently interacting right now! Registration is free, only takes a minute and lets you enjoy all of the interactive features of the site.

Join our community!

Please support our C++ advertiser: Programming Forums

Thread Tools Display Modes

Views: 1473 | Replies: 2

•

Join Date: Apr 2005

Location: German

Posts: 5

Reputation: feda is an unknown quantity at this point

Rep Power: 0

Solved Threads: 0

feda

Offline

Newbie Poster

help me in primmitive root

May 26th, 2005

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

Help with Code Tags

(Toggle Plain Text)

#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

•

Join Date: Nov 2004

Location: Tucson, Az

Posts: 107

Reputation: prog-bman is an unknown quantity at this point

Rep Power: 4

Solved Threads: 2

prog-bman

Offline

Junior Poster

Re: help me in primmitive root

May 26th, 2005

Code Tags!

Join me on IRC:
Server: irc.daniweb.com
Channel: #C++
Chat Via:
http://daniweb.com/chat/minichat.php
or
Your favorite IRC client.

•

Join Date: Dec 2004

Location: Allentown, PA

Posts: 60

Reputation: murschech is an unknown quantity at this point

Rep Power: 4

Solved Threads: 1

murschech

Offline

Junior Poster in Training

Re: help me in primmitive root

May 30th, 2005

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.