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

Откуда:
Сообщений: 1348
Gennadiy Usov
А вот интересная задача (по поводу определения раундов)

import math
a1= math.sqrt(1000000000000000000000001)//1
a2 = math.sqrt(1000000000000000000000000000000000000000000001)//1
print (a1, a2)

И печать результатов:

(1000000000000.0, 3.1622776601683792e+22)

Вот почему одно число целое, а другое число вещественное?
А черт его знает, надо в исходники питона смотреть.
Вот вам целочисленный корень:
def intsqrt(n):
    q = n.bit_length()
    if q <= 129:
        m = int(math.sqrt(n))
    else:
        k = (q - 128) >> 1
        m = int(math.sqrt(n >> (2*k))) << k
    k = (m + n // m) >> 1
    while k != m:
        m, k = k, (m + n // m) >> 1
    return k    
4 окт 19, 16:12    [21986893]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1840
Спасибо!

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

Откуда:
Сообщений: 1348
Gennadiy Usov
А вот интересная задача (по поводу определения раундов)

import math
a1= math.sqrt(1000000000000000000000001)//1
a2 = math.sqrt(1000000000000000000000000000000000000000000001)//1
print (a1, a2)

И печать результатов:

(1000000000000.0, 3.1622776601683792e+22)

Вот почему одно число целое, а другое число вещественное?
А вообще-то первое тоже вещественное - там же в конце ".0".
Просто во втором нечетное количество ноликов, и в 52 бита (точность мантиссы в double) оно не лезет, поэтому в экспоненциальной форме
4 окт 19, 16:25    [21986907]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1348
Barlone
Что-то у меня на диапазоне 200000 с 22048 нашлось 151 число. Черт возьми, надо было их вывести, а не просто посчитать.
Перепроверил, на 60 раундов Соловея-Штрассена, все простые:
+
22048+...
(981,1617,3063,3211,4143,7405,9843,10665,10725,11097,11467,13137,13333,15703,17001,
17787,18523,21397,24963,25405,26697,26935,30475,31627,34005,34431,35281,35763,36535,
37653,38841,39825,42637,43965,44281,45303,46303,46995,49957,54613,54873,57325,62847,
65377,65545,67701,67953,68415,68535,68941,69493,69543,72207,75775,76413,76647,77797,
78003,81081,81093,81795,83335,83593,84397,84463,89023,89835,89965,90127,90147,90993,
93795,94593,97455,97707,98077,99867,99945,100431,105435,107025,107385,107851,109197,
111343,115911,115941,116667,117601,123327,124381,125523,129051,130453,130551,130773,
131203,131301,131877,132915,133221,133651,134085,135751,135771,136383,136711,137443,
141901,147783,148455,150997,152751,153097,153817,155013,155191,156027,156057,157543,
160747,162385,162747,162891,164191,166843,167001,172603,173373,174157,175503,176563,
180081,182811,183397,184021,184167,186235,187017,187803,192091,192883,193107,193635,
193831,194205,195321,196261,197587,198213,199425)
4 окт 19, 18:11    [21987027]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 42918
Надо базу вести. Типа "Простые числа по версии Соловея-Штрассена". Потом еще базу. Простые по версии Усова.
4 окт 19, 18:14    [21987034]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1348
Прогнал через свой вариант теста все числа до 232. Количество найденных простых совпало с количеством простых, полученных решетом. Также сравнил список до 224. Ничего лишнего, ничего не пропущено.
5 окт 19, 07:06    [21987246]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1840
Попробовал перейти на раунды.
Пусть раунд - это обращение к основной формуле: pow(a1, t2, p).
Все остальные операторы не так затратны по времени, особенно для больших чисел.
Тогда:

-проверка чисел от- 5 -до - 1000005
-количество простых чисел- 78497
-количество раундов - 3482972
-минимальное количество раундов для числа - 1
-количество минимальных раундов - 421362
-максимальное количество раундов для числа - 39
5 окт 19, 11:19    [21987284]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1840
Далее, ещё интереснее.

Пусть ограничитель для проверки числа 39 раундов.
Для чисел после 2**1024-1 в количестве 10000 получается следующая картинка:

2019-10-05-12.59.02
-количество простых чисел- 14
-количество раундов - 1733
-минимальное количество раундов для числа - 1
-количество минимальных раундов - 1185
-максимальное количество раундов для числа - 39
-количество максимальных раундов - 546
-остаток- 2
2019-10-05-12.59.27

То есть, программа либо сразу сообщает, что число составное, либо все 39 раундов для простого числа.
И всего 2 раунда на более сложную проверку.
5 окт 19, 13:11    [21987307]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1840
Небольшое уточнение.

В предыдущем сообщении представлена распечатка работы программы, когда имеются делители до 100.

Та же программа, в которой нет делителей, выдаёт следующий результат:

-количество простых чисел- 14
-количество раундов - 5520
-минимальное количество раундов для числа - 1
-количество минимальных раундов - 4986
-максимальное количество раундов для числа - 38
-количество максимальных раундов - 532
-остаток- 2
5 окт 19, 20:26    [21987422]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 42918
Интересно. Во главе угла криптографии стоит операция деления. как некий бастион
который ограничивает перформанс криптоанализа. Что-бы мы не делали а эта
операция в стеке - принципиально не оптимизируема. Я думал о машинной реализации.
Судя по описаниям она принципиально не отличается от классического деления в столбик
с той разницей что работает двоичная логика вычитаний. И я подумал - а какую собсвенно
пользу можно извлечь из результата деления. В классическом варианте любая операция
машинного деления на самом деле делает больше. Она фиксирует остаток. Кроме
того если мы используем делители достаточно длинные по разрядной сетке но имеющие
вид последовательности простых то делители не будут сильно отличаться. Фактически
от шага к шагу меняются младшие разряды делителя.
5 окт 19, 22:10    [21987462]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1840
Ещё пример работы программы:

Пусть ограничитель для проверки числа 39 раундов.
Для чисел после 2**2048-1 в количестве 10000 получается следующая картинка:

-количество простых чисел- 7
-количество раундов - 5261
-минимальное количество раундов для числа - 1
-количество минимальных раундов - 4993
-максимальное количество раундов для числа - 38
-количество максимальных раундов - 266
-остаток- 2
6 окт 19, 06:26    [21987527]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1348
Далеко не для каждого составного числа найдется "свидетель простоты" по Рабину-Миллеру, то есть основание, по которому это число будет псевдопростым. На самом деле, такие составные числа, для которых существует хотя бы один свидетель простоты, довольно редки. Но уж если один свидетель простоты существует для некоего составного числа, то их (свидетелей) для этого числа обязательно будет несколько: все они будут корнями какой-то степени из единицы по модулю одного из делителей этого составного числа. Вот именно потому, что свидетели простоты по Миллеру-Рабину всегда появляются пачками, выгоднее не гонять кучу раундов, а использовать другой, независимый тест Люка, который опирается не на мультипликативную группу вычетов, а на другую группу.
6 окт 19, 17:59    [21987680]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1840
Barlone
Далеко не для каждого составного числа найдется "свидетель простоты" по Рабину-Миллеру, то есть основание, по которому это число будет псевдопростым. На самом деле, такие составные числа, для которых существует хотя бы один свидетель простоты, довольно редки. Но уж если один свидетель простоты существует для некоего составного числа, то их (свидетелей) для этого числа обязательно будет несколько: все они будут корнями какой-то степени из единицы по модулю одного из делителей этого составного числа. Вот именно потому, что свидетели простоты по Миллеру-Рабину всегда появляются пачками, выгоднее не гонять кучу раундов, а использовать другой, независимый тест Люка, который опирается не на мультипликативную группу вычетов, а на другую группу.
Тест Люка тоже выполняет серию раундов (основание степени, степень, модуль).
Почему нельзя посчитать количество этих раундов для различных чисел?

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

Откуда:
Сообщений: 1348
Конечно тест Люка вероятностный. Я вообще не про то.
Вот есть списки сильных псевдопростых чисел по разным основаниям. Так вот, далеко не каждое число попадет хотя бы в один такой список. Ну то есть, можно перебрать например все составные нечетные числа n от 15 до 9999, и для каждого перебрать все основания от 2 до n-2 и провести тест Миллера-Рабина. Получить список составных чисел, являющихся псевдопростыми хотя бы по одному основанию.
Потом получить аналогичный список для теста Люка - то есть провести тест по всем вариантам параметров, которые могут использоваться для этого теста, и выписать псевдопростые по Люка хотя бы по одному варианту параметров.
А потом проверить, есть ли в этих двух списках совпадения.
6 окт 19, 19:49    [21987722]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1840
Barlone
Конечно тест Люка вероятностный. Я вообще не про то.
...
можно перебрать например все составные нечетные числа n от 15 до 9999, и для каждого перебрать все основания от 2 до n-2 и провести тест Миллера-Рабина. Получить список составных чисел, являющихся псевдопростыми хотя бы по одному основанию.
Потом получить аналогичный список для теста Люка - то есть провести тест по всем вариантам параметров, которые могут использоваться для этого теста, и выписать псевдопростые по Люка хотя бы по одному варианту параметров.
А потом проверить, есть ли в этих двух списках совпадения.
Есть два варианта: совпадают и не совпадают.
А что дальше?

Надо говорить об этом.
6 окт 19, 20:00    [21987727]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1348
Gennadiy Usov
Barlone
Конечно тест Люка вероятностный. Я вообще не про то.
...
можно перебрать например все составные нечетные числа n от 15 до 9999, и для каждого перебрать все основания от 2 до n-2 и провести тест Миллера-Рабина. Получить список составных чисел, являющихся псевдопростыми хотя бы по одному основанию.
Потом получить аналогичный список для теста Люка - то есть провести тест по всем вариантам параметров, которые могут использоваться для этого теста, и выписать псевдопростые по Люка хотя бы по одному варианту параметров.
А потом проверить, есть ли в этих двух списках совпадения.
Есть два варианта: совпадают и не совпадают.
А что дальше?

Надо говорить об этом.
Есть гипотеза, что совпадений не будет.
6 окт 19, 20:44    [21987764]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1840
Barlone
Gennadiy Usov
Есть два варианта: совпадают и не совпадают.
А что дальше?
Надо говорить об этом.
Есть гипотеза, что совпадений не будет.
Кто бы сомневался.

Если не совпадает, то что делать?
6 окт 19, 20:57    [21987772]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
exp98
Member

Откуда:
Сообщений: 1846
Barlone
Что-то у меня на диапазоне 200000 с 22048 нашлось 151 число.
А ты мне отвечал, что долго считать. За это личное спасибо.
Может всё же сочтёшь кол-во персонально для меня ещё диапазончик
2^4096 +500000, предварительная оценка [ 176,05 + - 13,268 ] ??
Вроде не намного и дольше считать, раз в 5-6 ... я думаю. Мне только кол-во.
9 окт 19, 14:53    [21990502]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1840
mayton
Gennadiy Usov, я несколько раз обращался к тебе с просьбой собрать отклик твоего кода через равные
промежутки интервалов. Я хотел построить график. И по нему оценить асимптоматику. Это важно.
Важные даже не числа а форма графика. Парабола. Экспонента. Или x в степени x как некая ссылка
на комбинаторную сложность. Но мне показалось что данные у тебя беспорядочны и их мало и я отбросил
эту затею.
Насколько я помню, последними таблицами были 21976531 и 21982245.
В последнем сообщении была фраза:
mayton
Добавил 100 тысяч на диапазоне 2048 бит.
Вот данные для проверки. Две таблички надо соединить. Но уже поздно. Я засыпаю.
А далее -
mayton
Я говорю табличку заполните.
В табличках есть параметры:
диапазон, количество простых чисел и время работы программы на диапазоне.

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

Откуда:
Сообщений: 1840
Barlone
Gennadiy Usov
Barlone
Ищем простые от 2^1024 - нашлись 2^1024 + (643, 1081, 2113, 2715, 3711)
Ещё 5335, 5793, 5947, 7015, 7447, 7935, 8953, 8995, 9855.
1 мин. 48 сек.
У меня секунд за 15 те же.
На каждом ПК и на каждом языке программирования свои скорости.

В работе 22011445 рассматривался эвристический алгоритм для определения простых чисел в окрестности чисел Mn = 2^n – 1.

Кроме того, была проведена оценка размера таких окрестностей
с точки зрения отсутствия возможности получения составных чисел при работе эвристического алгоритма.
Поэтому для чисел 2^1024-1 и 2^2048-1 размер такой окрестности будет составлять намного больше, чем 10000 чисел.
Следовательно, в этой окрестности при рассмотрении очередного числа достаточно одно вычисление вида «pow».
Допустим, это "рабочий диапазон".

Для чисел 2^1024-1 и 2^2048-1 рабочий диапазон имеет место как со знаком +, так и со знаком -.

Исследования на ПК для диапазона из 10000 чисел показали, что:
для знака + эвристический алгоритм работает на 4% медленнее оператора pow.
для знака - эвристический алгоритм работает на 3% быстрее оператора pow.

Вне рабочего диапазона (например, очень далеко от чисел 2^1024-1 и 2^2048-1), по всей видимости,
необходимо несколько проверок вида «pow».
13 ноя 19, 16:40    [22015600]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1840
Gennadiy Usov
Следовательно, в этой окрестности при рассмотрении очередного числа достаточно одно вычисление вида «pow».
Допустим, это "рабочий диапазон".
...
Вне рабочего диапазона (например, очень далеко от чисел 2^1024-1 и 2^2048-1), по всей видимости,
необходимо несколько проверок вида «pow».
Конечно, необходимо заметить, что исследования проводились для "pow(3,", или для pow3.

Поэтому, если нужно быстро найти простые числа, то можно их найти в так называемом "рабочем диапазоне" от числа Мерсенна.
И для этого достаточно одно обращение к pow3.

Вне "рабочего диапазона" потребуется уже несколько обращений к pow3,
или несколько обращений к операторам pow с другим основанием степени.

При этом напоминаю, что для чисел Mnk, у которых k кратно 4, "рабочий диапазон" будет намного больше,
чем для остальных чисел Mnk.
16 ноя 19, 09:42    [22017831]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
exp98
Member

Откуда:
Сообщений: 1846
Прошу тебя, друг Аркадий Геннадий, не говори красиво!(цэ):
Gennadiy Usov
Кроме того, была проведена оценка размера таких окрестностей с точки зрения отсутствия возможности получения составных чисел при работе эвристического алгоритма.

Почти ничего не понял в ваших словах, но благодаря следущей строчке:
Gennadiy Usov
Поэтому для чисел 2^1024-1 и 2^2048-1 размер такой окрестности будет составлять намного больше, чем 10000 чисел.
решил прикинуть по науке. Фразу "отсутствия возможности получения составных" интерпретировал как диапазон, гарантирующий (с хорошей долей вероятности) наличие хоть 1 простого. Оценивал на бумажке. Почему-то у меня не получается "намного больше, чем 10000".
Наоборот, если исходить из прикида, что на дальности 1млн от 2^2K кол-во простых можно оценить как наиболее вероятный интервал 72тыс +- 268, то тогда уже на дальности 3620 весьма вероятно 1 простое. А на дальности 10тыс их весьма вероятно 5.
Соответственно, ведя отсчёт от 2^K, в 10тыс поместится простых 11-12 штук.
Кстати другим способом на дальности 10тыс от 2^K их оценивается 14.4 +- 4.
К сож, теорвер не позволяет мне оценить точнее малые кол-ва (точнее конечно будет не на бумажке).

Я это всё к тому, что как-то не понятна фраза про "намного больше, чем 10000".
17 ноя 19, 00:09    [22018018]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1840
exp98
Фразу "отсутствия возможности получения составных" интерпретировал как диапазон, гарантирующий (с хорошей долей вероятности) наличие хоть 1 простого. Оценивал на бумажке. Почему-то у меня не получается "намного больше, чем 10000".
Рабочий диапазон есть диапазон чисел,
где эвристический алгоритм определяет сколько угодно чисел, которые будут простыми числами,
причём ни одно из определённых чисел не будет составным числом.
17 ноя 19, 07:52    [22018063]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
exp98
Member

Откуда:
Сообщений: 1846
автор
Рабочий диапазон есть диапазон чисел, где эвристический алгоритм определяет сколько угодно чисел, которые будут простыми числами, причём ни одно из определённых чисел не будет составным числом.
Видите, даже попытка разъяснить боле-мене конкретный вопрос, всё равно приводит к двусмысленности.
Писать по-русски ведь тоже ещё уметь надо. Тем более технический текст. Обычно почему-то полагается, что читатель проделал к этому моменту тот же самый мыслительный путь, и важно, что остановился на том же самом месте, что и писатель.
И тогда целиком воспроизводится ситуация анекдота: "Да пошла ты наф со своим утюгом!"

Однако практически всегда это не так. Но такой писатель никогда не оценивает со стороны, как писанина будет воспринята. Это не только ваша особенность, большинство прогеров так же пишут.
То же самое относится к вашей самооценке правильности собственной программы, сам сделал, сам написал и ку-ка-ре-ку. А вы все верьте.

Я уже не говорю о спец. подборе слов для выражения мысли ... Как же меня задрали за всю жизнь эти "постановщики задач", приходят и начаинают с "прерваного места". И вы ещё тут ... вот почти и не читаю, но только прочту, блин ... А попытка одной фразой ответиь на неск. вопросов ?..

Вашу двусмысленность наверное (я лищь предполагаю) можно было бы ликвидировать. Но "сколько угодно чисел", да ещё "которые будут простыми" ... наверное это бесконечность, да? впихнутая в конечный диапазон!

Как вариант: РД есть диапазон чисел, в к-ром ЭАGUОПЧ безошибочно определяет любое составное число как составное.

И всё равно остаётся необъяснённым вопрос, не пропускает ли ЭА при этом ПЧ, ошибочно принимая их за составное? (о том, что некто некогда как-то где-то это проверял, я наслышан)
17 ноя 19, 17:36    [22018253]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1840
exp98
автор
Рабочий диапазон есть диапазон чисел, где эвристический алгоритм определяет сколько угодно чисел, которые будут простыми числами, причём ни одно из определённых чисел не будет составным числом.
Как вариант: РД есть диапазон чисел, в к-ром ЭАGUОПЧ (других эвристических алгоритмов пока нет)
безошибочно определяет любое составное число как составное.
Наверное, так будет проще для читателя.

Хотя, любой тест простоты определяет простоту чисел,
то есть, "отсекает" составные числа.
exp98
И всё равно остаётся необъяснённым вопрос, не пропускает ли ЭА при этом ПЧ, ошибочно принимая их за составное? (о том, что некто некогда как-то где-то это проверял, я наслышан)
А всё очень просто. Перебор делителей.
Поэтому на моём ПК получается проверить только до 2^32-1 +k.

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