Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I don't understand the 'Wiedemann algorithm' works. Can someone explain the factoring of RSA-704 in an easy way?

share|improve this question
1  
Short answer: no. Also, are you asking about the block Wiedemann algorithm, or the NFS in general? –  fgrieu Jun 24 '13 at 9:23
1  
fgrieu is correct. You might as well ask for a simple explanation of Perelman's proof of the Poincare conjecture. Some things simply don't allow simple explanations. EDIT: Sorry, I should be more helpful. To understand the factorization process you should start by understanding the general number field sieve. Wikipedia is a good start and has links to several important papers about the technique. –  pg1989 Jun 24 '13 at 17:44
add comment

1 Answer 1

Let me try a simple explanation of NFS. I will necessarily skip lots of details, but I hope you will get the main ideas.

The number field sieve algorithm (NFS) is a member of a large family: index calculus algorithms. All algorithms in the family, which can be used for factoring and discrete logarithms in finite fields, share a common structure:

  • Preparation phase: find a adequate representation of the desired structure and choose a smoothness basis, i.e. a set of small elements.

  • Phase I: Find many multiplicative relations between elements of the smoothness basis. Simple example: $2\cdot 3 = -1 \pmod{7}$. You need more equations than the number of smoothness basis elements. Formally taking logarithm of all multiplicative relations, we get linear relations between logarithms of small elements.

  • Phase II: Perform linear algebra. Here the details vary between Dlogs and factoring. For Dlogs, finding a non-zero kernel element modulo the group order directly gives the logarithms of the small elements. For factoring, you search instead for a kernel element in the transposed system modulo 2. This correspong to finding a product of the initial relation where all elements will appear with an even exponent.

  • Phase III: Conclude the computation. For Dlogs, this is the individual logarithm phase. For factoring, we extract from the above linear relation two elements whose squares are equal, say $A^2\equiv B^2\pmod{N}$, with probability $1/2$, the gcd of $A-B$ and $N$ yields a non-trivial factor of $N$. If it does not work, try another relation.

The Wiedemann algorithm is an iterative method for the linear algebra phase. Usually, when working modulo $2$, block Wiedemann is used. This method allows to compute many relations (as many as the block size), after computing a sequence of matrix by vector block product. The reason for using this approach (or Lanczos method) for solving the system is that it is much faster and much more efficient in terms of memory than Gaussian elimination for the large linear systems that are involved.

With NFS, some of the details become mathematically quite involved. For this reason, I will just add a few more points.

  • Preparation phase: $N$ is represented by finding two polynomials $f$ and $g$ of relatively small degrees and small coefficients with a common root $R$ modulo $N$. Most of the time, one of the two polynomials is linear. On the linear side, the smoothness basis contains small prime numbers. On the other side (algebraic side), the smoothness basis contains degree one ideals of small norm.
  • Multiplicative relations generation. Take an element $a+bX$ and send it to $a+bR$ on the linear side and to the ideal generated by $a+b\alpha$ ($\alpha$ a complex root of the polynomial defining the algebraic side). If both side completely factor into elements of the smoothness basis, you get a relation.
  • Linear algebra and square root. This becomes more difficult than in the general case, because to get a relation $A^2=B^2$ it is not only necessary to have even exponent on the ideal side, you also need to make sure that the resulting value is a principal ideal. This is done by adding multiplicative characters in the relation matrix before the linear algebra step.

Hope that helps.

share|improve this answer
add comment

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.