mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Math (https://www.mersenneforum.org/forumdisplay.php?f=8)
-   -   Solving linear systems modulo n (https://www.mersenneforum.org/showthread.php?t=9692)

 drido 2007-12-03 16:29

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?

 jasonp 2007-12-03 18:03

[QUOTE=drido;119812]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) ?
[/QUOTE]
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.

 drido 2008-02-07 16:20

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?

 R.D. Silverman 2008-02-08 15:06

[QUOTE=drido;125089]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?

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.

 All times are UTC. The time now is 15:14.