Ticket #1535 (new enhancement)

Opened 14 months ago

`prime?' function does not check if x < 2.

Reported by: anonymous Owned by: djhaskin987
Priority: trivial Milestone:
Component: djhaskin987/miller-rabin.plt Keywords: primality exhaustive
Cc: Version: (1 4)
Racket Version:

Description

It seems that (prime? 1 2 random) will cause an infinite loop. See fixed version below (perhaps not the best solution). The only change is at the start of the function: (cond ((< x 2) #f) ((or (= x 2) (= x 3)) #t)

(define (prime? x k (rng random))

(cond ((< x 2)

#f)

((or (= x 2) (= x 3))

#t)

((let-values (((s d) (get-s-d (sub1 x))))

(let loop ((i 0))

(if (>= i k)

#t

(let ((test (mod-exp (add1 (rng (- x 3))) d x)))

(if (or (= test 1) (= test (sub1 x)))

(loop (add1 i))
(let carmichael-test ((r 1)

(ctest (modulo (* test test) x)))

(cond ((>= r s)

#f)

((= ctest 1)

#f)

((= ctest (sub1 x))

(loop (add1 i)))

(else

(carmichael-test (add1 r) (modulo (* ctest ctest) x)))))))))))))

Note: See TracTickets for help on using tickets.