Big Integer and primitive roots
If I generate two Big Integer numbers is it possible to test if one is a primitive
I have already written the algorithm for integers.
I'm wondering does the Big Integer class have a built in method. I've been
on google but no luck yet
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?*
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).
Originally Posted by xxxxx
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
BigInteger.modPow(BigInteger exponent, BigInteger modulus)
as opposed to
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.
* 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.
Last edited by meisl; 04-05-2005 at 02:05 PM.
-- Android Development Center
-- Cloud Development Project Center
-- HTML5 Development Center
-- Windows Mobile Development Center