Sorceress

Sorcerean Primes

May 17th, 2020
214
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. 'Program for generating maximum Sorcerean Primes
  2. '-----------------------------------------------
  3.  
  4. '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 )
  5.  
  6. '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.
  7.  
  8. '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.
  9.  
  10. '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...
  11.  
  12. _DEFINE A-Z AS _UNSIGNED _INTEGER64
  13. TYPE st_t
  14.   p AS _INTEGER64
  15.   n AS _INTEGER64
  16.   z AS INTEGER
  17. END TYPE
  18.  
  19. DIM SHARED st(255) AS st_t
  20. DIM SHARED std AS INTEGER
  21.  
  22. FOR mz = 0 TO 15 'maximum number of consecutive zeroes
  23.   big = 0
  24.   Push 2, 1, 0 'feed the stack
  25.  
  26.   WHILE std > 0
  27.  
  28.     GOSUB Pop
  29.  
  30.     'if we are not yet at max zeroes, the 0 branch is ok, so push to stack
  31.     IF z < mz THEN Push p * 2&&, n, z + 1
  32.  
  33.     'consider appending 1
  34.     n = n + p
  35.  
  36.     'is it prime?
  37.     f = 1
  38.     IF n > 1 THEN
  39.       a = SQR(n)
  40.       FOR j = 2 TO a
  41.         IF (n \ j) * j = n THEN f = 0: j = a
  42.       NEXT
  43.     END IF
  44.  
  45.     'if prime, the 1 branch is ok so push to stack
  46.     IF f = 1 THEN
  47.       Push p * 2&&, n, 0
  48.       IF n > big THEN big = n
  49.     END IF
  50.  
  51.   WEND
  52.   PRINT mz; "::"; big: SLEEP
  53. NEXT
  54.  
  55. END
  56.  
  57. Pop:
  58. p = st(std).p
  59. n = st(std).n
  60. z = st(std).z
  61. std = std - 1
  62. RETURN
  63.  
  64. SUB Push (p, n, z)
  65.   std = std + 1
  66.   st(std).p = p
  67.   st(std).n = n
  68.   st(std).z = z
  69. END SUB
RAW Paste Data