计划中的奇怪之处

Question

我试图在Scheme中实现费马的素性测试。 我编写了一个过程 fermat2（最初称为 fermat1），它返回 true 当a^p-1全等1(mod p)时（请正确阅读！！） 一个

每个素数 p 数都应该满足该过程（因此费马小定理..） 对于任何一个

但是，当我尝试计算该过程在固定次数的试验中产生正确结果的次数时......（使用代码中描述的 countt 过程）我得到了令人震惊的结果

所以我稍微改变了程序（我没有看到任何逻辑变化..可能是我瞎了）并将其命名为 fermat1 （替换旧的 fermat1 ，现在旧的 fermat1 -> fermat2）并且它起作用了..素数通过了一直进行测试...

为什么程序 fermat2 调用的次数更少...实际上是错误的？ 如果它是错误的，为什么我没有得到错误......相反，计算被跳过！！（我认为是这样！）

你所要做的就是理解我想要告诉的内容

(countt fermat2 19 100)
(countt fermat1 19 100)

并亲自看看。

代码：

;;Guys this is really weird
;;I might not be able to explain this
;;just try out
;;(countt fermat2 19 100) 
;;(countt fermat1 19 100)
;;compare both values ...
;;did you get any error using countt with fermat2,if yes please specify why u got error
;;if it was because of reminder procedure .. please tell your scheme version

;;created on 6 mar 2011 by fedvasu
;;using mit-scheme 9.0 (compiled from source/microcode)
;; i cant use a quote it mis idents (unfriendly stack overflow!)
;;fermat-test based on fermat(s) little theorem a^p-1 congruent to 1 (mod p) p is prime
;;see MIT-SICP,or Algorithms by Vazirani or anyother number theory book

;;this is the correct logic of fermat-test (the way it handles 0)
 (define (fermat1 n)
     (define (tryout a x)
;; (display "I've been called\n")
      (= (remainder (fast-exp a (- x 1)) x) 1))
                    ;;this exercises the algorithm
                    ;;1+ to avoid 0
       (define temp (random n))
       (if (= temp 0)
     (tryout (1+ temp) n)
     (tryout temp n)))

;;old fermat-test
;;which is wrong
;;it doesnt produce any error!!
;;the inner procedure is called only selective times.. i dont know when exactly 
;;uncomment the display line to see how many times tryout is called (using countt)
;;i didnt put any condition when it should be called
;;rather it should be every time fermat2 is called
;;how is it so??(is it to avoid error?)
  (define (fermat2 n)
   (define (tryout a x)
     ;; (display "I've been called\n")
      (= (remainder (fast-exp a (- x 1)) x) 1))
                     ;;this exercises the algorithm
                     ;;1+ to avoid 0
                    (tryout (1+ (random n)) n))

;;this is the dependency procedure for fermat1 and fermat2
;;this procedure calculates base^exp (exp=nexp bcoz exp is a keyword,a primitive)
;;And it is correct :)
  (define (fast-exp base nexp)
   ;;this is iterative procedure where a*b^n = base^exp is constant always
   ;;A bit tricky though
    (define (logexp a b n)
      (cond ((= n 0) a);;only at the last stage a*b^n is not same as base^exp
         ((even? n) (logexp a (square b) (/ n 2)))
         (else (logexp (* a b) b (- n 1)))))

        (logexp 1 base nexp))


 ;;utility procedure which takes a procedure and its argument and an extra 
 ;; argument times which tells number of times to call
 ;;returns the number of times result of applying proc on input num yielded true
 ;;counting the number times it yielded true
 ;;procedure yields true for fixed input,
 ;;by calling it fixed times)
 ;;uncommenting display line will help
   (define (countt proc num times)
     (define (pcount p n t c)
             (cond ((= t 0)c)
                ((p n );; (display "I'm passed by fermat1\n")
                (pcount p n (- t 1) (+ c 1)));;increasing the count
                 (else c)))
        (pcount proc num times 0))

我真的很痛苦..弄清楚它实际上做了什么..请遵循代码并告诉我们为什么会出现这种差异？

Answer 1

Even (countt fermat2 19 100) 调用两次会返回不同的结果。

让我们修复您的 fermat2，因为它更短。定义是：“如果n是素数，a是任何小于n的正整数，则a的n次方与模n全等。”。这意味着 f(a, n) = a^n mod n == a mod n。您的代码告诉 f(a, n) = a^(n-1) mod n == 1 这是不同的。如果我们根据定义重写它：

(define (fermat2 n)
  (define (tryout a x)
    (= (remainder (fast-exp a x) x) 
       (remainder a x)))

  (tryout (1+ (random n)) n))

这还不正确。 (1+ (random n)) 返回从 1 到 n 的数字，而我们需要 [1..n)：

(define (fermat2 n)
  (define (tryout a x)
    (= (remainder (fast-exp a x) x) 
       (remainder a x)))

  (tryout (+ 1 (random (- n 1))) n))

这是正确的版本，但我们可以提高它的可读性。由于您仅在 fermat2 的范围内使用 tryout ，因此不需要在参数 x 中传递 n - 后者已经绑定在 fermat2 的范围内tryout，所以最终版本是

(define (fermat n)
  (define (tryout a)
    (= (remainder (fast-exp a n) n) 
       (remainder a n)))

  (tryout (+ 1 (random (- n 1)))))

更新：

我说fermat2中使用的公式不正确。这是错误的，因为如果 a*k = b*k (mod n) 则 a = b (mod n)。 Vasu 指出的错误在于生成用于测试的随机数。