Рубрики

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

Мы уже знакомились с тестированием на примитивность в предыдущих статьях этой серии.

Тест примитивности Соловея – Штрассена является вероятностным тестом для определения того, является ли число составным или, возможно, простым.
Прежде чем углубляться в код, нам нужно понять некоторые ключевые термины и концепции, чтобы иметь возможность кодировать этот алгоритм.

Фон:

Символ Лежандра : Этот символ определен для пары целых чисел a и p, таких что p простое. Обозначается (a / p) и рассчитывается как:

      = 0    if a%p = 0
(a/p) = 1    if there exists an integer k such that 
      = -1   otherwise.

Эйлер доказал, что:

%p   Condition (i)

Символ Якобиана : этот символ является обобщением символа Лежандра, где p заменяется на n, где n

n = p1k1 * .. * pnkn

тогда якобианский символ определяется как:

 () * () * ..... * ()

Если n взять за простое число, то якобиан будет равен символу Лежандра. Эти символы имеют определенные свойства
1) (a / n) = 0, если gcd (a, n)! = 1, следовательно (0 / n) = 0. Это потому, что если gcd (a, n)! = 1, то должно быть некоторое простое число pi такой, что пи делит и а и п. В этом случае (a / pi) = 0 [по определению символа Лежандра].
2) (ab / n) = (a / n) * (b / n). Это может быть легко получено из факта (ab / p) = (a / p) (b / p) (здесь (a / p) — Легендарный Символ).
3) Если a чётно, то (a / n) = (2 / n) * ((a / 2) / n). Можно показать, что:

      = 1 if n = 1 ( mod 8 ) or n = 7 ( mod 8 )
(2/n) = -1 if n = 3 ( mod 8 ) or n = 5 ( mod 8 )
      = 0 otherwise

4)

 if a and n are both odd.

Алгоритм:

Мы выбираем число n для проверки его простоты и случайное число a, которое лежит в диапазоне [2, n-1], и вычисляем его якобиан (a / n), если n — простое число, то якобиан будет равен к Лежандру, и он будет удовлетворять условию (i), заданному Эйлером. Если он не удовлетворяет данному условию, то n является составным, и программа остановится. Как и любой другой вероятностный тест на простоту, его точность также прямо пропорциональна количеству итераций. Поэтому мы запускаем тест в течение нескольких итераций, чтобы получить более точные результаты.

Примечание: нас не интересует вычисление якобиана четных чисел, поскольку мы уже знаем, что они не простые, кроме 2.

псевдокод:

Algorithm for Jacobi:
Step 1    //base cases omitted
Step 2     if a>n then
Step 3         return ()
Step 4     else
Step 5         return ()
Step 6     endif
Algorithm for Solovay-Strassen:
Step 1    Pick a random element a < n
Step 2    if gcd(a, n) > 1 then
Step 3        return COMPOSITE
Step 4    end if
Step 5    Compute  using repeated squaring
           and  using Jacobian algorithm.
Step 6    if  not equal to  then
Step 7        return composite
Step 8    else
Step 9        return prime
Step 10   endif

Реализация:

C ++

// C ++ программа для реализации Solovay-Strassen
// Тест на простоту
#include <bits/stdc++.h>

using namespace std;

  
// по модулю для выполнения двоичного возведения в степень

long long modulo(long long base, long long exponent,

                                      long long mod)

{

    long long x = 1;

    long long y = base;

    while (exponent > 0)

    {

        if (exponent % 2 == 1)

            x = (x * y) % mod;

  

        y = (y * y) % mod;

        exponent = exponent / 2;

    }

  

    return x % mod;

}

  
// Для вычисления символа якобиана заданного числа

int calculateJacobian(long long a, long long n)

{

    if (!a)

        return 0;// (0 / n) = 0

  

    int ans = 1;

    if (a < 0)

    {

        a = -a; // (a / n) = (-a / n) * (- 1 / n)

        if (n % 4 == 3)

            ans = -ans; // (-1 / n) = -1, если n = 3 (мод 4)

    }

  

    if (a == 1)

        return ans;// (1 / n) = 1

  

    while (a)

    {

        if (a < 0)

        {

            a = -a;// (a / n) = (-a / n) * (- 1 / n)

            if (n % 4 == 3)

                ans = -ans;// (-1 / n) = -1, если n = 3 (мод 4)

        }

  

        while (a % 2 == 0)

        {

            a = a / 2;

            if (n % 8 == 3 || n % 8 == 5)

                ans = -ans;

  

        }

  

        swap(a, n);

  

        if (a % 4 == 3 && n % 4 == 3)

            ans = -ans;

        a = a % n;

  

        if (a > n / 2)

            a = a - n;

  

    }

  

    if (n == 1)

        return ans;

  

    return 0;

}

  
// Выполнить тест примитивности Соловая-Штрассена

bool solovoyStrassen(long long p, int iterations)

{

    if (p < 2)

        return false;

    if (p != 2 && p % 2 == 0)

        return false;

  

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

    {

        // Генерируем случайное число а

        long long a = rand() % (p - 1) + 1;

        long long jacobian = (p + calculateJacobian(a, p)) % p;

        long long mod = modulo(a, (p - 1) / 2, p);

  

        if (!jacobian || mod != jacobian)

            return false;

    }

    return true;

}

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

int main()

{

    int iterations = 50;

    long long num1 = 15;

    long long num2 = 13;

  

    if (solovoyStrassen(num1, iterations))

        printf("%d is prime\n",num1);

    else

        printf("%d is composite\n",num1);

  

    if (solovoyStrassen(num2, iterations))

        printf("%d is prime\n",num2);

    else

        printf("%d is composite\n",num2);

  

    return 0;

}

python3

# Python3 программа для реализации Solovay-Strassen
# Тест на первичность

import random

  
# функция по модулю для выполнения двоичного
# возведение в степень

def modulo(base, exponent, mod): 

    x = 1

    y = base; 

    while (exponent > 0): 

        if (exponent % 2 == 1): 

            x = (x * y) % mod; 

  

        y = (y * y) % mod; 

        exponent = exponent // 2

  

    return x % mod; 

  
# Для вычисления якобианского символа
# номер

def calculateJacobian(a, n): 

  

    if (a == 0): 

        return 0;# (0 / n) = 0

  

    ans = 1

    if (a < 0): 

          

        # (a / n) = (-a / n) * (- 1 / n)

        a = -a; 

        if (n % 4 == 3): 

          

            # (-1 / n) = -1, если n = 3 (мод 4)

            ans = -ans; 

  

    if (a == 1): 

        return ans; # (1 / n) = 1

  

    while (a): 

        if (a < 0):

              

            # (a / n) = (-a / n) * (- 1 / n)

            a = -a; 

            if (n % 4 == 3):

                  

                # (-1 / n) = -1, если n = 3 (мод 4)

                ans = -ans; 

  

        while (a % 2 == 0): 

            a = a // 2

            if (n % 8 == 3 or n % 8 == 5): 

                ans = -ans; 

  

        # обмен

        a, n = n, a; 

  

        if (a % 4 == 3 and n % 4 == 3): 

            ans = -ans; 

        a = a % n; 

  

        if (a > n // 2): 

            a = a - n; 

  

    if (n == 1): 

        return ans; 

  

    return 0

  
# Выполнить Соловай-Штрассен
# Тест на первичность

def solovoyStrassen(p, iterations): 

  

    if (p < 2): 

        return False

    if (p != 2 and p % 2 == 0): 

        return False

  

    for i in range(iterations):

          

        # Генерация случайного числа

        a = random.randrange(p - 1) + 1

        jacobian = (p + calculateJacobian(a, p)) % p; 

        mod = modulo(a, (p - 1) / 2, p); 

  

        if (jacobian == 0 or mod != jacobian): 

            return False

  

    return True

  
Код водителя

iterations = 50

num1 = 15

num2 = 13

  

if (solovoyStrassen(num1, iterations)): 

    print(num1, "is prime "); 

else:

    print(num1, "is composite"); 

  

if (solovoyStrassen(num2, iterations)): 

    print(num2, "is prime"); 

else:

    print(num2, "is composite"); 

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

PHP

<?php
// PHP-программа для реализации
// Соловай-Штрассен тест на первичность

  
// по модулю
// двоичное возведение в степень

function modulo($base, $exponent, $mod)

{

    $x = 1;

    $y = $base;

    while ($exponent > 0)

    {

        if ($exponent % 2 == 1)

            $x = ($x * $y) % $mod;

  

        $y = ($y * $y) % $mod;

        $exponent = $exponent / 2;

    }

  

    return $x % $mod;

}

  
// Для вычисления якобиана
// символ данного числа

function calculateJacobian($a, $n)

{

    if (!$a)

        return 0;// (0 / n) = 0

  

    $ans = 1;

    if ($a < 0)

    {

        // (a / n) = (-a / n) * (- 1 / n)

        $a = -$a

        if ($n % 4 == 3)

          

            // (-1 / n) = -1, если n = 3 (мод 4)

            $ans = -$ans

    }

  

    if ($a == 1)

        return $ans;// (1 / n) = 1

  

    while ($a)

    {

        if ($a < 0)

        {

            // (a / n) = (-a / n) * (- 1 / n)

            $a = -$a;

            if ($n % 4 == 3)

                  

                // (-1 / n) = -1, если n = 3 (мод 4)

                $ans = -$ans;

        }

  

        while ($a % 2 == 0)

        {

            $a = $a / 2;

            if ($n % 8 == 3 || $n % 8 == 5)

                $ans = -$ans;

  

        }

        //обмен

        list($a, $n) = array($n, $a);

  

        if ($a % 4 == 3 && $n % 4 == 3)

            $ans = -$ans;

        $a = $a % $n;

  

        if ($a > $n / 2)

            $a = $a - $n;

  

    }

  

    if ($n == 1)

        return $ans;

  

    return 0;

}

  
// Выполнить Соловай-
// Strassen Primality Test

function solovoyStrassen($p, $iterations)

{

    if ($p < 2)

        return false;

    if ($p != 2 && $p % 2 == 0)

        return false;

  

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

    {

        // Генерируем случайное число а

        $a = rand() % ($p - 1) + 1;

        $jacobian = ($p

                     calculateJacobian($a

                                       $p)) % $p;

        $mod = modulo($a, ($p - 1) / 2, $p);

  

        if (!$jacobian || $mod != $jacobian)

            return false;

    }

    return true;

}

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

$iterations = 50;

$num1 = 15;

$num2 = 13;

  

if (solovoyStrassen($num1, $iterations))

    echo $num1," is prime ","\n";

else

    echo $num1," is composite\n";

  

if (solovoyStrassen($num2, $iterations))

    echo $num2," is prime\n";

else

    echo $num2," is composite\n";

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


Выход :

15 is composite
13 is prime

Время работы: Используя быстрые алгоритмы для модульного возведения в степень, время работы этого алгоритма составляет O (k · n), где k — количество различных значений тестируемого нами.

Точность: алгоритм может вернуть неправильный ответ. Если вход n действительно прост, то выход всегда будет корректным. Однако, если вход n является составным, то возможно, что выход будет неправильно, вероятно, простым. Тогда число n называется псевдопримарой Эйлера-Якоби.

Ссылки:

Эта статья предоставлена Palash Nigam . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

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

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

0.00 (0%) 0 votes