Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 2 3 4 5 6 [7] 8 9 10   вперед  Ctrl      все
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Barlone
Member

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

Откуда:
Сообщений: 9486
Gennadiy Usov
Я говорю об одинаковых условиях для двух программ: старенький ПК, Питон.
И что?
Вот я в детстве иногда лепил из пластилина. Кое-что из моих "творений" даже стояло дома на видном месте.
И что? Кому и зачем всё это может быть интересно?

P.S.
"Всё" - не столько мои излияния, сколько ваши "труды". Уж не обижайтесь.
3 окт 19, 13:10    [21985806]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1840
Basil A. Sidorov
Gennadiy Usov
Программа оценила число:
2019-10-03-13.00.20
-число- 3825123056546413053
-Нет простых чисел- 0
2019-10-03-13.00.20
Этот загадочный ответ сообщает, что число простое или как?
Программа "приняла" число и "сказала",

что среди представленных чисел (одно число в перечне) 0 простых чисел. (слово "нет" - лишнее, убираю)

2019-10-03-13.09.54
-число- 3825123056546413053
-простых чисел- 0
2019-10-03-13.09.54
3 окт 19, 13:11    [21985809]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1348
Gennadiy Usov
Barlone
пропущено...
На питоне? Да, хороший вариант для измерения скорости :)
Но сравнивались две прогроммы на Питоне.

Я же не говорю о времени работы программ.
Я говорю об одинаковых условиях для двух программ: старенький ПК, Питон.
Не, просто питон известен своей тормознутостью...
Хотя, вы в степень то наверное встроенной функцией возводили?
3 окт 19, 13:11    [21985810]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1348
Gennadiy Usov
Basil A. Sidorov
пропущено...
Этот загадочный ответ сообщает, что число простое или как?
Программа "приняла" число и "сказала",

что среди представленных чисел (одно число в перечне) 0 простых чисел. (слово "нет" - лишнее, убираю)

2019-10-03-13.09.54
-число- 3825123056546413053
-простых чисел- 0
2019-10-03-13.09.54
Эй, у меня последняя цифра была 1
3 окт 19, 13:15    [21985812]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Basil A. Sidorov
Member

Откуда:
Сообщений: 9486
Gennadiy Usov
Программа "приняла" число и "сказала", что среди представленных чисел (одно число в перечне) 0 простых чисел. (слово "нет" - лишнее, убираю)
"Ясвасхудею".
А выдать что-то вроде:
  Всего чисел - xxx
Проверено чисел - yyy
Простых чисел - zzz
?

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

Откуда:
Сообщений: 1348
Gennadiy Usov
Barlone
Вот еще хорошее число: 3825123056546413051
Программа оценила число:

2019-10-03-13.00.20
-число- 3825123056546413053
-Нет простых чисел- 0
2019-10-03-13.00.20
не то число
3 окт 19, 13:16    [21985815]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1840
Barlone
Gennadiy Usov
пропущено...
Программа оценила число:

2019-10-03-13.00.20
-число- 3825123056546413053
-Нет простых чисел- 0
2019-10-03-13.00.20
не то число
Разобрался.

У меня цикл по нечётным числам с шагом 2 на диапазоне, я назначил число и ограничил на +1,
а цикл (на то он и цикл) прибавляет и сравнивает с ограничителем.

А печать идёт после выхода из цикла.
Внутри цикла составные числа программе не нужны, поэтому эти числа там не печатаются.

Исправил (отнял 2):

2019-10-03-13.19.53
-число- 3825123056546413051
-простых чисел- 0
2019-10-03-13.19.53
3 окт 19, 13:26    [21985834]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1840
Barlone
А насчет практики - есть такое число Скьюза. Это про гипотезу, что количество простых чисел, не превосходящих n, меньше чем интегральный логарифм li(n). Она выполняется до 10316, а потом перестает выполняться... Вы свой алгоритм хотя бы до 10316 проверяли?
На топике считал для некоторой таблички числа порядка 2^2048.

На диапазоне 2^1024 количество простых чисел на диапазоне совпало с расчётом mayton.

А вопрос один - с чем сравнивать, как проверять.
Делители "будут очень долго считать"...
3 окт 19, 13:34    [21985843]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1348
Gennadiy Usov
Barlone
пропущено...
не то число
Разобрался.

У меня цикл по нечётным числам с шагом 2 на диапазоне, я назначил число и ограничил на +1,
а цикл (на то он и цикл) прибавляет и сравнивает с ограничителем.

А печать идёт после выхода из цикла.
Внутри цикла составные числа программе не нужны, поэтому эти числа там не печатаются.

Исправил (отнял 2):

2019-10-03-13.19.53
-число- 3825123056546413051
-простых чисел- 0
2019-10-03-13.19.53
Не сходится с тем, что вы про свой алгоритм рассказываете...
3 окт 19, 13:42    [21985851]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1840
Basil A. Sidorov
Gennadiy Usov
Программа "приняла" число и "сказала", что среди представленных чисел (одно число в перечне) 0 простых чисел. (слово "нет" - лишнее, убираю)
"Ясвасхудею".
А выдать что-то вроде:
  Всего чисел - xxx
Проверено чисел - yyy
Простых чисел - zzz
?
Ну или учитывая, что простые числа, типа, "редкие", по мере проверки просто печать список "эвристически простых", а по итогу выдать общую статистику?
Согласен.

Поскольку задают вопросы, нужно привести программу в порядок:
красиво оформить выходные данные.

Хотя программы должно быть две (дубляж):
для диапазона и для отдельного числа.
3 окт 19, 13:45    [21985856]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1840
Barlone
Gennadiy Usov
Разобрался.
У меня цикл по нечётным числам с шагом 2 на диапазоне, я назначил число и ограничил на +1,
а цикл (на то он и цикл) прибавляет и сравнивает с ограничителем.
А печать идёт после выхода из цикла.
Внутри цикла составные числа программе не нужны, поэтому эти числа там не печатаются.
Исправил (отнял 2):

2019-10-03-13.19.53
-число- 3825123056546413051
-простых чисел- 0
2019-10-03-13.19.53
Не сходится с тем, что вы про свой алгоритм рассказываете...
И где расхождение?
3 окт 19, 13:47    [21985859]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1348
n = 3825123056546413051
n-1 = 21*1912561528273206525

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

Откуда:
Сообщений: 1840
Barlone
n = 3825123056546413051
n-1 = 21*1912561528273206525
a(n-1)/2 mod n равно 1 или n-1 для всех a от 2 до 36...
Хороший пример!

У меня записано:
"Число А выбирается равное 10, с запасом – пока подтверждено только одно число 25326001 при а = 7.
Можно увеличить число 10.
Но для этого нужны проверки для чисел, больших 250 000 000."

Просто увеличиваем А до 15 простых чисел!
То есть до 47.
И смотрим дальше.

Ещё есть примеры?
3 окт 19, 14:58    [21985926]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Aleksandr Sharahov
Member

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

Откуда:
Сообщений: 1840
Насчет простых чисел поторопился...

У числа 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

Откуда:
Сообщений: 1348
Gennadiy Usov
Насчет простых чисел поторопился...

У числа 3825123056546413051 log (n) = 42...

Поэтому ставим А = 42 и рассматриваем все числа от 2 до 42.

Число 36 - попадает.

Ещё раз уточнил старые расчёты.

Для тестовых расчётов log (1 000 000 001) = 20.

Мне встречались числа 11, 13, 15.

Поэтому, A = log (n).

И в тесте Миллера-Рабина log (n).
Однако ушли от вероятности.

Эх, опять промахнулись... 3317044064679887385961981 - вот тут уже 43 надо.
3 окт 19, 15:41    [21985973]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Barlone
Member

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

Откуда:
Сообщений: 1348
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
Вот вам тест простоты на питоне, вызывать isprime(n) - проверяйте, ищите контрпримеры. Это как раз Люка.
3 окт 19, 15:46    [21985985]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Barlone
Member

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

Откуда:
Сообщений: 1348
Поторопился, если подсунуть квадрат очень большого числа, math.sqrt вычисляется с ошибкой, и в цикле поиска квадратичного невычета зависает... Поправил.
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))
3 окт 19, 16:10    [21986008]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Barlone
Member

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

Откуда:
Сообщений: 1840
Barlone
Эх, опять промахнулись... 3317044064679887385961981 - вот тут уже 43 надо.
А вот и нет!

Здесь s = 2.
При s = 1 одни 1 и (n - 1) до 42.
А при s = 0 при 2 сразу составное!
3 окт 19, 16:23    [21986019]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1840
Barlone
Поторопился, если подсунуть квадрат очень большого числа, math.sqrt вычисляется с ошибкой, и в цикле поиска квадратичного невычета зависает...
Поправил.
Спасибо!

А если пройтись по всем нечётным, где s = 1, и считать 1 и (n - 1) до "выбывания"?
3 окт 19, 16:32    [21986033]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 42917
Barlone
Gennadiy Usov
Взял из вики описание теста Люка-Лемера и написал программу на Питоне.
На питоне? Да, хороший вариант для измерения скорости :)

В нашем случае это норм вариант. Тут-же принципиальная возможность изучается.
Перформанс - второе дело. Тем более что для Питона есть библиотеки поддержки длинных.
3 окт 19, 16:45    [21986047]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 2 3 4 5 6 [7] 8 9 10   вперед  Ctrl      все
Все форумы / Программирование Ответить