Sorcerean Primes

'Program for generating maximum Sorcerean Primes
'-----------------------------------------------

'8821867028551 is prime, and when reduced modulo 2^n the residue is also prime, for any n. ( nb: 1 is considered a prime here :p )

'Primes of this form are called Sorcerean Primes. They are useful as multipliers in hash functions, due them remaining prime no matter the modulus / bit-length of the output.

'Another consideration is protecting avalanche characteristics. If the multipler is much smaller than the modulus, then there is insufficient mixing of the bits. So multiplers should be large, and have as "few" consecutive zeroes as realistically possible.

'We can compute the largest Sorcerean Prime, given the maximum number of consecutive zeros allowed. This integer sequence goes: 7, 107, 9829, 9829, 295973, 8660611, 1086357773, 104759050307, 1101728322077, and so on...

_DEFINE A-Z AS _UNSIGNED _INTEGER64
TYPE st_t
  p AS _INTEGER64
  n AS _INTEGER64
  z AS INTEGER
END TYPE

DIM SHARED st(255) AS st_t
DIM SHARED std AS INTEGER

FOR mz = 0 TO 15 'maximum number of consecutive zeroes
  big = 0
  Push 2, 1, 0 'feed the stack

  WHILE std > 0

    GOSUB Pop

    'if we are not yet at max zeroes, the 0 branch is ok, so push to stack
    IF z < mz THEN Push p * 2&&, n, z + 1

    'consider appending 1
    n = n + p

    'is it prime?
    f = 1
    IF n > 1 THEN
      a = SQR(n)
      FOR j = 2 TO a
        IF (n \ j) * j = n THEN f = 0: j = a
      NEXT
    END IF

    'if prime, the 1 branch is ok so push to stack
    IF f = 1 THEN
      Push p * 2&&, n, 0
      IF n > big THEN big = n
    END IF

  WEND
  PRINT mz; "::"; big: SLEEP
NEXT

END

Pop:
p = st(std).p
n = st(std).n
z = st(std).z
std = std - 1
RETURN

SUB Push (p, n, z)
  std = std + 1
  st(std).p = p
  st(std).n = n
  st(std).z = z
END SUB