20071203, 16:29  #1 
Dec 2007
2_{8} Posts 
Solving linear systems modulo n
i need to solve a linear system modulo a composite number.
if this number is n = p*q where p and q are prime, i know i have to solve the system modulo p and modulo q and combine the solutions with the chinese remainder theorem. but what if this number is a power of a prime (n = p^k) or a composition of powers (n = p1^k1 * p2^k2) ? How should i proceed? 
20071203, 18:03  #2  
Tribal Bullet
Oct 2004
3534_{10} Posts 
Quote:


20080207, 16:20  #3 
Dec 2007
2_{16} Posts 
Hi,
unfortunately, after all this time, I didn't solve my problem yet: implementing in C the Index Calculus method for computing discrete logarithms. On the web I didn't find anything different by the proposed version of Studholm but it's too diffilcult to me. Does anyone knows a simple implementation of this method? In particular I'm in trouble to code the linear algebra step of the algorithm: how employ Henseltype methods for matrix algebra modulo prime powers and chinese remainder methods for gluing powers of different primes. Any suggestions or link to other resources? Thank you for your reply jasonp! 
20080208, 15:06  #4  
Nov 2003
2^{2}·5·373 Posts 
Quote:
mathod used by Kevin McCurley etal. in their efforts. If N is the modulus, factor it. Solve the system mod p for each prime p dividing N. You can do this either by the Lanczos or Weidemann method. [or even by Gaussian elim if the matrix is small enough]. Then for primes p that divide N to a higher power than 1, raise the solution to p^k via Hensel's Lemma. [Hensel's lemma says that if A is a solution to f(x) = 0 mod p^k , then a solution mod p^(k+1) will be of the form A + hp for some h.] Now paste everything together by the CRT. For an effective implementation of the CRT, see my joint paper with Peter: P. Montgomery & R. Silverman An FFT Extension to the P1 Factoring Algorithm, in Math.Comp. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Solving systems of equations modulo n  carpetpool  carpetpool  2  20170205 20:40 
SIQS  problem with solving linear algebra  Dome  Factoring  14  20150306 17:59 
New Method for Solving Linear Systems  Dubslow  Miscellaneous Math  24  20120824 10:46 
Solving linear systems faster than ever...  WraithX  Math  2  20101023 21:27 
Mathematica questionsolving systems  ZetaFlux  Math  6  20050922 21:47 