Finding good multipliers

Given a modulus m, find a multiplier a so that the recurrence x = a x mod m starting with x = 1 goes through all the integers from 1 to m − 1.

Sub FindGoodMultiplier( _
  ByVal Modulus As Long, _
  Optional ByVal OverflowAt As Long = 32767)

  Dim Multiplier As Long
  Dim Hit() As Boolean
  Dim m As Long
  Dim x As Long
  Dim i As Long

  Do While Modulus > 1
    ReDim Hit(1 To Modulus - 1) As Boolean
    m = OverflowAt \ Modulus
    If m >= Int(Modulus ^ (2 / 3)) Then m = Int(Modulus ^ (2 / 3))
    For Multiplier = m To 2 Step -1
      For i = 1 To Modulus - 1: Hit(i) = False: Next i
      x = 1
      For i = 2 To Modulus - 1
        If x = 0 Then Exit For
        If Hit(x) Then Exit For
        Hit(x) = True
        x = (x * Multiplier) Mod Modulus
      Next i
      If i > Modulus - 1 Then
        Debug.Print Multiplier & " is a good multiplier for modulus " & Modulus
        Exit Sub
      End If
    Next Multiplier
    Modulus = Modulus - 1
    DoEvents
  Loop

  Debug.Print "No good multiplier was found"

End Sub

FindGoodMultiplier 32768, 2147483647
1020 is a good multiplier for modulus 32749

FindGoodMultiplier 100
21 is a good multiplier for modulus 97

   1  21  53  46  93  13  79  10  16  45  72  57  33  14   3  63  62  41  85  39
  43  30  48  38  22  74   2  42   9  92  89  26  61  20  32  90  47  17  66  28
   6  29  27  82  73  78  86  60  96  76  44  51   4  84  18  87  81  52  25  40
  64  83  94  34  35  56  12  58  54  67  49  59  75  23  95  55  88   5   8  71
  36  77  65   7  50  80  31  69  91  68  70  15  24  19  11  37

FindGoodMultiplier 128
23 is a good multiplier for modulus 128

   1  23  21 102  60 110 117  24  44 123  35  43 100  14  68  40  31  78  16 114
  82 108  71 109  94   3  69  63  52  53  76  97  72   5 115 105   2  46  42  77
 120  93 107  48  88 119  70  86  73  28   9  80  62  29  32 101  37  89  15  91
  61   6  11 126 104 106  25  67  17  10 103  83   4  92  84  27 113  59  87  96
  49 111  13  45  19  56  18  33 124  58  64  75  74  51  30  55 122  12  22 125
  81  85  50   7  34  20  79  39   8  57  41  54  99 118  47  65  98  95  26  90
  38 112  36  66 121 116

FindGoodMultiplier 512
63 is a good multiplier for modulus 509

   1  63 406 128 429  50  96 449 292  72 464 219  54 348  37 295 261 155  94 323
 498 325 115 119 371 468 471 151 351 226 495 136 424 244 102 318 183 331 493  10
 121 497 262 218 500 451 418 375 211  59 154  31 426 370 405  65  23 431 176 399
 196 132 172 147  99 129 492 456 224 369 342 168 404   2 126 303 256 349 100 192
 389  75 144 419 438 108 187  74  81  13 310 188 137 487 141 230 238 233 427 433
 302 193 452 481 272 339 488 204 127 366 153 477  20 242 485  15 436 491 393 327
 241 422 118 308  62 343 231 301 130  46 353 352 289 392 264 344 294 198 258 475
 403 448 229 175 336 299   4 252  97   3 189 200 384 269 150 288 329 367 216 374
 148 162  26 111 376 274 465 282 460 476 466 345 357  95 386 395 453  35 169 467
 408 254 223 306 445  40 484 461  30 363 473 277 145 482 335 236 107 124 177 462
  93 260  92 197 195  69 275  19 179  79 396   7 441 297 387 458 350 163  89   8
 504 194   6 378 400 259  29 300  67 149 225 432 239 296 324  52 222 243  39 421
  55 411 443 423 181 205 190 263 281 397  70 338 425 307 508 446 103 381  80 459
 413  60 217 437  45 290 455 161 472 214 248 354 415 186  11 184 394 390 138  41
  38 358 158 283  14 373  85 265 407 191 326 178  16 499 388  12 247 291   9  58
  91 134 298 450 355 478  83 139 104 444 486  78 333 110 313 377 337 362 410 380
  17  53 285 140 167 341 105 507 383 206 253 160 409 317 120 434 365  90  71 401
 322 435 428 496 199 321 372  22 368 279 271 276  82  76 207 316  57  28 237 170
  21 305 382 143 356  32 489 267  24 494  73  18 116 182 268  87 391 201 447 166
 278 208 379 463 156 157 220 117 245 165 215 311 251  34 106  61 280 334 173 210
 505 257 412 506 320 309 125 240 359 221 180 142 293 135 361 347 483 398 133 235
  44 227  49  33  43 164 152 414 123 114  56 474 340  42 101 255 286 203  64 469
  25  48 479 146  36 232 364  27 174 273 402 385 332  47 416 249 417 312 314 440
 234 490 330 430 113 502  68 212 122  51 159 346 420 501   5 315 503 131 109 250
 480 209 442 360 284  77 270 213 185 457 287 266 470  88 454  98  66  86 328 304
 319 246 228 112 439 171  84 202