DevX Home Today's Headlines   Articles Archive   Tip Bank   Forums

# Thread: Big Integer and primitive roots

1. Registered User
Join Date
Nov 2004
Location
asdf
Posts
24

## Big Integer and primitive roots

If I generate two Big Integer numbers is it possible to test if one is a primitive
of another.
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

2. 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.
Last edited by meisl; 04-05-2005 at 02:05 PM.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•

 FAQ Latest Articles Java .NET XML Database Enterprise
 Questions? Contact us. C++ Web Development Wireless Latest Tips Open Source

×
We have made updates to our Privacy Policy to reflect the implementation of the General Data Protection Regulation.