Congruence notation

meknowsnothing · 2007-05-30, 23:33

I read about the AKS primality test. That algorithm uses the relation (x - a)^n = (x^n - a) mod (n, x^r - 1). What does it mean? I know that a=b mod c <=> c|a-b but the notation a=b mod (c,d) is new for me. Or is (n,x^r-1) just the greatest common divisor of n and x^r-1?

wblipp · 2007-05-31, 03:32

Quote:

Originally Posted by meknowsnothing

I read about the AKS primality test. That algorithm uses the relation (x - a)^n = (x^n - a) mod (n, x^r - 1). What does it mean?

Must be something going around. fetofs asked the same question earlier this month. The answers are pretty good.

http://www.mersenneforum.org/showthread.php?t=8119

2007-05-30, 23:33	#1
meknowsnothing May 2007 3 Posts	Congruence notation I read about the AKS primality test. That algorithm uses the relation (x - a)^n = (x^n - a) mod (n, x^r - 1). What does it mean? I know that a=b mod c <=> c\|a-b but the notation a=b mod (c,d) is new for me. Or is (n,x^r-1) just the greatest common divisor of n and x^r-1?

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	storm5510	Math	27	2009-09-22 23:14
prime 95 notation	spyros	Information & Answers	19	2009-06-19 20:28
congruence mod 2^p-1	abiessuunreg	Miscellaneous Math	3	2005-03-07 21:03