Big Integer and primitive roots


DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Results 1 to 2 of 2

Thread: Big Integer and primitive roots

  1. #1
    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
    asdf

  2. #2
    Join Date
    Mar 2005
    Location
    Sendling, MUC, .de
    Posts
    100
    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
    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 03: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
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

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