mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2007-12-03, 16:29   #1
drido
 
Dec 2007

2 Posts
Default 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?
drido is offline   Reply With Quote
Old 2007-12-03, 18:03   #2
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3·1,163 Posts
Default

Quote:
Originally Posted by drido View Post
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) ?
Use Hensel's lemma; an answer mod p uniquely specifies an answer mod p^k, if the latter exists. Repeat for each p^k then use the CRT as before. The presence of powers in the CRT modulus doesn't matter (CRT only cares that the p^k are coprime to each other), though it requires finding inverses mod p^k which also needs Hensel's lemma.
jasonp is offline   Reply With Quote
Old 2008-02-07, 16:20   #3
drido
 
Dec 2007

210 Posts
Default

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 Hensel-type 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!
drido is offline   Reply With Quote
Old 2008-02-08, 15:06   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26·113 Posts
Default

Quote:
Originally Posted by drido View Post
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 Hensel-type 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!
I am not familiar with the method of Studholm, but you do have the
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 P-1 Factoring
Algorithm, in Math.Comp.
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Solving systems of equations modulo n carpetpool carpetpool 2 2017-02-05 20:40
SIQS - problem with solving linear algebra Dome Factoring 14 2015-03-06 17:59
New Method for Solving Linear Systems Dubslow Miscellaneous Math 24 2012-08-24 10:46
Solving linear systems faster than ever... WraithX Math 2 2010-10-23 21:27
Mathematica question-solving systems Zeta-Flux Math 6 2005-09-22 21:47

All times are UTC. The time now is 16:25.

Thu Nov 26 16:25:32 UTC 2020 up 77 days, 13:36, 5 users, load averages: 1.54, 1.65, 1.60

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.