Member Avatar for 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

  • 3 Contributors
  • 2 Replies
  • 231 Views
  • 5 Days Discussion Span
  • Latest Post Latest Post by murschech

Dani AI

Generated

A concise, reliable test for a primitive root modulo a prime q

A number a is a primitive root mod q exactly when its multiplicative order is q-1. The standard fast test: factor q-1, and for every distinct prime factor r of q-1 confirm that a^((q-1)/r) (mod q) is not 1. If none of those powers equals 1 then a generates the whole multiplicative group and is a primitive root. This avoids computing large a^i directly and is far faster than checking all q-1 powers.

Here is a compact C++ implementation (uses fast modular exponentiation and a simple factorization of q-1):

#include <iostream>
#include <vector>
#include <cstdint>

using ull = unsigned long long;

ull mod_pow(ull a, ull e, ull mod) {
    ull res = 1 % mod;
    a %= mod;
    while (e) {
        if (e & 1) res = (unsigned __int128)res * a % mod;
        a = (unsigned __int128)a * a % mod;
        e >>= 1;
    }
    return res;
}

std::vector<ull> prime_factors(ull n) {
    std::vector<ull> out;
    for (ull p = 2; p*p <= n; ++p) {
        if (n % p == 0) {
            out.push_back(p);
            while (n % p == 0) n /= p;
        }
    }
    if (n > 1) out.push_back(n);
    return out;
}

bool is_primitive_root(ull g, ull p) {
    if (g <= 1 || g >= p) return false;
    ull phi = p - 1;
    for (ull q : prime_factors(phi))
        if (mod_pow(g, phi / q, p) == 1) return false;
    return true;
}

Notes and troubleshooting

  • For small q a simple brute-force approach (track seen residues with a boolean array and iterate x = x*a % q) is easy to implement but O(q).
  • Check q is prime (primitive roots exist for prime moduli) and handle q=2 as a special trivial case.
  • Avoid using pow() from <cmath> for integer powers: it returns floating point and will overflow/round for moderate integers. As hinted, compute all powers modulo q using integer modular exponentiation to prevent overflow and incorrect results.

Recommended Answers

All 2 Replies

Member Avatar for 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.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.