Function: math-prime-test

math-prime-test is an autoloaded and byte-compiled function defined in calc-comb.el.gz.

Signature

(math-prime-test N ITERS)

Source Code

;; Defined in /usr/src/emacs/lisp/calc/calc-comb.el.gz
(defun math-prime-test (n iters)
  (if (and (Math-vectorp n) (cdr n))
      (setq n (nth (1- (length n)) n)))
  (if (Math-messy-integerp n)
      (setq n (math-trunc n)))
  (let ((res))
    (while (> iters 0)
      (setq res
	    (cond ((and (integerp n) (<= n 5003))
		   (list (= (math-next-small-prime n) n)))
		  ((not (Math-integerp n))
		   (error "Argument must be an integer"))
		  ((Math-integer-negp n)
		   '(nil))
		  ((< n 8000000)
		   (let ((i -1) v)
		     (while (and (> (% n (setq v (aref math-primes-table
						       (setq i (1+ i)))))
				    0)
				 (< (* v v) n)))
		     (if (= (% n v) 0)
			 (list nil v)
		       '(t))))
		  ((not (equal n (car math-prime-test-cache)))
		   (cond ((if (consp n)
                              (= (% (nth 1 n) 2) 0)
                            (= (% n 2) 0))
                          '(nil 2))
			 ((if (consp n)
                              (= (% (nth 1 n) 5) 0)
                            (= (% n 5) 0))
                          '(nil 5))
			 (t (let ((q n) (sum 0))
                              (while (not (eq q 0))
                                (setq sum (%
                                           (+
                                            sum
                                            (calcFunc-mod
                                             q 1000000))
                                           111111))
                                (setq q
                                      (math-quotient
                                       q 1000000)))
			      (cond ((= (% sum 3) 0) '(nil 3))
				    ((= (% sum 7) 0) '(nil 7))
				    ((= (% sum 11) 0) '(nil 11))
				    ((= (% sum 13) 0) '(nil 13))
				    ((= (% sum 37) 0) '(nil 37))
				    (t
				     (setq math-prime-test-cache-k 1
					   math-prime-test-cache-q
					   (math-div2 n)
					   math-prime-test-cache-nm1
					   (math-add n -1))
				     (while (math-evenp
					     math-prime-test-cache-q)
				       (setq math-prime-test-cache-k
					     (1+ math-prime-test-cache-k)
					     math-prime-test-cache-q
					     (math-div2
					      math-prime-test-cache-q)))
				     (setq iters (1+ iters))
				     (list 'maybe
					   0
					   (math-sub
					    100
					    (math-div
					     '(float 232 0)
					     (math-numdigs n))))))))))
		  ((not (eq (car (nth 1 math-prime-test-cache)) 'maybe))
		   (nth 1 math-prime-test-cache))
		  (t   ; Fermat step
		   (let* ((x (math-add (calcFunc-random (math-add n -2)) 2))
			  (y (math-pow-mod x math-prime-test-cache-q n))
			  (j 0))
		     (while (and (not (eq y 1))
				 (not (equal y math-prime-test-cache-nm1))
				 (< (setq j (1+ j)) math-prime-test-cache-k))
		       (setq y (math-mod (math-mul y y) n)))
		     (if (or (equal y math-prime-test-cache-nm1)
			     (and (eq y 1) (eq j 0)))
			 (list 'maybe
			       (1+ (nth 1 (nth 1 math-prime-test-cache)))
			       (math-mul (nth 2 (nth 1 math-prime-test-cache))
					 '(float 25 -2)))
		       '(nil unknown))))))
      (setq math-prime-test-cache (list n res)
	    iters (if (eq (car res) 'maybe)
		      (1- iters)
		    0)))
    res))