Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 0 down vote favorite

I am trying to implement index calculus algorithm for discrete logarithm problem. In general the algorithm works like this : Input: Zp, order d, generator a, b element of Z Output: log_ab

1- find a set Factor_Base = {p1,...,ph}

2- find random number k and compute a^k

3- factorize a^k= f1^x*f2^y*...*fn^o

4- if factors of a^k belong in Factor_Base then find a relation k = x*logaf1 + y*logaf2 + ...+ o*logafn

5- repeat steps 2 - 4 until we have enough relations

6 - Solve the linear equation system for the unknown logs

7 - compute y= logab ( Involving more steps )

My problem is in step 6 . How to solve the system of linear equations?

In specific I use python with numpy. Is there an easy way to solve this system?

share|improve this question
So, your question is, how does one solve a system of linear equations? Are you familiar with Gaussian elimination? Do you have access to any textbooks? If it's a programming problem, maybe there's a better forum for your question, some kind of computing stackexchange. – Gerry Myerson Jan 3 '12 at 14:51
@Gerry Myerson I want to solve the linear quations using Gaussian elimination in a finite field. Gaussian elimination is the same for finite fields? – gosom Jan 3 '12 at 17:05
1  
@gosom: Yes: Gaussian elimination is the same over any field; just perform the operations in the field (e.g., working over $\mathbf{F}_2$, $1+1=0$). – Arturo Magidin Jan 3 '12 at 18:30

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.