Рубрики

Тест на первичность | Набор 2 (метод Ферма)

Учитывая число n, проверьте, является ли оно простым или нет. Мы представили и обсудили школьный метод тестирования на примитивность в наборе 1.

Тест на первичность | Комплект 1 (Введение и школьный метод)

В этом посте обсуждается метод Ферма. Этот метод является вероятностным и основан на приведенной ниже маленькой теореме Ферма.

Fermat's Little Theorem:
If n is a prime number, then for every a, 1 < a < n-1,

an-1 ≡ 1 (mod n)
 OR 
an-1 % n = 1 
 

Example: Since 5 is prime, 24 ≡ 1 (mod 5) [or 24%5 = 1],
         34 ≡ 1 (mod 5) and 44 ≡ 1 (mod 5) 

         Since 7 is prime, 26 ≡ 1 (mod 7),
         36 ≡ 1 (mod 7), 46 ≡ 1 (mod 7) 
         56 ≡ 1 (mod 7) and 66 ≡ 1 (mod 7) 

Refer this for different proofs.

Если данное число простое, тогда этот метод всегда возвращает true. Если данное число является составным (или не простым), то оно может возвращать true или false, но вероятность получения неверного результата для составного является низкой и может быть уменьшена путем выполнения большего количества итераций.

Ниже приведен алгоритм:

// Higher value of k indicates probability of correct
// results for composite inputs become higher. For prime
// inputs, result is always correct
1)  Repeat following k times:
      a) Pick a randomly in the range [2, n - 2]
      b) If gcd(a, n)  1, then return false
      c) If an-1 &nequiv; 1 (mod n), then return false
2) Return true [probably prime]. 

Ниже приведена реализация вышеуказанного алгоритма. Код использует степенную функцию из модульного экспонирования

C ++

// C ++ программа для поиска наименьшего двойника в заданном диапазоне
#include <bits/stdc++.h>

using namespace std;

  
/ * Итеративная функция для вычисления (a ^ n)% p в O (логика) * /

int power(int a, unsigned int n, int p)

{

    int res = 1;      // Инициализировать результат

    a = a % p;  // Обновляем 'a' if 'a'> = p

  

    while (n > 0)

    {

        // Если n нечетно, умножаем 'a' на результат

        if (n & 1)

            res = (res*a) % p;

  

        // n должно быть даже сейчас

        n = n>>1; // n = n / 2

        a = (a*a) % p;

    }

    return res;

}

  
/ * Рекурсивная функция для вычисления gcd из 2 чисел * /

int gcd(int a, int b)

{

    if(a < b)

        return gcd(b, a);

    else if(a%b == 0)

        return b;

    else return gcd(b, a%b);  

}

  
// Если n простое, то всегда возвращает true, если n
// составной, чем возвращает ложь с высокой вероятностью
// Более высокое значение k увеличивает вероятность правильного
// результат.

bool isPrime(unsigned int n, int k)

{

   // Угловые шкафы

   if (n <= 1 || n == 4)  return false;

   if (n <= 3) return true;

  

   // Попробуйте k раз

   while (k>0)

   {

       // Выбрать случайное число в [2..n-2]

       // Выше угловых случаев убедитесь, что n> 4

       int a = 2 + rand()%(n-4);  

  

       // Проверка, если a и n взаимно просты

       if (gcd(n, a) != 1)

          return false;

   

       // Маленькая теорема Ферма

       if (power(a, n-1, n) != 1)

          return false;

  

       k--;

    }

  

    return true;

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    int k = 3;

    isPrime(11, k)?  cout << " true\n": cout << " false\n";

    isPrime(15, k)?  cout << " true\n": cout << " false\n";

    return 0;

}

Джава

// Java-программа для поиска
// самый маленький близнец в данном диапазоне

  

import java.io.*;

import java.math.*;

  

class GFG {

      

    / * Итеративная функция для расчета

    // (a ^ n)% p в O (логика) * /

    static int power(int a,int n, int p)

    {

        // Инициализировать результат

        int res = 1;

          

        // Обновляем 'a' if 'a'> = p

        a = a % p; 

      

        while (n > 0)

        {

            // Если n нечетно, умножаем 'a' на результат

            if ((n & 1) == 1)

                res = (res * a) % p;

      

            // n должно быть даже сейчас

            n = n >> 1; // n = n / 2

            a = (a * a) % p;

        }

        return res;

    }

      

    // Если n простое, то всегда возвращает true,

    // Если n составное, то возвращает false с

    // высокая вероятность, большее значение k увеличивается

    // вероятность правильного результата.

    static boolean isPrime(int n, int k)

    {

    // Угловые шкафы

    if (n <= 1 || n == 4) return false;

    if (n <= 3) return true;

      

    // Попробуйте k раз

    while (k > 0)

    {

        // Выбрать случайное число в [2..n-2]

        // Выше угловых случаев убедитесь, что n> 4

        int a = 2 + (int)(Math.random() % (n - 4)); 

      

        // Маленькая теорема Ферма

        if (power(a, n - 1, n) != 1)

            return false;

      

        k--;

        }

      

        return true;

    }

      

    // Программа для водителя

    public static void main(String args[])

    {

        int k = 3;

        if(isPrime(11, k))

            System.out.println(" true");

        else

            System.out.println(" false");

        if(isPrime(15, k))

            System.out.println(" true");

        else

            System.out.println(" false");

              

    }

}

  
// Этот код предоставлен Никитой Тивари.

PHP

<?php
// PHP программа для поиска
// самый маленький близнец в данном диапазоне

  
// Итеративная функция для расчета
// (a ^ n)% p в O (логи)

function power($a, $n, $p)

{

      

    // Инициализировать результат

    $res = 1; 

      

    // Обновляем 'a' if 'a'> = p

    $a = $a % $p

  

    while ($n > 0)

    {

          

        // Если n нечетно, умножаем

        // 'a' с результатом

        if ($n & 1)

            $res = ($res * $a) % $p;

  

        // n должно быть даже сейчас

        $n = $n >> 1; // n = n / 2

        $a = ($a * $a) % $p;

    }

    return $res;

}

  
// Если n простое, то всегда
// возвращает true, если n
// составной, чем возврат
// ложь с высокой вероятностью
// Чем выше значение k увеличивается
// вероятность верного
// результат.

function isPrime($n, $k)

{

      

    // Угловые шкафы

    if ($n <= 1 || $n == 4) 

    return false;

    if ($n <= 3) 

    return true;

      

    // Попробуйте k раз

    while ($k > 0)

    {

          

        // Выбрать случайное число

        // в [2..n-2]

        // Выше угловых случаев

        // убедиться, что n> 4

        $a = 2 + rand() % ($n - 4); 

      

        // Маленькая теорема Ферма

        if (power($a, $n-1, $n) != 1)

            return false;

      

        $k--;

    }

  

    return true;

}

  
// Код драйвера

$k = 3;

$res = isPrime(11, $k) ? " true\n": " false\n";

echo($res);

  

$res = isPrime(15, $k) ? " true\n": " false\n";

echo($res);

  
// Этот код предоставлен Ajit.
?>


Выход:

true
false

Временная сложность этого решения составляет O (k Log n). Обратите внимание, что функция питания занимает O (Log n) время.

Обратите внимание, что приведенный выше метод может потерпеть неудачу, даже если мы увеличим количество итераций (большее k). Существуют некоторые составные числа со свойством, которое для каждого a <n, gcd (a, n) = 1 и a n-1 ≡ 1 (mod n) . Такие числа называются числами Кармайкла . Тест простоты Ферма часто используется, если для фильтрации необходим быстрый метод, например, на этапе генерации ключа криптографического алгоритма открытого ключа RSA.

Вскоре мы будем обсуждать больше методов для тестирования Primality.


Ссылки:

https://en.wikipedia.org/wiki/Fermat_primality_test
https://en.wikipedia.org/wiki/Prime_number
http://www.cse.iitk.ac.in/users/manindra/presentations/FLTBasedTests.pdf
https://en.wikipedia.org/wiki/Primality_test

Эта статья предоставлена Ajay . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Тест на первичность | Набор 2 (метод Ферма)

0.00 (0%) 0 votes