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

[Gerhard Niklasch <nikl@mathematik.tu-muenchen.de>]

In response to:
> Message-Id: <199910142336.TAA22894@tasam.com>
> From: Lucas Wiman  <lrwiman@tasam.com>
> Subject: Re: SPRP's, and miller(n,k)
> Date: Thu, 14 Oct 1999 19:36:48 -0400 (EDT)

[about miller() testing for spsp to bases 2,13,23,1662803;  I wrote:]

> > I have what I believe to be the complete list of 42 composites
[without prime divisors <100]
> > up to 3*2^46 which would (wrongly) pass the miller() test for the four
> > bases chosen at k==16.  Without Atkin's `end-matching' check, there
> > would be 86 of them.
> 
> Could you post this list (of both 42, and 86)?

Why not... indeed it would be nice if someone else could check
independently that I haven't missed any  (my search procedure
wasn't fully automated, and given that I did this more than 8
months ago, contemporary faster hardware might make it less of
a chore than it was for my machines).  Anybody interested in
learning how I went about this please contact me off the list,
preferably at <mailto:gerhard.niklasch@okay.net>.  Some clues
are contained in the filenames below...

Another hint -- products of two (distinct) primes can be found
starting from the smaller prime factor as long as it isn't too
large, and the upper bound of the search is not needed for this
(one has a finite set of candidates for the larger factor, usually
empty).  I pushed this to about 760000 or so.  Only the first two
entries were found in this way  (but it saved a fair amount of
time elsewhere).

Enjoy, Gerhard

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
\\  1000000000000 lower bound for solutions, according to G. Jaeschke
\\211106232532992 current upper cutoff (3*2^46)
\\listing all spsps to the joint bases found by our search; those marked
\\with [*] fail the tail-mismatch criterion
\\suns2:numbers/spsp-sieve-1323-t2b.39900.log (1998Nov03)
    1122004669633 = 611557*1834669 [*]
\\suns2:numbers/spsp-sieve-1323-t2b.50720.log (1998Nov09)
    1251470005633 = 645877*1937629 [*]
\\suns2:numbers/spsp-1323/2_3_3_3.lg2 (1999Jan10)
    1851044809321 = 962041*1924081 [*]
\\suns2:numbers/spsp-1323/6_6_7_7.lg2 (1999Jan10)
    2943013357441 = 1213057*2426113 [*]
\\suns2:numbers/spsp-1323/1_1_0_0.lg2 (1999Jan03)
    3141703961467 = 886243*3544969
\\suns2:numbers/spsp-1323/2_2_0_2.lg2 (1999Jan03)
    3587493568961 = 1093541*3280621 [*]
\\suns2:numbers/spsp-1323/2_0_1_2.lg2 (1999Jan03)
    3821068403461 = 1382221*2764441 [*]
\\suns2:numbers/spsp-1323/1_1_1_0.lg2 (1999Jan03)
    4433977754251 = 1052851*4211401
\\suns2:numbers/spsp-1323/8_9_9_9.lg2 (1999Jan10)
    5332040947201 = 1154561*4618241 [*]
\\suns2:numbers/spsp-1323/2_2_1_1.lg2 (1999Jan03)
    5813209465381 = 1704877*3409753 [*]
\\suns2:numbers/spsp-1323/0_1_0_1.lg2 (1999Jan03)
    5867930920351 = 1211191*4844761
\\suns2:numbers/spsp-1323/2_2_2_2.lg2 (1999Jan03)
    5926264938557 = 1987673*2981509 [*]
\\suns2:numbers/spsp-1323/1_1_1_1.lg2 (1999Jan03)
    6005270044507 = 1225283*4901129
\\suns2:numbers/spsp-1323/1_0_0_1.lg2 (1999Jan03)
    7928173529251 = 1407851*5631401
\\suns2:numbers/spsp-1323/3_4_3_4.lg2 (1999Jan10)
    8055526015153 = 2006929*4013857 [*]
\\suns2:numbers/spsp-1323/1_1_0_1.lg2 (1999Jan03)
    9510594947587 = 1541963*6167849
\\suns2:numbers/spsp-1323/1_1_1_1.lg2 (1999Jan03)
    9924187357873 = 1408843*7044211
\\suns2:numbers/spsp-1323/2_2_2_2.lg2 (1999Jan03)
   10380816337921 = 1860181*5580541 [*]
\\suns2:numbers/spsp-1323/1_1_0_1.lg2 (1999Jan03)
   11305984260187 = 1681219*6724873
\\suns2:numbers/spsp-1323/2_2_2_2.lg2 (1999Jan03)
   11705412905101 = 2419237*4838473 [*]
\\suns2:numbers/spsp-1323/3_4_3_3.lg2 (1999Jan10)
   11747370971953 = 2423569*4847137 [*]
\\suns2:numbers/spsp-1323/2_0_2_1.lg2 (1999Jan03)
   12221931386701 = 2472037*4944073
\\suns2:numbers/spsp-1323/2_1_2_0.lg2 (1999Jan03)
   13585109440033 = 2127997*6383989
\\suns2:numbers/spsp-1323/2_2_0_2.lg2 (1999Jan03)
   14125927490561 = 2169941*6509821 [*]
\\suns2:numbers/spsp-1323/1_0_0_1.log (1999Jan01)
   15070413782971 = 1171*19891*647011
\\suns2:numbers/spsp-1323/2_1_0_1.lg2 (1999Jan10)
   15194034844453 = 2756269*5512537
\\suns2:numbers/spsp-1323/2_1_2_2.lg2 (1999Jan03)
   16981387733441 = 2379173*7137517 [*]
\\suns2:numbers/spsp-1323/0_1_0_0.lg2 (1999Jan02)
   18851967524167 = 2170943*8683769
\\suns2:numbers/spsp-1323/2_0_1_2.lg2 (1999Jan03)
   20852647990721 = 2636453*7909357
\\suns2:numbers/spsp-1323/0_0_0_0.cd2 (1999Jan03)
   21857026665241 = 2090791*10453951
\\suns2:numbers/spsp-1323/2_1_3_3.lg2 (1999Jan10)
   22344034251241 = 3342457*6684913 [*]
\\suns2:numbers/spsp-1323/2_2_2_0.cd2 (1999Jan03)
   22660250284261 = 1683013*13464097
\\suns2:numbers/spsp-1323/0_1_0_0.cd2 (1999Jan03)
   23577638872537 = 2171527*10857631
\\suns2:numbers/spsp-1323/0_0_1_1.cd2 (1999Jan03)
   24115772485351 = 2455391*9821561
\\suns2:numbers/spsp-1323/0_1_0_1.cd2 (1999Jan03)
   24612318663193 = 2218663*11093311
\\suns2:numbers/spsp-1323/0_0_1_0.cd2 (1999Jan03)
   25352889094807 = 2517583*10070329
\\suns2:numbers/spsp-1323/0_0_0_0.cd2 (1999Jan03)
   27097909572007 = 2602783*10411129
\\suns2:numbers/spsp-1323/0_1_1_0.cd2 (1999Jan03)
   27220482764287 = 2608663*10434649
\\suns2:numbers/spsp-1323/2_0_2_2.lg2 (1999Jan03)
   29841161381461 = 3862717*7725433
\\suns2:numbers/spsp-1323/2_2_2_2.lg2 (1999Jan03)
   32304412537741 = 4018981*8037961 [*]
\\suns2:numbers/spsp-1323/2_2_2_2.lg2 (1999Jan03)
   34676805139021 = 4163941*8327881 [*]
\\suns2:numbers/spsp-1323/2_2_2_1.lg2 (1999Jan03)
   35221371377653 = 4196509*8393017 [*]
\\suns2:numbers/spsp-1323/2_0_2_0.lg2 (1999Jan03)
   35248771513621 = 4198141*8396281[*]
\\suns2:numbers/spsp-1323/2_2_2_2.lg2 (1999Jan03)
   39980911534453 = 4471069*8942137 [*]
\\suns2:numbers/spsp-1323/1_0_0_1.cd2 (1999Jan03)
   41119967081467 = 3206243*12824969
\\suns2:numbers/spsp-1323/2_2_2_2.cd2 (1999Jan03)
   44870394402541 = 4736581*9473161[*]
\\suns2:numbers/spsp-1323/2_2_2_1.cd2 (1999Jan03)
   45910825958341 = 4791181*9582361 [*]
\\suns2:numbers/spsp-1323/5_6_5_5.cd2 (1999Jan10)
   49110566041153 = 4955329*9910657 [*]
\\suns2:numbers/spsp-1323/0_0_0_1.cd2 (1999Jan03)
   49780323665047 = 3527759*14111033
\\suns2:numbers/spsp-1323/2_2_0_0.cd2 (1999Jan03)
   50803940882701 = 5040037*10080073 [*]
\\suns2:numbers/spsp-1323/0_0_1_1.cd2 (1999Jan03)
   53476535601607 = 3656383*14625529
\\suns2:numbers/spsp-1323/2_2_2_2.cd2 (1999Jan03)
   54941963940181 = 5241277*10482553
\\suns2:numbers/spsp-1323/2_2_0_2.c2d (1999Jan03)
   59340573060161 = 4447493*13342477 [*]
\\suns2:numbers/spsp-1323/1_1_1_1.cd2 (1999Jan03)
   62012721783977 = 2624939*23624443
\\suns2:numbers/spsp-1323/2_2_2_2.cd2 (1999Jan03)
   68306092099381 = 5844061*11688121
\\suns2:numbers/spsp-1323/1_0_0_1.cd2 (1999Jan03)
   69972509495953 = 3740923*18704611
\\suns2:numbers/spsp-1323/2_0_2_1.cd2 (1999Jan03)
   83579746757653 = 6464509*12929017
\\suns2:numbers/spsp-1323/2_2_2_2.cd2 (1999Jan03)
   85744173313633 = 5346157*16038469 [*]
\\suns2:numbers/spsp-1323/2_2_2_1.cd2 (1999Jan03)
   87676890910381 = 6621061*13242121 [*]
\\suns2:numbers/spsp-1323/2_0_2_2.cd2 (1999Jan03)
   88498760116861 = 6652021*13304041 [*]
\\suns2:numbers/spsp-1323/1_1_0_1.cd2 (1999Jan03)
   92706803877187 = 4814219*19256873
\\suns2:numbers/spsp-1323/0_1_0_0.cd2 (1999Jan03)
   96012713716921 = 4382071*21910351
\\suns2:numbers/spsp-1323/2_1_2_1.cd2 (1999Jan03)
   99460864996741 = 7051981*14103961 [*]
\\suns2:numbers/spsp-1323/2_2_2_1.cd2 (1999Jan03)
  106958672854741 = 7312957*14625913 [*]
\\suns2:numbers/spsp-1323/2_0_0_2.cd2 (1999Jan03)
  109368167659453 = 7394869*14789737 [*]
\\suns2:numbers/spsp-1323/2_0_1_1.cd2 (1999Jan10)
  110006593482061 = 7416421*14832841
\\suns2:numbers/spsp-1323/2_0_2_2.cd2 (1999Jan03)
  111240847306697 = 3515693*31641229 [*]
\\suns2:numbers/spsp-1323/2_0_0_2.cd2 (1999Jan03)
  113815324808461 = 7543717*15087433 [*]
\\suns2:numbers/spsp-1323/2_2_2_3.cd2 (1999Jan10)
  116696442835801 = 7638601*15277201 [*]
\\suns2:numbers/spsp-1323/0_1_0_0.cd2 (1999Jan03)
  117534457050841 = 4848391*24241951
\\suns2:numbers/spsp-1323/2_0_2_0.cd2 (1999Jan03)
  129261138517369 = 5084509*25422541 [*]
\\suns2:numbers/spsp-1323/0_1_0_1.cd2 (1999Jan03)
  129786350545351 = 5696191*22784761
\\suns2:numbers/spsp-1323/2_0_2_0.cd2 (1999Jan03)
  131611059223381 = 8112061*16224121 [*]
\\suns2:numbers/spsp-1323/5_6_6_6.cd2 (1999Jan10)
  136037918681281 = 8247361*16494721
\\suns2:numbers/spsp-1323/2_2_3_3.cd2 (1999Jan10)
  136334985668281 = 8256361*16512721 [*]
\\suns2:numbers/spsp-1323/2_1_2_2.cd2 (1999Jan03)
  140095746491581 = 8369461*16738921 [*]
\\suns2:numbers/spsp-1323/2_1_2_2.cd2 (1999Jan03)
  143754214268701 = 8478037*16956073 [*]
\\suns2:numbers/spsp-1323/2_2_2_2.cd2 (1999Jan03)
  144196497034453 = 8491069*16982137 [*]
\\suns2:numbers/spsp-1323/1_0_1_0.cd2 (1999Jan03)
  149680671821227 = 6117203*24468809
\\suns2:numbers/spsp-1323/2_0_2_2.ce2 (1999Jan10)
  167080251101653 = 9140029*18280057
\\suns2:numbers/spsp-1323/3_3_3_4.ce2 (1999Jan11)
  170090595666001 = 9222001*18444001
\\suns2:numbers/spsp-1323/2_1_2_1.ce2 (1999Jan10)
  175981585172221 = 9380341*18760681
\\suns2:numbers/spsp-1323/2_2_2_2.ce2 (1999Jan10)
  185461348618981 = 9629677*19259353 [*]
\\suns2:numbers/spsp-1323/2_2_2_2.cd2 (1999Jan03)
  193383956980321 = 8028781*24086341 [*]
\\suns2:numbers/spsp-1323/2_2_2_1.cd2 (1999Jan03)
  201286322141921 = 8191181*24573541 [*]
\\suns2:numbers/spsp-1323/0_0_0_0.cd2 (1999Jan03)
  202132337264287 = 7108663*28434649
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++