You wrote it in lecture 6 slide 13. I can't find out why, besides the test that has shown it to be in P.
my idea:
given m, a primitive root g modulo m will show that m is a power of a prime… verifying that g is a primitive root is O(log^3(m)) (i think.. it's polynomial in size of input, anyway).
now that we know m is a power of a prime, we want to know that the power is 1. if the power is k, and m=p^k, then we know that p>2 and that k<log_p(m)<log_2(m). so we check (using efficient computations done in the reals) for each k from 2 to log_m if the k-th root of m is an integer. this is O(size of representation of m) steps and each step is done efficiently so i think the whole procedure is eventualy done in Poly time.
and we needed g as a witness…
I think that your idea is not fully right:
1. I don't see how one can verify whether an element, g, is a primitive element. I think that is why we were always told to select p=2q+1 (when both q,p are prime), this way it is easy to find an element whose order is 2 and another one whose order is q (by guessing and simple test) and then multiply them to get an order of 2q.
2. I didn't take Numerical Analysis. In the short google-ing I did I could only find algorithms for n-th root which depends on a precision parameter. So event if we knew that m is a power of a prime, I'm not sure it is that easy to find the root in a deterministic manner - I might be wrong because, as I said, I'm not familiar with Numerical methods.
3. I found this
cmi.
ac.
in/
~ramprasad/
lecturenotes/
comp_numb_theory/
lecture17.pdf which solves the problem.
Please comment if you know something I don't regarding 1 and 2.
Thank you for your time!
hmm…
1) if we knew the factors of m-1 then we could check if a given g is a p.r by raising it to the (m-1)/2 power and seeing it is -1… but this only suffices to show g is a p.r if we already knew that m is prime… so youre right, it's a problem and im not sure what to do here…
2)for calculating the integer k-th root of n (if exists).. you get a real number which is very close to an integer s and you know the k for which you are calculating the k-th root, then just raise s to the power of k and see that youre getting n… anyway in the procedure above we needed -not- to get an integer so in the numerical method beacuse we know the precision parameter delta i.e how at most far we are from the real root, if we see there is no integer at distance delta from what we have numerically calculated then we know there is no k-th root…