(Partial) factorization (by trial division) of p-1 is in other to make use of CRT of discrete logarithms mod m where m | p-1.
The index calculus algorithm requires a relations collection phase, and a linear algebra phase. The linear algebra phase just requires sparse linear algebra over F_2 to discover squares. Beyond the quadratic field sieve, the number field sieve and function field sieves require more mathematics than most computer scientists, cryptographers, or programmers possess. Understanding of prime ideals, class groups, unit groups, and treatment of maximal orders not given by a power basis requires a background not typically found in programmers. (And those will such a background are likely to work in industry or government, where their code is proprietary.) Also optimization of NFS seems to be more art than science, even if one has a working implementation. It is NOT usually called by a one-line call to factorization or discrete log. Generally the algorithm is (only?) suitable for distributed computation. A good QFS (after Pollard rho [and ECM for factorization problems]) should suffice for any stand-alone system. --David --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~----------~----~----~----~------~----~------~--~---
