Эвристический алгоритм (формула, тест простоты) для определения простых чисел / Страница 7 / Программирование / Sql.ru

2019-10-03-13.00.20
 -число-  3825123056546413053
-Нет простых чисел- 0
2019-10-03-13.00.20
  Всего чисел - xxx
  Проверено чисел - yyy
  Простых чисел - zzz
  Всего чисел - xxx
  Проверено чисел - yyy
  Простых чисел - zzz
import math

def jacobi(a, n):
    assert(a > 0 and n % 2 == 1)
    a %= n
    t = 1
    while a != 0:
        while a % 2 == 0:
            a = a // 2
            r = n % 8
            if r == 3 or r == 5:
                t = -t
        a, n = n, a
        if a % 4 == 3 and n % 4 == 3:
            t = -t
        a %= n
    if n == 1:
        return t
    else:
        return 0

def pair2(a, d, n):
    return ((a[0] * a[0] + n - 2) % n, (a[0] * a[1]) % n)
        
def pairmul(a, b, d, n):
    x = (a[0] * b[0] + d * a[1] * b[1]) % n
    if x % 2 == 0:
        x = x // 2
    else:
        x = (n + x) // 2
    y = (a[0] * b[1] + b[0] * a[1]) % n
    if y % 2 == 0:
        y = y // 2
    else:
        y = (n + y) // 2
    return (x, y)

def pairpow(a, m, d, n):
    r = (1, 0)
    while m != 0:
        if m % 2 == 1:
            r = pairmul(r, a, d, n)
        a = pair2(a, d, n)
        m = m // 2
    return r

def isprime(n):
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    if n == 3:
        return True
    if n % 3 == 0:
        return False
    if n == 5:
        return True
    if n % 5 == 0:
        return False

    m = int(math.sqrt(n))
    if m * m == n:
        return False

    p = 3
    d = p * p - 4
    j = jacobi(d, n)
    while j == 1:
        p = p + 1
        d = p * p - 4
        j = jacobi(d, n)

    if j == 0:
        return False

    if pow(d, n // 2, n) != n - 1:
        return False

    a = pairpow((p, 1), (n + 1) // 2, d, n)
    if a[1] != 0:
        return False
    if a[0] != 1 and a[0] != n - 1:
        return False
    return True

import math

def jacobi(a, n):
    assert(a > 0 and n % 2 == 1)
    a %= n
    t = 1
    while a != 0:
        while a % 2 == 0:
            a = a // 2
            r = n % 8
            if r == 3 or r == 5:
                t = -t
        a, n = n, a
        if a % 4 == 3 and n % 4 == 3:
            t = -t
        a %= n
    if n == 1:
        return t
    else:
        return 0

def pair2(a, d, n):
    return ((a[0] * a[0] + n - 2) % n, (a[0] * a[1]) % n)
        
def pairmul(a, b, d, n):
    x = (a[0] * b[0] + d * a[1] * b[1]) % n
    if x % 2 == 0:
        x = x // 2
    else:
        x = (n + x) // 2
    y = (a[0] * b[1] + b[0] * a[1]) % n
    if y % 2 == 0:
        y = y // 2
    else:
        y = (n + y) // 2
    return (x, y)

def pairpow(a, m, d, n):
    r = (1, 0)
    while m != 0:
        if m % 2 == 1:
            r = pairmul(r, a, d, n)
        a = pair2(a, d, n)
        m = m // 2
    return r

def isprime(n):
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    if n == 3:
        return True
    if n % 3 == 0:
        return False
    if n == 5:
        return True
    if n % 5 == 0:
        return False

    m = int(math.sqrt(n))
    if m * m == n:
        return False
    k = (m + n // m) // 2
    while k != m:
        m, k = k, (m + n // m) // 2
    if m * m == n:
        return False
    
    p = 3
    d = p * p - 4
    j = jacobi(d, n)
    while j == 1:
        p = p + 1
        d = p * p - 4
        j = jacobi(d, n)

    if j == 0:
        return False

    if pow(d, n // 2, n) != n - 1:
        return False

    a = pairpow((p, 1), (n + 1) // 2, d, n)
    if a[1] != 0:
        return False
    if a[0] != 1 and a[0] != n - 1:
        return False
    return True
    

n = 3317044064679887385961981
m = n // 2
print(isprime(3317044064679887385961981*3317044064679887385961981))

#for i in range (2, 44):
#    print (i, pow(i,m,n), jacobi(i,n))

Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел [new]
Barlone Member Откуда: Сообщений: 1451	А насчет практики - есть такое число Скьюза. Это про гипотезу, что количество простых чисел, не превосходящих n, меньше чем интегральный логарифм li(n). Она выполняется до 10³¹⁶, а потом перестает выполняться... Вы свой алгоритм хотя бы до 10³¹⁶ проверяли?
3 окт 19, 13:08 [21985803] Ответить \| Цитировать Сообщить модератору

Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел [new]
Barlone Member Откуда: Сообщений: 1451	n = 3825123056546413051 n-1 = 2¹*1912561528273206525 a^(n-1)/2 mod n равно 1 или n-1 для всех a от 2 до 36...
3 окт 19, 13:51 [21985863] Ответить \| Цитировать Сообщить модератору

Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел [new]
Gennadiy Usov Member Откуда: Сообщений: 2357	Насчет простых чисел поторопился... У числа 3825123056546413051 log (n) = 42... Поэтому ставим А = 42 и рассматриваем все числа от 2 до 42. Число 36 - попадает. Ещё раз уточнил старые расчёты. Для тестовых расчётов log (1 000 000 001) = 20. Мне встречались числа 11, 13, 15. Поэтому, A = log (n). И в тесте Миллера-Рабина log (n). Однако ушли от вероятности.
3 окт 19, 15:36 [21985967] Ответить \| Цитировать Сообщить модератору

Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел [new]
Barlone Member Откуда: Сообщений: 1451	А насчет простых то как раз всё правильно: понятно, что если a^m mod n = 1 и b^m mod n = 1 то и (ab)^m mod n = 1
3 окт 19, 15:44 [21985979] Ответить \| Цитировать Сообщить модератору

Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел [new]
Barlone Member Откуда: Сообщений: 1451	Точнее, один раунд ~~Ферма~~ Соловея-Штрассена плюс Люка
3 окт 19, 15:53 [21985994] Ответить \| Цитировать Сообщить модератору

Добро пожаловать в форум, Guest >> Войти \| Регистрация \| Поиск \| Правила \|			В избранное \| Подписаться
Все форумы / Программирование

Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел [new]
Aleksandr Sharahov Member Откуда: Москва Сообщений: 2060
3 окт 19, 15:33 [21985965] Ответить \| Цитировать Сообщить модератору

Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел [new]
Barlone Member Откуда: Сообщений: 1451	С куском отладочного кода в конце :)
3 окт 19, 16:13 [21986011] Ответить \| Цитировать Сообщить модератору