combine puzzle!
 

[url]https://rosettacode.org/wiki/Miller–Rabin_primality_test[/url]
very bad algorithm!
so very slow, if R is very big number!


in chinese, about 4000 years ago:


if R prime than:


(2^R-2) mod R = 0


and:
(2^R-2) mod R>0 then R is non-prime!


but:
(2^R-2) mod R=0 then, R is may be a prime and not?


but there was more!


and some arabian mathematicians translated it, arabic lang. thousand year ago.


and a few hundred years ago, some mathematicians translated it, european lang.


and very bad, wrong manuplation!
(2^R-1) mod R =? 1


if chinese method think:
MM127=2^(2^127-1)-1 is a prime, only half page prof, and very simple!
any R prime test by chinese method a few minutes, if R countable!
please think it!

[QUOTE=hal1se;492667][url]https://rosettacode.org/wiki/Miller–Rabin_primality_test[/url]
very bad algorithm!
so very slow, if R is very big number!


in chinese, about 4000 years ago:


if R prime than:


(2^R-2) mod R = 0


and:
(2^R-2) mod R>0 then R is non-prime!


but:
(2^R-2) mod R=0 then, R is may be a prime and not?


but there was more!


and some arabian mathematicians translated it, arabic lang. thousand year ago.


and a few hundred years ago, some mathematicians translated it, european lang.


and very bad, wrong manuplation!
(2^R-1) mod R =? 1


if chinese method think:
MM127=2^(2^127-1)-1 is a prime, only half page prof, and very simple!
any R prime test by chinese method a few minutes, if R countable!
please think it![/QUOTE]

Fermat used :
[TEX]A^{R}\equiv A \bmod R \forall A, \gcd(A,R)=1[/TEX]

[QUOTE=hal1se;492667][url]https://rosettacode.org/wiki/Miller–Rabin_primality_test[/url]
very bad algorithm!
so very slow, if R is very big number!


in chinese, about 4000 years ago:


if R prime than:


(2^R-2) mod R = 0


and:
(2^R-2) mod R>0 then R is non-prime![/QUOTE]

Nothing of the sort was known in China 4000 years ago. The earliest known writing in China is from the Shang Dynasty 3200 years ago and as far as we know they had only simple arithmetic. It wasn't until the I Ching in the Zhou Dynasty 3000 years ago that any real mathematics (basic geometry) appeared.

See, e.g., [url]http://mathworld.wolfram.com/ChineseHypothesis.html[/url] for the origin of this misunderstanding.

See also [url=http://hkumath.hku.hk/~mks/FermatLittleThmRev.pdf]On the myth of an ancient Chinese theorem about primality[/url]

On the mathematical content, Fermat's test is no faster than the Miller-Rabin test, but provides less certainty and (unlike M-R) has pseudoprimes.

Sorry its my farm-boy roots.
 

When I read the title I first thought of this:

I think it is interesting that all known primality tests other than sieving (not exactly a test) and trial-by-division and the LL test are based on and have as a bottleneck the powermod operation (corrections/counterexamples would be appreciated).
It is also interesting that at least in theory the powermod operation can be made to run in parallel, but there does not seem to be any such publicised/published effort (corrections are appreciated).:smile:

[QUOTE=petrw1;492913]When I read the title I first thought of this:[/QUOTE]

Me too!