Re: SPRP's, and miller(n,k)

[Bill Daly <bill.daly@tradition-ny.com>]

It occurs to me that there is more that one can do when a number passes
a strong pseudoprime test to two or more bases. Take, for example, the
first pseudoprime in your list, m = r*s = 1122004669633 =
611557*1834669. Let k be the largest odd factor of m-1, thus k =
17531322963. The sprp(2) test gives 2^(2*k) = -1 mod m, and the sprp(3)
test gives 3^k = -1 mod m. Now as it happens, k is divisible by several
small primes, including 3. Let k1 = k/3. Then 2^(4*k1) and 3^(2*k1) are
both cube roots of 1 mod m, thus also mod r and mod s. There are 3 cube
roots of 1 mod r and mod s, thus there are 9 cube roots of 1 mod m. It
may well happen that the two cube roots of 1 found above are not
conjugates, and if this is the case their difference will have a factor
in common with m. Thus, calculate gcd(2^(4*k1) mod m, 3^(2*k1) mod m),
which as it happens is equal to r. Thus, with just the sprp(2) and
sprp(3) tests and a little extra effort, we can show that m is composite
by the simple artifice of factoring it.

The procedure is this. Given a candidate prime m, such that k is the
largest odd factor of m-1 (which we would have to calculate anyway),
find small factors of k. If there are none, just go about your business
as usual. Say we find small factors q1, q2, ..., qj. Let k1 = k/q1, k2 =
k1/q2, ..., kj = k[j-1]/qj. Given base a, calculate a^kj mod m, a^k[j-1]
= (a^kj)^qj, ..., a^k = (a^k1)^q1 mod m, then a^(2*k), a^(4*k) etc.
until the sprp(a) test is complete. Remember which power j_a of 2 is
such that a^(k*2^j_a) = 1 mod m. Also, save a^k1..a^kj mod m for later.
Repeat this for another base b. If m is both an sprp(a) and an sprp(b),
then we can find two q1-th roots of 1 mod m, namely a^(k1*2^j_a) and
b^(k1*2^j_b), which we calculate by squaring the saved values of a^k1
and b^k1. Calculate the gcd of the difference of these two values with
m. With any luck we will find a factor of m, if m is in fact composite.
If no factor is found, repeat with a^(k2*2^j_a) and b^(k2*2^j_b) etc.
until we either find a factor or exhaust all the small factors of k.

It costs little to find small factors of k, and nothing to calculate
a^kj..a^k1 on the way to calculating a^k. Thus, the main cost of this is
the gcd calculations.

I've tried this with the first 17 numbers in your list, and 14 of them
can be shown to be composite by this method:

1122004669633 is divisible by 611557, [q,a,b] = [3, 2, 13]
1251470005633 is divisible by 1937629, [q,a,b] = [3, 2, 23]
1851044809321 is divisible by 1924081, [q,a,b] = [27, 13, 23]
2943013357441 is divisible by 2426113, [q,a,b] = [9, 2, 13]
3141703961467 is divisible by 886243, [q,a,b] = [3, 2, 13]
3587493568961 is divisible by 1093541, [q,a,b] = [5, 13, 23]
3821068403461 is divisible by 1382221, [q,a,b] = [9, 13, 23]
4433977754251 is divisible by 4211401, [q,a,b] = [3, 2, 1662803]
5332040947201 is divisible by 4618241, [q,a,b] = [75, 2, 13]
5813209465381 is divisible by 1704877, [q,a,b] = [9, 13, 23]
5867930920351 is divisible by 4844761, [q,a,b] = [3, 2, 23]
7928173529251 is divisible by 5631401, [q,a,b] = [75, 2, 1662803]
8055526015153 is divisible by 2006929, [q,a,b] = [9, 2, 13]
9924187357873 is divisible by 1408843, [q,a,b] = [9, 13, 1662803]

Only 5926264938557, 6005270044507 and 9510594947587 cannot be resolved.
Note that the only small primes used are 3 and 5.

Regards,

Bill
**********************************************************************
This email and any files transmitted with it are confidential and
intended solely for the use of the individual or entity to whom
they are addressed.
This footnote also confirms that this email message has been swept by
MIMEsweeper for the presence of computer viruses.
**********************************************************************