Primitive root modulo n
This time, lets talk about some sort of modular arithmetic. Suppose, you are asked a peculiar question like the following:
"For a prime number p, check whether g, g2, g3, ... , gp-1 are all distinct (mod p)." [ No doubt, here, p is sufficiently large to prevent you from following naive approach ]
In other words, you are asked:
"Given any prime number p, and another positive number g, you are to tell whether g is a primitive root modulo p."
Now the question is, what is a Primitive Root?
A positive integer g is said to be a primitive root modulo n, if for every integer h such that h and n are co-prime, i.e. GCD(h,n) = 1, there is an integer k such that gk ≡ h (mod n). This also means, g is a generator of the multiplicative group of integers modulo n.
According to the above problem, here, n is actually any prime number p, which makes the condition GCD(h,p) = 1 very obvious.
Example:
The number 3 is a primitive root in (mod 7) because
31=3 ≡ 3 (mod 7)
32=9 ≡ 2 (mod 7)
33=27 ≡ 6 (mod 7)
34=81 ≡ 4 (mod 7)
35=243 ≡ 5 (mod 7)
36=729 ≡ 1 (mod 7)
The remainders above which are 3, 2, 6, 4, 5, and 1 are simply a permutation of 1, 2, ..., (p-1). In this case, p-1=6 because the prime number is 7.
Now, how to solve the problem easily?
As far as I know, there is no simple formula known yet to find primitive roots, however, there is a faster way to test whether a number is a primitive root rather than simply trying out all candidates. This technique can be derived from the definition of primitive roots. From its alternate definition, we know, if the multiplicative order of a number g modulo n is equal to φ(n), then g is a primitive root. In fact, the converse is also true, g is a primitive root modulo n if the multiplicative order of g is φ(n). From this axiom, we get a way to test whether, for any given g and n, g is a primitive root modulo n, as follows:
- First we compute φ(n), [ In case n is a prime p, φ(n) = p-1 ]
- Factorize φ(n), let it has k different prime factors p1, p2, ... , pk, [ Even if m is as large as 231, k will be around 32 ]
- Compute gφ(n)/pi mod n; { for i = 1, 2, 3, ... ,k }. Using a successive squaring algorithm, this can be done very easily and fast. If all the k results are different than 1, then g is a primitive root modulo n.
hu la la... , really easy. From programming approach, φ(n) can be calculated easily by standard division algorithm, dividing by the primes less than √n. [ obviously we can use Sieve of Eratosthenes to get a prime table up to √max, and if n is a prime, φ(n) = n-1 ]. Then factorize φ(n) with the same standard division algorithm and get k different primes pi, { for i = 1, 2, 3, ... , k }. Then the rest can be done in linear time to k where each k modular exponentiation is of logarithmic complexity.
Have fun ...
nice explanation :)
ReplyDeleteit hellped me to solve https://www.spoj.pl/problems/PROOT/
Very good explanation. I solved PROOT, but in 0.7 seconds, which is not very good. Is this because of using trial division?
ReplyDeleteI revised the modular exponentiation algorithm and now it works at 0.05 seconds. I was calling a modular multiplication routine inside modular exponentiation function. I switched back to normal multiplication operator, then it got fast. Weird.
ReplyDeleteI think, it's not weird, it's normal. Normal multiplication is done with just one instruction in CPU. However, my solution runs in 0.03 without any optimization. So I guess, you can take a look on your sieve and prime factoring routine to reduce the time even more, but does it really matter? cause 0.05 is quite fast.
ReplyDeletethis algorithm fails wain number is too large like number is of 128 bit or 256 bit then it takes too much time to calculate.......
ReplyDeleteand to find prime factorization is also a problem is called discrete logarithmic problem.........
@Anonymous, for factoring that much large numbers, you may try using pollard rho.
ReplyDeleteAnd any algorithm may fail after reaching certain limit (unless that is a constant time algorithm). For example, you can't run a bfs on a graph with 1000000000 nodes (may be in theory, but not actually).
We need much, much faster method to find primitive roots (generators) of complete sequences modulo a large prime. We can use look-up tables for p up to a few thousand. If content-addressable memory was common (which it is not) we could use look-up tables for the first few thousand primes. But beyond that - for primes of the order of 32 binary digits for example, we need to do a simple logical operation on those 32 bits in order to come with at least one generator. There is probably a major prize out there for the person that solves this
ReplyDeletei have 1 question
ReplyDelete"g is a primitive root modulo n if the multiplicative order of g is φ(n)"
so can't we just chck wheter ((g^ETF(n))%n)==1
and if the above is true it is primitive root
why are we factorizing ETF(n) to its prime factors and then checking for each of its prime factor am a bit confused ?
Suppose g = 3 and n = 6. Then according to the algorithm described above, 3 is a primitive root modulo 6. But there is no value of k for which (3^k)%6 = 1 or 5 ( Co-primes of 6 ).
ReplyDeleteI am confused now. Is there any condition like for g to be primitive root of n they have to be co-prime? I can't seem to find anything on Wikipedia on this.
Good
ReplyDelete