Рубрики

Тест на первичность | Набор 3 (Миллер-Рабин)

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

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

В этом посте обсуждается метод Миллера-Рабина. Этот метод является вероятностным (как и Ферма), но обычно он предпочтительнее метода Ферма.

Алгоритм:

// It returns false if n is composite and returns true if n
// is probably prime.  k is an input parameter that determines
// accuracy level. Higher value of k indicates more accuracy.
bool isPrime(int n, int k)
1) Handle base cases for n < 3
2) If n is even, return false.
3) Find an odd number d such that n-1 can be written as d*2r. 
   Note that since n is odd, (n-1) must be even and r must be 
   greater than 0.
4) Do following k times
     if (millerTest(n, d) == false)
          return false
5) Return true.

// This function is called for all k trials. It returns 
// false if n is composite and returns false if n is probably
// prime.  
// d is an odd number such that  d*2r = n-1 for some r >= 1
bool millerTest(int n, int d)
1) Pick a random number 'a' in range [2, n-2]
2) Compute: x = pow(a, d) % n
3) If x == 1 or x == n-1, return true.

// Below loop mainly runs 'r-1' times.
4) Do following while d doesn't become n-1.
     a) x = (x*x) % n.
     b) If (x == 1) return false.
     c) If (x == n-1) return true. 

Пример:

Input: n = 13,  k = 2.

1) Compute d and r such that d*2r = n-1, 
     d = 3, r = 2. 
2) Call millerTest k times.

1st Iteration:
1) Pick a random number 'a' in range [2, n-2]
      Suppose a = 4

2) Compute: x = pow(a, d) % n
     x = 43 % 13 = 12

3) Since x = (n-1), return true.

IInd Iteration:
1) Pick a random number 'a' in range [2, n-2]
      Suppose a = 5

2) Compute: x = pow(a, d) % n
     x = 53 % 13 = 8

3) x neither 1 nor 12.

4) Do following (r-1) = 1 times
   a) x = (x * x) % 13 = (8 * 8) % 13 = 12
   b) Since x = (n-1), return true.

Since both iterations return true, we return true.

Реализация:
Ниже приведена реализация вышеуказанного алгоритма.

C ++

// C ++ программа теста миллеровости Рабина
#include <bits/stdc++.h>

using namespace std;

  
// Функция полезности для модульного возведения в степень.
// Возвращает (x ^ y)% p

int power(int x, unsigned int y, int p)

{

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

    x = x % p;  // Обновление x, если оно больше или

                // равно p

    while (y > 0)

    {

        // Если y нечетно, умножаем x на результат

        if (y & 1)

            res = (res*x) % p;

  

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

        y = y>>1; // y = y / 2

        x = (x*x) % p;

    }

    return res;

}

  
// Эта функция вызывается для всех k испытаний. Возвращается
// false, если n составное и возвращает false, если n
// возможно простое число
// d нечетное число такое, что d * 2 <sup> r </ sup> = n-1
// для некоторого r> = 1

bool miillerTest(int d, int n)

{

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

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

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

  

    // Вычисляем ^ d% n

    int x = power(a, d, n);

  

    if (x == 1  || x == n-1)

       return true;

  

    // Продолжаем возводить в квадрат x, пока одно из следующих действий не

    // случилось

    // (i) d не достигает n-1

    // (ii) (x ^ 2)% n не равно 1

    // (iii) (x ^ 2)% n не является n-1

    while (d != n-1)

    {

        x = (x * x) % n;

        d *= 2;

  

        if (x == 1)      return false;

        if (x == n-1)    return true;

    }

  

    // Возвращаем композит

    return false;

}

  
// Возвращает false, если n составное, и возвращает true, если n
// вероятно прост. k является входным параметром, который определяет
// уровень точности. Более высокое значение k указывает на большую точность.

bool isPrime(int n, int k)

{

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

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

    if (n <= 3) return true;

  

    // Находим r таким, что n = 2 ^ d * r + 1 для некоторого r> = 1

    int d = n - 1;

    while (d % 2 == 0)

        d /= 2;

  

    // Итерация по заданному числу 'k' раз

    for (int i = 0; i < k; i++)

         if (!miillerTest(d, n))

              return false;

  

    return true;

}

  
// Драйвер программы

int main()

{

    int k = 4;  // Количество итераций

  

    cout << "All primes smaller than 100: \n";

    for (int n = 1; n < 100; n++)

       if (isPrime(n, k))

          cout << n << " ";

  

    return 0;

}

Джава

// Java-тест Миллера-Рабина

import java.io.*;

import java.math.*;

  

class GFG {

  

    // Сервисная функция для модульной работы

    // возведение в степень. Возвращает (x ^ y)% p

    static int power(int x, int y, int p) {

          

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

          

        // Обновление x, если оно больше или

        // равно p

        x = x % p; 

  

        while (y > 0) {

              

            // Если y нечетно, умножаем x на результат

            if ((y & 1) == 1)

                res = (res * x) % p;

          

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

            y = y >> 1; // y = y / 2

            x = (x * x) % p;

        }

          

        return res;

    }

      

    // Эта функция вызывается для всех k испытаний.

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

    // возвращает false, если n, вероятно, простое число.

    // d нечетное число такое, что d * 2 <sup> r </ sup>

    // = n-1 для некоторого r> = 1

    static boolean miillerTest(int d, int n) {

          

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

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

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

      

        // Вычисляем ^ d% n

        int x = power(a, d, n);

      

        if (x == 1 || x == n - 1)

            return true;

      

        // Продолжаем возводить в квадрат х, пока один из

        // следования не происходит

        // (i) d не достигает n-1

        // (ii) (x ^ 2)% n не равно 1

        // (iii) (x ^ 2)% n не является n-1

        while (d != n - 1) {

            x = (x * x) % n;

            d *= 2;

          

            if (x == 1)

                return false;

            if (x == n - 1)

                return true;

        }

      

        // Возвращаем композит

        return false;

    }

      

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

    // и возвращает true, если n вероятно

    // премьер. k является входным параметром, который

    // определяет уровень точности. выше

    // значение k указывает на большую точность.

    static boolean isPrime(int n, int k) {

          

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

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

            return false;

        if (n <= 3)

            return true;

      

        // Находим r таким, что n = 2 ^ d * r + 1

        // для некоторого r> = 1

        int d = n - 1;

          

        while (d % 2 == 0)

            d /= 2;

      

        // Итерация по заданному числу 'k' раз

        for (int i = 0; i < k; i++)

            if (!miillerTest(d, n))

                return false;

      

        return true;

    }

      

    // Драйвер программы

    public static void main(String args[]) {

          

        int k = 4; // Количество итераций

      

        System.out.println("All primes smaller "

                                + "than 100: ");

                                  

        for (int n = 1; n < 100; n++)

            if (isPrime(n, k))

                System.out.print(n + " ");

    }

}

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

python3

# Python3 программа теста Миллера-Рабина

import random 

  
# Сервисная функция, чтобы сделать
# модульное возведение в степень.
# Возвращает (x ^ y)% p

def power(x, y, p):

      

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

    res = 1

      

    # Обновите x, если оно больше или

    # равно p

    x = x % p; 

    while (y > 0):

          

        # Если у нечетно, умножить

        # х с результатом

        if (y & 1):

            res = (res * x) % p;

  

        # у должно быть даже сейчас

        y = y>>1; # y = y / 2

        x = (x * x) % p;

      

    return res;

  
# Эта функция называется
# для всех k испытаний. Возвращается
# false, если n составное и
# возвращает false, если n
# вероятно, простое. д странный
# число такое, что d * 2 <sup> r </ sup> = n-1
# для некоторого r> = 1

def miillerTest(d, n):

      

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

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

    a = 2 + random.randint(1, n - 4);

  

    # Вычислить ^ D% N

    x = power(a, d, n);

  

    if (x == 1 or x == n - 1):

        return True;

  

    # Продолжайте возводить в квадрат х, пока один

    # из следующего не

    # случиться

    # (i) d не достигает n-1

    # (ii) (x ^ 2)% n не равно 1

    # (iii) (x ^ 2)% n не является n-1

    while (d != n - 1):

        x = (x * x) % n;

        d *= 2;

  

        if (x == 1):

            return False;

        if (x == n - 1):

            return True;

  

    # Возврат композит

    return False;

  
# Возвращает false, если n
# Composite и возвращает true, если n
#, вероятно, простое число. к является
# входной параметр, который определяет
# уровень точности. Более высокое значение
# k указывает на большую точность.

def isPrime( n, k):

      

    # Угловые чехлы

    if (n <= 1 or n == 4):

        return False;

    if (n <= 3):

        return True;

  

    # Найти r такое, что n =

    # 2 ^ d * r + 1 для некоторого r> = 1

    d = n - 1;

    while (d % 2 == 0):

        d //= 2;

  

    # Итерировать заданное число раз 'k'

    for i in range(k):

        if (miillerTest(d, n) == False):

            return False;

  

    return True;

  
Код водителя
Количество итераций

k = 4

  

print("All primes smaller than 100: ");

for n in range(1,100):

    if (isPrime(n, k)):

        print(n , end=" ");

  
# Этот код предоставлен mits

C #

// C # программа теста Миллера-Рабина

using System;

  

class GFG

{

  

    // Сервисная функция для модульной работы

    // возведение в степень. Возвращает (x ^ y)% p

    static int power(int x, int y, int p) 

    {

          

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

          

        // Обновление x, если оно больше

        // или равно p

        x = x % p; 

  

        while (y > 0)

        {

              

            // Если y нечетно, умножаем x на результат

            if ((y & 1) == 1)

                res = (res * x) % p;

          

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

            y = y >> 1; // y = y / 2

            x = (x * x) % p;

        }

          

        return res;

    }

      

    // Эта функция вызывается для всех k испытаний.

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

    // возвращает false, если n, вероятно, простое число.

    // d нечетное число такое, что d * 2 <sup> r </ sup>

    // = n-1 для некоторого r> = 1

    static bool miillerTest(int d, int n) 

    {

          

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

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

        Random r = new Random();

        int a = 2 + (int)(r.Next() % (n - 4));

      

        // Вычисляем ^ d% n

        int x = power(a, d, n);

      

        if (x == 1 || x == n - 1)

            return true;

      

        // Продолжаем возводить в квадрат х, пока один из

        // следования не происходит

        // (i) d не достигает n-1

        // (ii) (x ^ 2)% n не равно 1

        // (iii) (x ^ 2)% n не является n-1

        while (d != n - 1) 

        {

            x = (x * x) % n;

            d *= 2;

          

            if (x == 1)

                return false;

            if (x == n - 1)

                return true;

        }

      

        // Возвращаем композит

        return false;

    }

      

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

    // и возвращает true, если n вероятно

    // премьер. k является входным параметром, который

    // определяет уровень точности. выше

    // значение k указывает на большую точность.

    static bool isPrime(int n, int k) 

    {

          

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

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

            return false;

        if (n <= 3)

            return true;

      

        // Находим r таким, что n = 2 ^ d * r + 1

        // для некоторого r> = 1

        int d = n - 1;

          

        while (d % 2 == 0)

            d /= 2;

      

        // Итерация по заданному числу 'k' раз

        for (int i = 0; i < k; i++)

            if (miillerTest(d, n) == false)

                return false;

      

        return true;

    }

      

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

    static void Main() 

    {

        int k = 4; // Количество итераций

      

        Console.WriteLine("All primes smaller " +

                                   "than 100: ");

                                  

        for (int n = 1; n < 100; n++)

            if (isPrime(n, k))

                Console.Write(n + " ");

    }

}

  
// Этот код предоставлен mits

PHP

<?php
// PHP программа теста Миллера-Рабина

  
// Полезная функция для выполнения
// модульное возведение в степень.
// Возвращает (x ^ y)% p

function power($x, $y, $p)

{

      

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

    $res = 1; 

      

    // Обновление x, если оно больше или

    // равно p

    $x = $x % $p

    while ($y > 0)

    {

          

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

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

        if ($y & 1)

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

  

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

        $y = $y>>1; // $ y = $ y / 2

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

    }

    return $res;

}

  
// Эта функция называется
// для всех k испытаний. Возвращается
// false если n составное и
// возвращает false, если n
// возможно простое число д странный
// число такое, что d * 2 <sup> r </ sup> = n-1
// для некоторого r> = 1

function miillerTest($d, $n)

{

      

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

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

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

  

    // Вычисляем ^ d% n

    $x = power($a, $d, $n);

  

    if ($x == 1 || $x == $n-1)

    return true;

  

    // Продолжаем возводить в квадрат х, пока один

    // из следующего не

    // случилось

    // (i) d не достигает n-1

    // (ii) (x ^ 2)% n не равно 1

    // (iii) (x ^ 2)% n не является n-1

    while ($d != $n-1)

    {

        $x = ($x * $x) % $n;

        $d *= 2;

  

        if ($x == 1)     return false;

        if ($x == $n-1) return true;

    }

  

    // Возвращаем композит

    return false;

}

  
// Возвращает false, если n
// составной и возвращает true, если n
// вероятно прост. к является
// входной параметр, который определяет
// уровень точности. Более высокое значение
// k указывает на большую точность.

function isPrime( $n, $k)

{

      

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

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

    if ($n <= 3) return true;

  

    // Находим r таким, что n =

    // 2 ^ d * r + 1 для некоторого r> = 1

    $d = $n - 1;

    while ($d % 2 == 0)

        $d /= 2;

  

    // Итерация по заданному числу 'k' раз

    for ($i = 0; $i < $k; $i++)

        if (!miillerTest($d, $n))

            return false;

  

    return true;

}

  

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

    // Количество итераций

    $k = 4; 

  

    echo "All primes smaller than 100: \n";

    for ($n = 1; $n < 100; $n++)

    if (isPrime($n, $k))

        echo $n , " ";

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


Выход:

All primes smaller than 100: 
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 
61 67 71 73 79 83 89 97 

Как это работает?
Ниже приведены некоторые важные факты, лежащие в основе алгоритма:

  1. Теорема Ферма утверждает, что, если n — простое число, то для каждого a, 1 <= a <n, a n-1 % n = 1
  2. В базовых случаях убедитесь, что n должно быть нечетным. Поскольку n нечетно, n-1 должно быть четным. И четное число может быть записано как d * 2 s, где d нечетное число и s> 0.
  3. Из вышеупомянутых двух точек для каждого случайно выбранного числа в диапазоне [2, n-2] значение a d * 2 r % n должно быть 1.
  4. Согласно лемме Евклида , если x 2 % n = 1 или (x 2 — 1)% n = 0 или (x-1) (x + 1)% n = 0. Тогда для простого числа n либо n делит (x-1) или n делит (x + 1). Что означает либо x% n = 1, либо x% n = -1.
  5. Из пунктов 2 и 3 можно сделать вывод
        For n to be prime, either
        ad % n = 1 
             OR 
        ad*2i % n = -1 
        for some i, where 0 <= i <= r-1.

Следующая статья:
Тест на первичность | Комплект 4 (Соловай-Штрассен)

Ссылки:
https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test

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

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

Тест на первичность | Набор 3 (Миллер-Рабин)

0.00 (0%) 0 votes