combine puzzle!

hal1se · 2018-07-28, 19:16

https://rosettacode.org/wiki/Miller–...primality_test
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!

science_man_88 · 2018-07-28, 19:29

Quote:

Originally Posted by hal1se

https://rosettacode.org/wiki/Miller–...primality_test
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!

Fermat used :
$A^{R}\equiv A \bmod R \forall A, \gcd(A,R)=1$

CRGreathouse · 2018-07-29, 17:14

Quote:

Originally Posted by hal1se

https://rosettacode.org/wiki/Miller–...primality_test
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!

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., http://mathworld.wolfram.com/ChineseHypothesis.html for the origin of this misunderstanding.

Dr Sardonicus · 2018-07-31, 13:10

See also On the myth of an ancient Chinese theorem about primality

CRGreathouse · 2018-07-31, 13:35

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.

petrw1 · 2018-08-01, 20:50

When I read the title I first thought of this:

a1call · 2018-08-02, 02:31

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).

masser · 2018-08-02, 04:32

Quote:

Originally Posted by petrw1

When I read the title I first thought of this:

Me too!

2018-07-28, 19:16	#1
hal1se Jul 2018 3·13 Posts	combine puzzle! https://rosettacode.org/wiki/Miller–...primality_test 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!

2018-08-01, 20:50	#6
petrw1 1976 Toyota Corona years forever! "Wayne" Nov 2006 Saskatchewan, Canada 1001001000100₂ Posts	Sorry its my farm-boy roots. When I read the title I first thought of this: Attached Thumbnails

2018-08-02, 02:31	#7
a1call "Rashid Naimi" Oct 2015 Remote to Here/There 807₁₆ Posts	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). Last fiddled with by a1call on 2018-08-02 at 02:35

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
a puzzle	bcp19	Puzzles	18	2012-03-02 04:11
A well-known puzzle...	mart_r	Puzzles	31	2009-04-09 22:51
Dot puzzle	nibble4bits	Puzzles	37	2006-02-27 09:35
Should a diskless node run it's own ecm program or should I combine them somehow?	jasong	GMP-ECM	1	2006-02-24 08:34
Combine sieving with SoB?	Mystwalker	Prime Sierpinski Project	67	2005-11-21 18:03

2018-07-31, 13:10	#4
Dr Sardonicus Feb 2017 Nowhere 4,643 Posts	See also On the myth of an ancient Chinese theorem about primality

2018-07-31, 13:35	#5
CRGreathouse Aug 2006 3·1,993 Posts	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.