Debian Codegraph @

lib/math/prime.scm

raw
1 ;;;
2 ;;; math/prime.scm - utilities related to prime numbers
3 ;;;
4 ;;; Copyright (c) 2013-2024 Shiro Kawai <[email protected]>
5 ;;; Copyright (c) 2013 @cddddr
6 ;;;
7 ;;; Redistribution and use in source and binary forms, with or without
8 ;;; modification, are permitted provided that the following conditions
9 ;;; are met:
10 ;;;
11 ;;; 1. Redistributions of source code must retain the above copyright
12 ;;; notice, this list of conditions and the following disclaimer.
13 ;;;
14 ;;; 2. Redistributions in binary form must reproduce the above copyright
15 ;;; notice, this list of conditions and the following disclaimer in the
16 ;;; documentation and/or other materials provided with the distribution.
17 ;;;
18 ;;; 3. Neither the name of the authors nor the names of its contributors
19 ;;; may be used to endorse or promote products derived from this
20 ;;; software without specific prior written permission.
21 ;;;
22 ;;; THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
23 ;;; "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
24 ;;; LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
25 ;;; A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
26 ;;; OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
27 ;;; SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
28 ;;; TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
29 ;;; PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
30 ;;; LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
31 ;;; NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
32 ;;; SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
33 ;;;
34
35 (define-module math.prime
36 (use srfi.27)
37 (use srfi.42)
38 (use gauche.uvector)
39 (use gauche.generator)
40 (use gauche.sequence)
41 (use gauche.threads)
42 (use data.sparse)
43 (use util.match)
44 (export primes *primes* reset-primes
45 small-prime? *small-prime-bound*
46 miller-rabin-prime? bpsw-prime?
47 naive-factorize mc-factorize
48 jacobi totient))
49 (select-module math.prime)
50
51 ;;;
52 ;;; Infinite sequence of prime numbers
53 ;;;
54
55 ;; This section of code is based on the segment sieve prime number generator
56 ;; written by @cddddr. Optimized by SK. As of 0.9.4_pre2, it can generate
57 ;; first 10^7 primes in 14sec on 2.4GHz Core2 machine.
58
59 (define (take-first-term a0 d lower-bound)
60 (if (<= lower-bound a0)
61 a0
62 (+ a0 (* d (quotient (- lower-bound a0 (- d) 1) d)))))
63 (define (->odd x) (if (odd? x) x (+ x 1)))
64 (define (->even x) (if (even? x) x (+ x 1)))
65 (define-inline (integer->index x) (ash x -1))
66
67 (define-constant *segment-size* (->even #e5e4))
68 (define-constant *first-segment-start*
69 (->odd (ceiling->exact (expt *segment-size* 0.6))))
70 (define-constant *sieve-vec-size* (/ *segment-size* 2))
71 (define-constant *sieve-filler* '#u8(0))
72
73 ;; sieve is a bytevector, representing a range of odd numbers.
74 ;; given odd number N in the range [start, end] (where start and end
75 ;; are both odd), (vector-ref bytevec (/ (- N start) 2)) is 0 if N
76 ;; is composite, 1 if not.
77 (define (segment-sieve! bytevec start primes)
78 (let ([root (floor->exact (sqrt (+ start *segment-size* -1)))]
79 [start-index (integer->index start)])
80 (let sieve! ([ps (cdr primes)])
81 (match-let1 (p . qs) ps
82 (when (<= p root)
83 (let1 i (- (take-first-term (integer->index (* p p)) p start-index)
84 start-index)
85 (u8vector-multi-copy! bytevec i p *sieve-filler*))
86 (sieve! qs))))))
87
88 (define (bytevec->generator bytevec start)
89 (let1 i 0
90 (^[] (let loop ([j i])
91 (cond [(>= j *sieve-vec-size*) (set! i j) (eof-object)]
92 [(not (zero? (u8vector-ref bytevec j)))
93 (set! i (+ j 1))
94 (+ (* j 2) start)]
95 [else (loop (+ j 1))])))))
96
97 (define (segment-prime-generator start primes)
98 (let1 bytevec (make-u8vector *sieve-vec-size* 1)
99 (segment-sieve! bytevec start primes)
100 (bytevec->generator bytevec start)))
101
102 ;; Head of prime sequence. We don't make it a generator,
103 ;; for we only need to calculate them once and it won't
104 ;; take long. We just wrap it with delay so that it won't
105 ;; tax loading time.
106 (define *small-primes*
107 (delay (list-ec (:range n 2 *first-segment-start*)
108 (if (every?-ec (:range j 2 (+ 1 (floor->exact (sqrt n))))
109 (< 0 (mod n j))))
110 n)))
111
112 ;; API
113 (define (primes)
114 (define start *first-segment-start*)
115 (define gen (list->generator (force *small-primes*)))
116 (define (gen-primes)
117 (let loop ([v (gen)])
118 (if (eof-object? v)
119 (begin
120 (set! gen (segment-prime-generator start prime-lseq))
121 (inc! start *segment-size*)
122 (loop (gen)))
123 v)))
124 (define prime-lseq (generator->lseq gen-primes))
125 prime-lseq)
126
127 ;; API
128 (define *primes* (primes))
129
130 ;; API
131 (define (reset-primes) (set! *primes* (primes)) (undefined))
132
133 ;;;
134 ;;; Primarity test
135 ;;;
136
137 ;; We provide both deterministic and probabilistic method.
138
139 ;; single Miller-Rabin test.
140 ;; n is the number to be tested, a is the chosen base.
141 ;; returns #f if n is composite.
142 (define (miller-rabin-test a n)
143 (let* ([n-1 (- n 1)]
144 [s (twos-exponent-factor n-1)]
145 [d (ash n-1 (- s))]
146 [a^d (expt-mod a d n)])
147 (or (= a^d 1)
148 (let loop ([i 0] [a^d a^d])
149 (cond [(= i s) #f]
150 [(= a^d n-1) #t]
151 [else (loop (+ i 1) (expt-mod a^d 2 n))])))))
152
153 ;; For small integers, determinisitc Miller-Rabin is known.
154 ;; Selfridge&Wagstaff doi:10.2307/2006210
155 ;; Jaeschke doi:10.2307/2153262
156 (define *deterministic-witnesses*
157 ;; ((bound a ...) ...)
158 ;; If the number to test is less than bound, we only need to test with a ...
159 '((1373653 2 3)
160 (9080191 31 73)
161 (4759123141 2 7 61)
162 (2152302898747 2 3 5 7 11)
163 (3474749660383 2 3 5 7 11 13)
164 (341550071728321 2 3 5 7 11 13 17)))
165
166 (define *small-prime-bound*
167 (car (last *deterministic-witnesses*)))
168
169 (define (deterministic-miller-rabin n witnesses)
170 (every?-ec (: a witnesses) (miller-rabin-test a n)))
171
172 ;; If n is below *small-prime-bound*, returns deterministic
173 ;; answer. If n is over, always return #f.
174 (define (small-prime? n)
175 (if (<= n 100)
176 (boolean (memv n (take *primes* 25))) ; we have 25 primes below 100.
177 (and-let* ([ (odd? n) ]
178 [p (find (^p (< n (car p))) *deterministic-witnesses*)])
179 (deterministic-miller-rabin n (cdr p)))))
180
181 (define *miller-rabin-random-source*
182 (rlet1 s (make-random-source)
183 (random-source-pseudo-randomize! s 1 1)))
184
185 (define default-miller-rabin-random-integer
186 (random-source-make-integers *miller-rabin-random-source*))
187
188 ;; API
189 (define (miller-rabin-prime? n :key (num-tests 7)
190 (random-integer default-miller-rabin-random-integer))
191 (unless (and (exact-integer? n) (> n 1))
192 (error "exact positive integer greater than 1 is expected, but got:" n))
193 (and (odd? n) ; filter out the trivial case
194 (if (< n *small-prime-bound*)
195 (small-prime? n)
196 (let ([bound (- (integer-length n) 2)]
197 [tested '()]) ;; tested primes
198 (define (rand)
199 (let1 r (+ 2 (random-integer bound))
200 (if (memv r tested)
201 (rand)
202 (begin (push! tested r) r))))
203 (every?-ec (: k num-tests) (miller-rabin-test (rand) n))))))
204
205 ;; Jacobi symbol calculation, used in bpsw-prime?
206 ;; http://en.wikipedia.org/wiki/Jacobi_symbol
207 ;; There exists better algorithms, but let's see how the straightforward
208 ;; one goes.
209
210 ;; API
211 (define (jacobi a n) ; n is odd
212 (define (J a n s)
213 (cond [(= n 1) (* s 1)]
214 [(= a 0) 0]
215 [(odd? a)
216 (if (and (= (logand a 3) 3) (= (logand n 3) 3))
217 (J (modulo n a) a (- s))
218 (J (modulo n a) a s))]
219 [else
220 (let1 k (- (twos-exponent-factor a))
221 (if (and (memv (logand n 7) '(3 5)) (odd? k))
222 (J (ash a k) n (- s))
223 (J (ash a k) n s)))]))
224 (when (or (even? n) (< n 1))
225 (error "n must be positive odd number, but got" n))
226 (if (< a 0)
227 (J (- a) n (if (= (logand n 3) 1) 1 -1))
228 (J a n 1)))
229
230 ;; Baillie-PSW primality test
231 ;; http://www.trnicely.net/misc/bpsw.html
232 ;; It is known that this correctly identifies primes/composites below 10^17,
233 ;; and it is very likely correct below 2^64 empirically.
234
235 ;; Find first element D in the sequence (-1)^n (2n+1) where n >= 2
236 ;; and JacobiSymbol(D,N) = -1.
237 ;; D is expected to be small if N is not a perfect square.
238 (define (bpsw-find-D n)
239 (let loop ([d 5] [s 1])
240 (if (= (jacobi (* s d) n) -1)
241 (* s d)
242 (loop (+ d 2) (- s)))))
243
244 ;; Strong Lucas-Selfridge test
245 (define (lucas-selfridge-test n P Q)
246
247 ;; calculate U_d, V_d and Q^d mod n. (d is such that n = d * 2^s)
248 (define (calculate-UV n P Q D d)
249 (let1 dsize (integer-length d)
250 (let loop ([U 1] [V P] [U_2^m 1] [V_2^m P] [Q_m Q] [Q^d Q] [bit 1])
251 (if (= bit dsize)
252 (values U V Q^d)
253 (let ([U_2^m_1 (modulo (* U_2^m V_2^m) n)]
254 [V_2^m_1 (modulo (- (* V_2^m V_2^m) (* 2 Q_m)) n)]
255 [Q_m_1 (modulo (* Q_m Q_m) n)])
256 (if (not (logbit? bit d))
257 (loop U V U_2^m_1 V_2^m_1 Q_m_1 Q^d (+ bit 1))
258 (let ([U (half-modn (+ (* U_2^m_1 V) (* U V_2^m_1)))]
259 [V (half-modn (+ (* V_2^m_1 V) (* D U U_2^m_1)))]
260 [Q^d (modulo (* Q^d Q_m_1) n)])
261 (loop U V U_2^m_1 V_2^m_1 Q_m_1 Q^d (+ bit 1)))))))))
262
263 ;; divide by 2 modulo n; we know n is odd
264 (define (half-modn x)
265 (if (odd? x)
266 (modulo (ash (+ x n) -1) n)
267 (modulo (ash x -1) n)))
268
269 (let* ([n+1 (+ n 1)]
270 [s (twos-exponent-factor n+1)]
271 [d (ash n+1 (- s))]
272 [D (bpsw-find-D n)]
273 [P 1]
274 [Q (/ (- 1 D) 4)])
275 (receive (U V Q^d) (calculate-UV n P Q D d)
276 (or (zero? U)
277 (zero? V)
278 (let loop ([r 1] [V V] [Q^d Q^d])
279 (if (>= r s)
280 #f
281 (let1 V (modulo (- (* V V) (* 2 Q^d)) n)
282 (or (zero? V)
283 (loop (+ r 1) V (modulo (* Q^d Q^d) n))))))))))
284
285 ;; API
286 (define (bpsw-prime? n)
287 (cond [(< n 2) #f]
288 [(= n 2) #t]
289 [(even? n) #f]
290 [else
291 (let1 fs (naive-factorize n 1000)
292 (cond
293 [(not (null? (cdr fs))) #f] ; definitely composite
294 [(< n 1000000) #t] ; we know it's prime
295 [(not (miller-rabin-test 2 n)) #f]
296 [(zero? (values-ref (exact-integer-sqrt n) 1)) #f] ;perfect square
297 [else (lucas-selfridge-test n 1 (/ (- 1 (bpsw-find-D n)) 4))]))]))
298
299 ;;;
300 ;;; Factorization
301 ;;;
302
303 (define-constant *small-factorize-table-limit* 50000)
304
305 (define-constant *small-factorize-table-index-limit*
306 (/ (- *small-factorize-table-limit* 1) 2))
307
308 ;; suitable for small n with memoization. n is odd number.
309 ;; mem-vec[k] remembers factorization of k*2+1.
310 ;;
311 (define naive-factorize-1
312 (let1 mem-vec (atom (make-sparse-vector))
313 (define (->index n) (/ (- n 1) 2)) ; n must be odd
314 (define (memo! i val)
315 (when (< i *small-factorize-table-index-limit*)
316 (atomic mem-vec (cut sparse-vector-set! <> i val)))
317 val)
318 (^[n divisor-limit]
319 (let try [(n n) (ps *primes*)]
320 ;; try to divide n with given primes.
321 (let1 i (->index n)
322 (or (and (< i *small-factorize-table-index-limit*)
323 (atomic mem-vec (cut sparse-vector-ref <> i #f)))
324 (and (small-prime? n)
325 (memo! i `(,n)))
326 (let loop ([ps ps])
327 (let* ([p (car ps)] [p^2 (* p p)])
328 (cond [(> p divisor-limit) `(,n)] ; n can be composite, so no memo
329 [(< n p^2) (memo! i `(,n))]
330 [(= n p^2) (memo! i `(,p ,p))]
331 [else
332 (receive (q r) (quotient&remainder n p)
333 (if (zero? r)
334 (memo! i (cons p (try q ps)))
335 (loop (cdr ps))))])))))))))
336
337 ;; API
338 (define (naive-factorize n :optional (divisor-limit +inf.0))
339 (unless (and (exact-integer? n)
340 (>= n 1))
341 (error "Argument must be an exact positive integer, but got:" n))
342 (cond
343 [(= n 1) '()]
344 [(<= n 3) `(,n)]
345 [else
346 (let1 k (twos-exponent-factor n)
347 (if (= k 0)
348 (naive-factorize-1 n divisor-limit)
349 ;; avoid simple recursion to naive-factorize for every factor of 2
350 ;; to save intermediate results generation (effective when n is bignum).
351 (let loop ([i 0] [r '()])
352 (if (= i k)
353 (let1 m (ash n (- k))
354 (reverse r (if (= m 1)
355 '()
356 (naive-factorize (ash n (- k)) divisor-limit))))
357 (loop (+ i 1) (cons 2 r))))))]))
358
359 ;; Monte Carlo factorization
360 ;; R. P. Brent, An improved Monte Carlo factorization algorithm, BIT 20 (1980), 176-184.
361 ;; http://maths-people.anu.edu.au/~brent/pub/pub051.html
362
363 ;; Single trial of factorizing n using x0 as the initial seed.
364 ;; If this returns a number, it's a nontrivial divisor of n.
365 ;; If this returns #f, you need to retry with different x0.
366 (define (mc-find-divisor-1 n x0)
367 (define (f x) (modulo (+ (* x x) 3) n))
368 (define (f^ r x) ; apply f on x for r times, e.g (f (f x)) for r=2
369 (let loop ([r r] [x x])
370 (if (= r 1) (f x) (loop (- r 1) (f x)))))
371 ;; the step value m: in the big-step loop, we only compute gcd for
372 ;; every m-th value of the series x_i.
373 (define m (ceiling->exact (log n 2)))
374 ;; 'big-step' loop
375 (define (big-step x y q r k)
376 (do ([i (min m (- r k)) (- i 1)]
377 [y y (f y)]
378 [q q (modulo (* q (abs (- x y))) n)])
379 [(= i 0) (values (gcd q n) q y)]))
380 (define (big-stride x y q r)
381 (let loop ([ys y] [k 0])
382 (receive (G q y) (big-step x ys q r k)
383 (cond [(or (>= k (- r m)) (> G 1)) (values G ys y q)]
384 [else (loop y (+ k m))]))))
385 (define (small-stride x ys)
386 (let loop ([ys (f ys)])
387 (let1 G (gcd (abs (- x ys)) n)
388 (if (> G 1) G (loop (f ys))))))
389
390 ;; The main body
391 (let loop ([y x0] [r 1] [q 1])
392 (let ([x y] [y (f^ r y)])
393 (receive (G ys y q) (big-stride x y q r)
394 (if (> G 1)
395 (if (< G n)
396 G
397 (let1 G (small-stride x ys)
398 (and (< G n) G))) ; if (= G N), we failed.
399 (loop y (* r 2) q))))))
400
401 ;; Try MC factorization. Returns (divisor . quotient).
402 ;; Note: This will loop forever if N is a prime. The caller should
403 ;; exclude primes. Unfortunately, we don't have a deterministic primality
404 ;; test > 2^64 yet.
405 (define (mc-try-factorize n)
406 (let loop ()
407 (if-let1 d (mc-find-divisor-1 n (random-integer n))
408 (cons d (quotient n d))
409 (loop))))
410
411 ;; API
412 (define (mc-factorize n)
413 ;; Break up n. We first exclude primes if possible.
414 ;; The worst case scenario is that n contains a factor
415 ;; greater than 2^64---in which case we'll take forever.
416 (define (smash n)
417 (if (definite-prime? n)
418 `(,n)
419 (let1 d (mc-try-factorize n)
420 (append (smash (car d)) (smash (cdr d))))))
421
422 (define (definite-prime? n)
423 (cond [(< n *small-prime-bound*) (small-prime? n)]
424 [(< n 18446744073709551616) (bpsw-prime? n)]; (expt 2 64)
425 [else #f]))
426
427 (define try-prime-limit 1000)
428
429 ;; We exclude trivial factors first.
430 (let* ([ps (naive-factorize n try-prime-limit)]
431 [n (last ps)])
432 (if (< n (* try-prime-limit try-prime-limit))
433 ps ;; we're completely done
434 (let1 nf (smash n) ; n may be composite, so try to break it more.
435 (if (null? (cdr nf))
436 ps ; n is unbreakable, so the original factorization was fine.
437 (sort (append nf (drop-right ps 1))))))))
438
439 ;;;
440 ;;; Fun stuff
441 ;;;
442
443 (define (totient n)
444 (if (<= n 2)
445 1
446 (fold (^[pk phi] (* phi (expt (car pk) (- (length pk) 1)) (- (car pk) 1)))
447 1 (group-sequence (mc-factorize n)))))
448
449 ;; Wishlist
450 ;; deterministic prime? (maybe using AKS primality test)
451 ;; more sophisticated integer factorization