| 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 |