I note that certain statements in
http://primes.utm.edu/prove/prove2_3.html
are incorrect. e.g. Mid way down the page, there is
the bullet point (from Jaeschke, Math Comp 61, 1993)
* If n < 9,080,191 is a both 31 and 73-SPRP, then n is prime.
n is a-SPRP is defined to be
Write n-1 = (2^s)*d where d is odd and s is non-negative:
n is a strong probable-prime base a (an a-SPRP) if either
(a^d) = 1 (mod n) or
(a^d)^(2^r) = -1 (mod n)
for some non-negative r less than s.
SPRP-ness can be implemented as:
huo=: <[EMAIL PROTECTED]:^:(0=2&|)^:a: NB. halve until odd
(+./c=n-1) +. 1={:c=. a n&|@^ huo n-1
For n=.946
(+./c=n-1) +. 1={:c=. 31 n&|@^ huo n-1
1
(+./c=n-1) +. 1={:c=. 73 n&|@^ huo n-1
1
In detail huo 946 is just 945 (the quantity d in the
definition of a-SPRP), and
946x | 31x^945x
1
946x | 73x^945x
945
The first demonstrates that 946 is 31-SPRP due to
31^d being 1 mod 946, and 946 is 73-SPRP due to
73^d being _1 mod 946. So according to the bullet
point, 946 should be prime. But it is not prime.
Might the J arithmetic be wrong? Some sanity checks:
946&|@* / 945$31
1
946&|@* / 945$73
945
946 | 31*31
15
946&|@*/ 31,472$15
1
946 | 73*73
599
946&|@*/ 73,472$599
945
Other composites claimed to be prime are 4 6 8.
4 6 8 (|"1) 31 73^/4 6 8 -1
3 1 7
1 1 1
(3 is _1 mod 4 and 7 is _1 mod 8.)
The bullet point (and other similar bullet points in the page)
are also flawed in that presumably 31 and 73 themselves
should be excluded from "n<9,080,191": a^d and (a^d)^(2^r)
are going to be 0 mod n if a=n, so they won't be 1 or -1 mod n,
so they are supposed to be composite.
Can the mathematicians among us please verify or refute
my reasoning?
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
