DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Results 1 to 2 of 2
  1. #1
    Join Date
    Nov 2004

    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. #2
    Join Date
    Mar 2005
    Sendling, MUC, .de
    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?*

    Quote 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
    BigInteger.modPow(BigInteger exponent, BigInteger modulus)
    BigInteger.mod(BigInteger modulus)
    as opposed to
    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.

    * 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
HTML5 Development Center
Latest Articles
Questions? Contact us.
Web Development
Latest Tips
Open Source

   Development Centers

   -- Android Development Center
   -- Cloud Development Project Center
   -- HTML5 Development Center
   -- Windows Mobile Development Center

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