-
+ 40350A3C1EE93BCF02AE34E2D7AED472BA7B852BBBEA3BD6DA4DEA6A304A665956B9A4839D6C2FD64E6D26B21E6C9C8937C65D17381715BB80184501849E177Effa/demos/2048_rng_prime.peh(0 . 0)(1 . 219)
13 (----------------------------------------------------------------------------)
14 (----------------------------------------------------------------------------)
15 (- Demo Tape for 'Peh'; produces a random probable-prime of the given form. -)
16 (- -)
17 (- (C) 2019 Stanislav Datskovskiy ( www.loper-os.org ) -)
18 (- http://wot.deedbot.org/17215D118B7239507FAFED98B98228A001ABFFC7.html -)
19 (- -)
20 (- You do not have, nor can you ever acquire the right to use, copy or -)
21 (- distribute this software ; Should you use this software for any purpose, -)
22 (- or copy and distribute it to anyone or in any manner, you are breaking -)
23 (- the laws of whatever soi-disant jurisdiction, and you promise to -)
24 (- continue doing so for the indefinite future. In any case, please -)
25 (- always : read and understand any software ; verify any PGP signatures -)
26 (- that you use - for any purpose. -)
27 (- -)
28 (- See also http://trilema.com/2015/a-new-software-licensing-paradigm . -)
29 (----------------------------------------------------------------------------)
30 (----------------------------------------------------------------------------)
31
32 (----------------------------------------------------------------------------)
33
34 ( Largest Primorial which fits in a 2048-bit FZ : )
35
36 @Primorial@ ( Regs : none )
37 .48CB4F7B0A023C393C0A4F253FFE4D1905DEFDF482D0C7754B59B612E3B741995
38 87DC933268A053E59F021733C80D558BF9CBBAD3A38E2FB5D4BA3157227E8ACA0
39 ACF379238AFA8DB31110AF0C566DC5DBC5C8E783E1566B3B44A4E35FFC2BFE481
40 C533A1609E99A1C9AF81C8F634F7400FBD1355D091FAB7B9AFF302AAC9D60C15C
41 29E3396A18523E177B1DA3898FF1F8BF74A2CC40032736A65B25B5908950863A8
42 019065A073EBF20164F14EA4338530C2818F208BAEEB2A810A9862A09B8ADE3BE
43 BDD7CF7DC88ECB1722F7ED2DAD24FE5C4851F7D6681CA2B97306BAC70E37D177C
44 139E2688AF33E5CCEF102A2AE35276983DDCABA3720E5C165EB88C0FE
45 ;
46
47 (----------------------------------------------------------------------------)
48
49 ( Number of 'passing' M-R shots required before we will say that a candidate
50 integer is a 'probable prime': 32. Can change this if you dare. )
51
52 @MR-Shots@ ( Regs : none )
53 .20
54 ;
55
56 (----------------------------------------------------------------------------)
57
58 ( Bitmask imposed, via logical OR, on the randomly-generated candidates.
59 Consists of a 1 in the uppermost position for the current FZ width,
60 and a 1 in the lowermost position, to give ODD integers of desired width. )
61
62 @Candidate-Bitmask@ ( Regs : none )
63 .1
64 .0 ~ W
65 .1 -
66 LS
67 .1
68 |
69 ;
70
71 (----------------------------------------------------------------------------)
72
73 ( Take an integer N from stack.
74 N MUST BE > 1; assumed to be true, given that the Candidate Bitmask is > 1.
75 if N is Relatively Prime vs. Primorial:
76 Return 0;
77 else:
78 return 1. )
79
80 @Primorial-Litmus@ ( Regs : none )
81
82 ( N is on the stack already. Now find GCD(N, Primorial) : )
83 @Primorial! G
84
85 ( Was the GCD equal to 1 ? )
86 .1 =
87
88 ( Invert the answer; i.e. a 'fail' will result in 1, a 'pass' -- 0 : )
89 .1 ^
90 ;
91
92 (----------------------------------------------------------------------------)
93
94 ( Take a Bitmask specifying the bits that must be set to 1, from the stack.
95 Generate RANDOM integers, until obtains one that, when OR'd with Bitmask,
96 passes the Primorial Litmus. )
97
98 @Make-Candidate@ ( Regs : u, m, z )
99
100 ( Get the Bitmask from the stack, and assign to m : )
101 $m
102
103 ( Begin a loop: )
104 :
105
106 ( u := u + 1 , i.e. increment the 'RNG shots' counter: )
107 u .1 + $u
108
109 ( Generate a random FZ of the current FZ width : )
110 ?
111
112 ( Take the mandatory-ones Bitmask, and OR it into
113 the random FZ from above, then store this to z: )
114 m | $z
115
116 ( Run z through the Primorial Litmus: )
117 z @Primorial-Litmus!
118
119 ( If 1, i.e. Litmus failed, cycle the loop; otherwise we're done: )
120 ,
121
122 ( Return the z which passed the Primorial Litmus: )
123 z
124 ;
125
126 (----------------------------------------------------------------------------)
127
128 ( Take integers N and I from stack (I is on the top of stack, followed by N) ;
129 Fire up to I shots of Miller-Rabin Test on N, each with a RANDOM witness;
130
131 If ALL I shots PASSED, i.e. M-R did NOT 'find composite' in any of them :
132 Return 0;
133 else (i.e. if any shot FAILED) :
134 Return 1 IMMEDIATELY. )
135
136 @Iterated-MR-Test@ ( Regs : i, n, r )
137 ( i := Maximum number of Miller-Rabin shots that we will perform : )
138 $i
139
140 ( n := N, i.e. store a copy of N: )
141 $n
142
143 ( Begin a loop: )
144 :
145
146 ( Put n on the stack: )
147 n
148
149 ( Generate a random Witness for this shot: )
150 ?
151 ( Recall that it will always be brought into the valid range,
152 automatically, in constant time. See also Ch. 16A. )
153
154 ( Run a M-R test; outputs 1 if FOUND composite, and 0 if NOT: )
155 P
156
157 ( r := result )
158 $r
159
160 ( i := i - 1 , i.e. decrement the shots counter: )
161 i .1 - $i
162
163 ( If any shots still remain... )
164 i .0 >
165
166 ( Invert the M-R result: if 'NOT found composite', give a 1 : )
167 r .1 ^
168
169 ( ...shots remain, AND current one did not 'find composite' : )
170 &
171
172 ( ... then have a 1, and we cycle the loop, for the next shot;
173 Otherwise, we're done: )
174 ,
175
176 ( At this point, N has failed a M-R shot, or passed all of the shots;
177 In either case, we return r,
178 which will be 0 IFF all shots passed, and otherwise 1 : )
179 r
180 ;
181
182 (------------------------------ Main Program : ------------------------------)
183
184 ( Regs: u, t, k, x )
185
186 ( Initialize u, 'RNG' counter, i.e. how many random FZ were needed : )
187 .0 $u
188
189 ( Initialize t, 'tries' counter, i.e. how many GCD-filtered candidates tried: )
190 .0 $t
191
192 ( Initialize k to the Bitmask that is to be imposed on candidates : )
193 @Candidate-Bitmask! $k
194
195 ( Begin the main loop: )
196 :
197
198 ( t := t + 1 , i.e. increment the 'tries' counter: )
199 t .1 + $t
200
201 ( Get a candidate x, using Bitmask k, which passes Primorial Litmus: )
202 k @Make-Candidate! $x
203
204 ( Perform MR-Shots of the Miller-Rabin Test: )
205 x @MR-Shots! @Iterated-MR-Test!
206
207 ( If not yet found a candidate which passed both the initial Primorial Litmus
208 and then the full number of M-R shots, then cycle the loop : )
209 ,
210
211 ( At this point, we have found a 'probable prime' candidate, and will print: )
212
213 ( ... the Bitmask used : )
214 [Bitmask Imposed on Candidates : ] k #
215
216 ( ... the number of 'passing' M-R shots required for termination : )
217 [Number of Mandated M-R Shots : ] @MR-Shots! #
218
219 ( ... the 'RNG shots' counter : )
220 [Total Number of Random FZ Used : ] u #
221
222 ( ... the 'tries' counter, i.e. how many passed Primorial Litmus : )
223 [GCD-Filtered Candidates Tested : ] t #
224
225 ( ... finally, the candidate which passed all of the requested tests : )
226 [Probable Prime Integer : ] x #
227
228 ( Now, terminate with a 'Yes' Verdict, as we have succeeded : )
229 QY
230
231 (--------------------------------~~The End~~---------------------------------)