 # 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