Congruence

[storm5510]

In mathematics and especially in abstract algebra as well as modular arithmetic, a congruence relation or simply congruence is an equivalence relation that is compatible with some algebraic operation(s).

Someone, explain this in simple terms. Please, no links to other sites...

[Mini-Geek]

Here's my understanding of it, simple as can be: (for modular arithmetic, at least) 13 is congruent to 1 modulo 12 because each are one higher than a multiple of 12. Or in formula form:

Where means congruent to.

[Dougy]

``Congruence'' means ``equivalence'' in some sense. This is one of the words in mathematics that has many meanings depending on what area of mathematics your interested in (eg. there are congruent triangles also).

Typically in number theory... two integers are congruent modulo m if they have the same remainder after division by m.

In Mini-Geek's example m=12. We see that 13 after division by 12 leaves a remainder 1. Similarly, 1 after division by 12 also leaves a remainder 1. In fact, all of the numbers in are congruent modulo 12. This can also be extended to negative integers too, so are all congruent modulo 12.

[lfm]

Originally Posted by storm5510

Someone, explain this in simple terms. Please, no links to other sites...

I usually read it as "referring to the same thing". Like 13:00 in a 24 hour time vs 1:00 PM in a 12 hour time system (13 = 1 (mod 12)) they are referring to the same time of day. So the various base 10 numbers when mapped into a (mod x) system are just different representations for the same end value referring to the same end result with different symbols. It no different from converting base 10 to binary or hexadecimal. It is the same number with different symbols 10(base 10) is congruent 1010(base 2).

IANAM so YMMV

[storm5510]

The reason I ask is I was trying to understand what is below:

The Algorithm of Miller-Rabin primality test for an odd integer n

1. We write n-1 = 2^k*m where k is integer and m is an odd number.

2. We choose a random integer "a" where it is between 1 to n-1.

3. Then calculate b = a^m mod n.

4. If b is congruent to 1 modulo n, then print "n is prime" and quit.

5. For i = 0 to k - 1 do

6. if b is congruent to (-1) modulo n,then print "n is prime" and quit; else b = b^2 mod n.

7. Otherwise, print "n is composite".

9² and 81 are congruent, for example.

[Mini-Geek]

In other words:

3. Then calculate b = a^m mod n.

define b to be the remainder of a^m divided by n

4. If b is congruent to 1 modulo n, then print "n is prime" and quit.

if b divided by n has a remainder of 1, then print "n is prime" and quit.

6. if b is congruent to (-1) modulo n,then print "n is prime" and quit; else b = b^2 mod n.

if b divided by n has a remainder that is one less than n (e.g. 19/10 has a remainder of 9, which is 10-1), then print "n is prime" and quit; else define b to be the remainder when b^2 is divided by n.

(I'll assume you understand the rest of it, like the 'for' loop)

http://en.wikipedia.org/wiki/Miller%...primality_test has explanations, pseudocode, an example, etc.

[storm5510]

I wasn't much concerned with the rest. Just the term. I rather doubt something like this could be coded, reliably anyway.

Thanks.

[bsquared]

Originally Posted by storm5510

I rather doubt something like this could be coded, reliably anyway.

Thanks.

What do you mean? Many people on this forum have implemented it, myself included. Where are you getting stuck?

[lfm]

Originally Posted by storm5510

I wasn't much concerned with the rest. Just the term. I rather doubt something like this could be coded, reliably anyway.

Thanks.

huh? Miller-Rabin tests are coded all the time. It is often what is behind "probable prime tests".

[storm5510]

Originally Posted by lfm

huh? Miller-Rabin tests are coded all the time. It is often what is behind "probable prime tests".

I should have said, I couldn't code it reliably. I saw examples in other platforms, and pseudocode below from Wikipedia.

Input: n > 2, an odd integer to be tested for primality;

Input: k, a parameter that determines the accuracy of the test

Output: composite if n is composite, otherwise probably prime

write n − 1 as 2s·d with d odd by factoring powers of 2 from n − 1
LOOP: repeat k times:
pick a randomly in the range [2, n − 1]
x ← ad mod n
if x = 1 or x = n − 1 then do next LOOP
for r = 1 .. s − 1
x ← x2 mod n
if x = 1 then return composite
if x = n − 1 then do next LOOP
return composite
return probably prime

[R.D. Silverman]

Originally Posted by storm5510

I should have said, I couldn't code it reliably. I saw examples in other platforms, and pseudocode below from Wikipedia.

If you will explain where you are getting stuck, perhaps help
might be offered.