Modular equations: How does one proceed if "m" isn't prime?

[Zermelo]

Greetings everyone.

In my cryptography class, we did some modular equations,for example
[imath]8\cdot x = 20 (\mod26)[/imath]
And the notes just give the solutions, without showing work.

I know that if [imath]m[/imath] is prime, then [imath](Z_m,+_m,\cdot_m)[/imath] is a field, so every number (apart from zero) has a multiplicative and additive inverse, so every equation of the type [imath]a\cdot x + b = c (\mod m)[/imath] can be solved "algebraically", by adding the additive inverse of b and multiplying by the multiplicative inverse of a.

But if m isn't prime, then no number a such that (a, m)>1 has a multiplicative inverse, like in our example [imath]8\cdot x = 20 (\mod26)[/imath]. How does one proceed with such equations? Is there a smart way, or do I just need to brute-force test all possibilities, or look at the multiplicative table for mod 26?

 

[Dr.Peterson]

Greetings everyone.

In my cryptography class, we did some modular equations,for example
[imath]8\cdot x = 20 (\mod26)[/imath]
And the notes just give the solutions, without showing work.

I know that if [imath]m[/imath] is prime, then [imath](Z_m,+_m,\cdot_m)[/imath] is a field, so every number (apart from zero) has a multiplicative and additive inverse, so every equation of the type [imath]a\cdot x + b = c (\mod m)[/imath] can be solved "algebraically", by adding the additive inverse of b and multiplying by the multiplicative inverse of a.

But if m isn't prime, then no number a such that (a, m)>1 has a multiplicative inverse, like in our example [imath]8\cdot x = 20 (\mod26)[/imath]. How does one proceed with such equations? Is there a smart way, or do I just need to brute-force test all possibilities, or look at the multiplicative table for mod 26?

What other theorems have you learned about congruences?

Can you do anything with the fact that 8, 20, and 26 are all even?

 

[Zermelo]

What other theorems have you learned about congruences?

Can you do anything with the fact that 8, 20, and 26 are all even?

I actually did a whole class on number theory, but I forgot most of the material... I only started remembering things once they reappeared in cryptography. Thanks for your answer, but my question was more general. If m is not prime, is there a constant-time algorithm to solve (or determine if there are no solutions to) [imath]a\cdot x = b (\mod m)[/imath]?

 

[Dr.Peterson]

I actually did a whole class on number theory, but I forgot most of the material... I only started remembering things once they reappeared in cryptography. Thanks for your answer, but my question was more general. If m is not prime, is there a constant-time algorithm to solve (or determine if there are no solutions to) [imath]a\cdot x = b (\mod m)[/imath]?

Have you looked (perhaps in your old textbook) for information on solving linear congruences, such as this?

How To Solve Linear Congruences - Interactive Mathematics

Numbers are congruent if they have a property that the difference between them is integrally divisible by a number (an integer). The number is called the modulus, and the statement is treated as congruent to the modulo. Mathematically, this can be expressed as b = c (mod m) Generally, a linear...

www.intmath.com

If your current class gives no worked examples of such problems, then you probably are expected to review this material.

(But your question actually was a specific one, not what you are asking now; it is not hard to solve, and may have been designed to get you thinking specifically, not using a general-purpose algorithm. Have you solved it?)

 

[Zermelo]

Have you looked (perhaps in your old textbook) for information on solving linear congruences, such as this?

How To Solve Linear Congruences - Interactive Mathematics

Numbers are congruent if they have a property that the difference between them is integrally divisible by a number (an integer). The number is called the modulus, and the statement is treated as congruent to the modulo. Mathematically, this can be expressed as b = c (mod m) Generally, a linear...

www.intmath.com

If your current class gives no worked examples of such problems, then you probably are expected to review this material.

(But your question actually was a specific one, not what you are asking now; it is not hard to solve, and may have been designed to get you thinking specifically, not using a general-purpose algorithm. Have you solved it?)

Ah yes! For some reason I didn't connect solving linear congruencies with solving linear modular equations. They're basically the same thing! When I learned number theory I didn't know anything about algebra, so I didn't think of congruencies as equations... Thanks, can't believe I missed this!

 

[Dr.Peterson]

Ah yes! For some reason I didn't connect solving linear congruencies with solving linear modular equations. They're basically the same thing! When I learned number theory I didn't know anything about algebra, so I didn't think of congruencies as equations... Thanks, can't believe I missed this!

They are exactly the same thing! (though if you search for "modular equation", you'll find that its proper definition is something I've never even heard of, not a congruence!).

I had thought of pointing out that you used an equals sign ([imath]=[/imath]) rather than a congruent sign [imath]\equiv[/imath]) in your statement of the problem; the former doesn't really belong with "mod". I suppose your current course is sloppy with the notation and terminology, and so fails to connect you with what you have learned before.

 

[Zermelo]

They are exactly the same thing! (though if you search for "modular equation", you'll find that its proper definition is something I've never even heard of, not a congruence!).

I had thought of pointing out that you used an equals sign ([imath]=[/imath]) rather than a congruent sign [imath]\equiv[/imath]) in your statement of the problem; the former doesn't really belong with "mod". I suppose your current course is sloppy with the notation and terminology, and so fails to connect you with what you have learned before.

Yes, exactly, but I’m getting comfortable.

While we’re having this conversation, let me ask another question, because I haven’t had much touch with algebra.

To me it seems that fields are “perfect”, because any equation ax+b=c (a != 0) has a unique solutio n, and that solution can be expressed and found easily using a constant time algorithm.
But for “weaker” algebraic structures (like rings),
1) every linear (affine) equation DOESN’T HAVE TO HAVE A SOLUTION
2) even if every linear equation does have a solution, we don’t have a general algorithm of finding them.

Are these statements true? Could you shed some light?

 

[Dr.Peterson]

To me it seems that fields are “perfect”, because any equation ax+b=c (a != 0) has a unique solutio n, and that solution can be expressed and found easily using a constant time algorithm.
But for “weaker” algebraic structures (like rings),
1) every linear (affine) equation DOESN’T HAVE TO HAVE A SOLUTION
2) even if every linear equation does have a solution, we don’t have a general algorithm of finding them.

Are these statements true? Could you shed some light?

I suppose that's all more or less true, though it may depend on how you are defining "constant time", and what kind of solution you want (e.g., decimal or simplified fraction). And there can be a "general algorithm", such as the extended Euclidean algorithm.

And, of course, one of the goals in cryptography is for something not to be easily solved ...