Carmichael numbers and Miller-Rabin test in E1.2.8

gyumni | Aug. 22, 2019, 6:43 a.m.

卡迈克尔数字mathematics and engineeringmath要求准确,可控制的

mathematics and engineering要求精确%到那几位,ok了


for every a<n, a = 2 a+1

a的n次幂除以n是否等于a,我要知道一下替代模型,和steps什么关系

10:06:39/2019-08-23

nontrivial square root of 1 modulo n

非平凡平方根

用model sutituted 测试exp 6 7 7,每个spuare都mod 7得一,但是 667是错误的

再测一下exp 3 9 9,看一下spu会不会被fooled ,

当 exp被除以2的时候,已经是在找s,了,当第一次为odd的时候,exp变为d,那a的d次幂是否等于一(or n-1a s da s d 2


(x-1)(x+1)或x=p-1

(x=p-1可能是负一的情况


)(define (expmod base exp m)

  (cond ((= exp 0) 1)

        ((even? exp)

         (remainder (square (expmod base (/ exp 2) m))

                    m))

        (else

         (remainder (* base (expmod base (- exp 1) m))

                    m))))

如果else不等于n-1,and thats

(define (fermat-test n)

  (define (try-it a)

    (= (expmod a (- n 1) n) 1))

  (try-it (+ 1 (random (- n 1)))))

don't equal to 

 

 

19:43:36

08/23/2019

已经计算出来了,但是算法复杂度没有减少,只是不能fooled了

 

About Us

brown1730and...

yysdll

为什么会说model subtituite 因为46里面说解释E1.2.5,她让我想到了,没有model,只有fuction,实话,我并没有看到实际的,只是记住了exp,exp-fast,n 或者log的式子,应该有模型的,就是通过1.1.5的替代fib有两个

Know more about EOPL! Know more about SICP!