mersenneforum.org  

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

Reply
 
Thread Tools
Old 2009-09-13, 18:30   #1
storm5510
Random Account
 
storm5510's Avatar
 
Aug 2009
U.S.A.

25×53 Posts
Question Congruence

Quote:
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...
storm5510 is offline   Reply With Quote
Old 2009-09-13, 18:57   #2
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17×251 Posts
Default

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:
13 \equiv 1 \hspace{1} (\text{mod } 12)
Where \equiv means congruent to.
Mini-Geek is offline   Reply With Quote
Old 2009-09-13, 21:28   #3
Dougy
 
Dougy's Avatar
 
Aug 2004
Melbourne, Australia

2308 Posts
Default

``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 \{1,13,25,\dots\} are congruent modulo 12. This can also be extended to negative integers too, so \{\dots,-23,-11,1,13,25,\dots\} are all congruent modulo 12.
Dougy is offline   Reply With Quote
Old 2009-09-13, 21:56   #4
lfm
 
lfm's Avatar
 
Jul 2006
Calgary

42510 Posts
Default

Quote:
Originally Posted by storm5510 View Post
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
lfm is offline   Reply With Quote
Old 2009-09-13, 23:16   #5
storm5510
Random Account
 
storm5510's Avatar
 
Aug 2009
U.S.A.

25×53 Posts
Default

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

Quote:
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".
92 and 81 are congruent, for example.

Last fiddled with by storm5510 on 2009-09-14 at 00:05
storm5510 is offline   Reply With Quote
Old 2009-09-14, 00:48   #6
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17·251 Posts
Default

In other words:
Quote:
3. Then calculate b = a^m mod n.
define b to be the remainder of a^m divided by n
Quote:
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.
Quote:
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.

Last fiddled with by Mini-Geek on 2009-09-14 at 00:52
Mini-Geek is offline   Reply With Quote
Old 2009-09-14, 01:34   #7
storm5510
Random Account
 
storm5510's Avatar
 
Aug 2009
U.S.A.

25·53 Posts
Post

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

Thanks.
storm5510 is offline   Reply With Quote
Old 2009-09-14, 02:49   #8
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

23×419 Posts
Default

Quote:
Originally Posted by storm5510 View Post
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?
bsquared is offline   Reply With Quote
Old 2009-09-14, 02:51   #9
lfm
 
lfm's Avatar
 
Jul 2006
Calgary

1A916 Posts
Default

Quote:
Originally Posted by storm5510 View Post
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".
lfm is offline   Reply With Quote
Old 2009-09-14, 16:02   #10
storm5510
Random Account
 
storm5510's Avatar
 
Aug 2009
U.S.A.

25·53 Posts
Default

Quote:
Originally Posted by lfm View Post
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.

Quote:
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]
xad mod n
if x = 1 or x = n − 1 then do next LOOP
for r = 1 .. s − 1
xx2 mod n
if x = 1 then return composite
if x = n − 1 then do next LOOP
return composite
return probably prime
storm5510 is offline   Reply With Quote
Old 2009-09-14, 18:33   #11
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by storm5510 View Post
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.
R.D. Silverman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Linear Congruence order 4 sequence not testing in PFGW? carpetpool Software 14 2017-07-13 19:54
Congruence relations Lee Yiyuan Miscellaneous Math 7 2012-05-08 12:55
Congruence notation meknowsnothing Math 1 2007-05-31 03:32
congruence mod 2^p-1 abiessuunreg Miscellaneous Math 3 2005-03-07 21:03

All times are UTC. The time now is 03:06.

Fri Dec 4 03:06:26 UTC 2020 up 23:17, 0 users, load averages: 1.62, 1.88, 1.84

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.