Прости числа, които лъжат теста на Ферма

[Добромир Глухаров]

Как да ги намерим чрез Lisp например? Следното е правено в LispWorks:

Код: Избери целия код

(defun square (n)
  (* n n))
(defun divides? (a b)
  (= (rem a b) 0))
(defun find-divisor (n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? n test-divisor) test-divisor)
        (T (find-divisor n (+ test-divisor 1)))))
(defun smallest-divisor (n)
  (find-divisor n 2))
(defun prime? (n)
  (= n (smallest-divisor n)))
(defun expmod (b e m)
  (cond ((= e 0) 1)
        ((evenp e)
         (rem (square (expmod b (/ e 2) m)) m))
        (T (rem (* b (expmod b (- e 1) m)) m))))
(defun fermat-test-for-a (n test-a)
  (if (< test-a n)
      (if (= (expmod test-a n n) test-a)
          (fermat-test-for-a n (+ test-a 1))
        nil)
    T))
(defun fermat-test (n)
  (fermat-test-for-a n 1))
(defun false-fermat-iter (max-n n)
  (if (fermat-test n)
      (if (prime? n)
          (if (< n max-n)
              (false-fermat-iter max-n (+ n 1)))
            n)
    (if (< n max-n)
        (false-fermat-iter max-n (+ n 1)))))
(defun false-fermat (min-n max-n)
  (false-fermat-iter max-n min-n))

И в Listener опитах това:

Код: Избери целия код

CL-USER 15 > false-fermat 7 1247
561

CL-USER 16 > false-fermat 1247 2489
1729

[Davids]

Стана ми интересно, бих се включил, само дето „лъгането на теста на ферма“ не мога да го разшифровам като значение, а непознатият синтаксис много ме затормозява с разбирането. Ще можеш ли да споделиш заданието малко по-детайлно

[Добромир Глухаров]

Според теста на Ферма, ако е дадено цяло число $n\geq2$ и $a^n\equiv a(mod n)$ не е изпълнено за някое цяло $a$, то $n$ е съставно. Следователно, ако проверим числото $n$ с теста на Ферма за $1\leq a\leq n-1$ и сравнението остава изпълнено, то можем ли да твърдим, че $n$ е просто? 561 и 1729 са контрапримери - според теста на Ферма трябва да са прости, а всъщност са съставни.

Извинявам се - в заглавието "Прости числа" трябва да е в кавички.

[aifC]

А с Милър-Рабин теста пробва ли, казват че е по-добър.

[Добромир Глухаров]

Пробвах теста на Соловей-Щрасен:

Код: Избери целия код

(defun square (n)
  (* n n))
(defun divides? (a b)
  (= (rem a b) 0))
(defun find-divisor (n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? n test-divisor) test-divisor)
        (T (find-divisor n (+ test-divisor 1)))))
(defun smallest-divisor (n)
  (find-divisor n 2))
(defun prime? (n)
  (= n (smallest-divisor n)))
(defun minus1-nth (n)
  (if (= (rem n 2) 0)
      1
    -1))
(defun a-mth-mod-n (a m n)
  (if (<= m 0)
      1
    (rem (* a (a-mth-mod-n a (- m 1) n)) n)))
(defun J (a n)
  (cond ((= a 1) 1)
        ((= (rem a 2) 0)
         (* (J (/ a 2) n) (minus1-nth (/ (- (square n) 1) 8))))
        (T (* (J (rem n a) a) (minus1-nth (/ (* (- a 1) (- n 1)) 4))))))
(defun Solovey-Strassen-test-for-a (n test-a)
  (if (< test-a n)
      (if (= (gcd test-a n) 1)
          (if (= (rem (- (J test-a n) (a-mth-mod-n test-a (/ (- n 1) 2) n)) n) 0)
              (Solovey-Strassen-test-for-a n (+ test-a 1))
            nil)
        (Solovey-Strassen-test-for-a n (+ test-a 1)))
    T))
(defun Solovey-Strassen-test (n)
  (Solovey-Strassen-test-for-a n 1))
(defun false-Solovey-Strassen-iter (max-n n)
  (if (Solovey-Strassen-test n)
      (if (prime? n)
          (if (< n max-n)
              (false-Solovey-Strassen-iter max-n (+ n 2)))
            n)
    (if (< n max-n)
        (false-Solovey-Strassen-iter max-n (+ n 2)))))
(defun false-Solovey-Strassen (max-n)
  (false-Solovey-Strassen-iter max-n 3))

Код: Избери целия код

CL-USER 1 > false-Solovey-Strassen 2000
NIL

CL-USER 2 >

[Добромир Глухаров]

Тест на Соловей-Щрасен: Ако за поне едно $a\in[1;n)$, за което $gcd(a,n)=1$, символът на Якоби $J(a,n)\not\equiv a^{\frac{n-1}{2}}(mod\ n)$, следва, че $n$ е съставно.

Символ на Якоби: $J(a,n)=\begin{cases}1;\ a=1\\J\left(\frac{a}{2},n\right).(-1)^{\frac{n^2-1}{8}};\ a - четно\\J(n%a,a).(-1)^{\frac{(a-1)(n-1)}{4}}; в\ останалите\ случаи\end{cases}$,

където $n%a$ е остатъкът при делене $n$ на $a$.

[Добромир Глухаров]

Тест на Соловей-Щрасен: Ако за поне едно $a\in[1;n)$, за което $gcd(a,n)=1$, символът на Якоби $J(a,n)\not\equiv a^{\frac{n-1}{2}}(mod\ n)$, следва, че $n$ е съставно.

Символ на Якоби: $J(a,n)=\begin{cases}1;\ a=1\\J\left(\frac{a}{2},n\right).(-1)^{\frac{n^2-1}{8}};\ a - четно\\J(n\%a,a).(-1)^{\frac{(a-1)(n-1)}{4}}; в\ останалите\ случаи\end{cases}$,

където $n\%a$ е остатъкът при делене $n$ на $a$.