Results 1 to 2 of 2

Math Help - Index calculus algorithm, -1 in factorization

  1. #1
    Member
    Joined
    Feb 2011
    Posts
    147
    Thanks
    3

    Index calculus algorithm, -1 in factorization

    I have to understand the idea of the index calculus algorithm. The algorithm can be found here.

    We have to find the discrete logarithm of an element of a multiplicative group of intergers modulo n (say n=5), let's say to base 2 (2 is a generator of \mathbb{Z}_5^*).

    We need a factor base in the input. The factor base is a tuple (-1,2,3,5,7,11,...,p_r), where p_r is the r-th prime. My question is why do we want -1 in the factor base?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927

    Re: Index calculus algorithm, -1 in factorization

    With good probability, the algorithm will stumble on a g^k which apparently isn't smooth over the factor base, but when taken as a negative number in \mathbb{Z} / n \mathbb{Z} turns out to be smooth, so you need to add -1 to your factor base to benefit from this.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Algorithm - Finding index of an array
    Posted in the Math Topics Forum
    Replies: 5
    Last Post: March 5th 2011, 09:56 AM
  2. [Factorization] Factorization of polynomials
    Posted in the Algebra Forum
    Replies: 9
    Last Post: April 9th 2010, 12:15 AM
  3. Replies: 2
    Last Post: March 4th 2010, 01:49 AM
  4. Replies: 3
    Last Post: June 26th 2008, 11:26 PM
  5. LU-Factorization Algorithm??
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: February 11th 2007, 08:40 PM

Search Tags


/mathhelpforum @mathhelpforum