I think you mean to test whether an element x of the multiplicative group (Z/pZ)* is a primitive root of that group (where x is the "one" and p is "another"), right?*
Originally Posted by
xxxxx
I'm wondering does the Big Integer class have a built in method.
The answer is no, but since you implemented it for ints, you will know that if p is prime or a power of an odd prime, then (Z/pZ)* is cyclic, ie. primitive roots exist for it (Gauss).
Furthermore, if p is an odd prime and x is no multiple of p (otherwise x cannot be primitive root), then you need the prime decomposition of p-1 and test if x^((p-1)/q_i) != 1 (mod p) for all prime factors q_i. If that's the case, then x is a primitive root mod p.
All this you can do with BigIntegers as well. It's even easier since there is the method
Code:
BigInteger.modPow(BigInteger exponent, BigInteger modulus)
and
Code:
BigInteger.mod(BigInteger modulus)
as opposed to
Code:
BigInteger.remainder(BigInteger divisor)
which works rather like % on ints (possibly negative results).
For cryptographic applications the discrete logarithm to base x of a number y in (Z/pZ)*, p prime, can be used (x being primitive root mod p, the discr. log. is the number of times you have to multiply x with itself mod p to obtain y).
There is an algorithm of worst-case complexity O(sqrt(p) log p) (as opposed to the naive average O(p/2) ) called "giant steps baby steps" by D. Shanks, which I implemented for BigIntegers some time ago.
Interested?
------
* to be most exact: the elements of the group are residue classes and integers x or y are rather representatives of one such class.
p.s.: just in case: by Z I refer to the set of integers (not ints!) and Z/pZ is the set of residue classes mod p, ie. of equivalence classes of integers where two integers are considered equivalent iff they give the same remainder (in the mathematical, not the %-sense!) when divided by p. Furthermore, (Z/pZ)* denotes Z/pZ without the zero element, ie. without the class containing the number zero and all multiples of p, which, together with multiplication mod p forms a multiplicative group, also denoted by (Z/pZ)* for brevity.