Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 .. 3 4 5 6 7 8 [9] 10 11 12   вперед  Ctrl      все
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1836
mayton
Вот Люка-Лемер на Питоне. Ничего сказать не могу т.к. не знаю этот язык. Но
информация - к сведенью
https://rosettacode.org/wiki/Lucas-Lehmer_test#Python
На самом деле меня интересует алгоритм, на основании которого построены эти программы.

Люка-Лемер предполагает использование показателя степени 2 исследуемого числа (числа Мерсенна).
А какой показатель степени 2 у числа, например, 12345678901?
25 авг 19, 19:03    [21957275]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1836
mayton
Полистал еще раз википедию чтоб понять вообще названия и терминологию. Нарисовал
mind-map. Прошу прощения. Имена благородных господ-математиков я мог исказить т.к. не везде
написано то как их правильно называть (Solovey или Solovay?)
Схема красивая!

14 тестов на простоту, не считая всякой мелочи, которая регулярно появляется в печати.
И что дальше?

Все эти тесты использовать?
Или всё-таки остановиться на некоторых?
25 авг 19, 19:07    [21957281]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 42897
Надо рисовать матрицу. Например имя теста. Его асимптоматика. И практическое время работы на
небольшой выборке чисел. На разрых порядках. На миллиардах. На триллионах. И так далее.
И есть у меня предположение что истинные тесты простоты слишком долго работают.
Может долгие часы. Или дни. Или годы.

При таком раскладе Миллер+Люка будут выгоднее. Никто не хочет ждать годы для проверки числа.
25 авг 19, 19:17    [21957285]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 42897
Gennadiy Usov
mayton
Вот Люка-Лемер на Питоне. Ничего сказать не могу т.к. не знаю этот язык. Но
информация - к сведенью
https://rosettacode.org/wiki/Lucas-Lehmer_test#Python
На самом деле меня интересует алгоритм, на основании которого построены эти программы.

Люка-Лемер предполагает использование показателя степени 2 исследуемого числа (числа Мерсенна).
А какой показатель степени 2 у числа, например, 12345678901?

Алгоритм - перед вами. Реверс-инжинеринг - это процесс извлечения алгоритма из кода.
Он - тоже работает. А вот за уточняющими вопросами типа показателей степени надо
читать книжки. Я так думаю.
25 авг 19, 19:19    [21957286]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1347
Gennadiy Usov
При этом пришлось изменить уравнение второго условия теста Миллера-Раввина
https://ru.wikipedia.org/wiki/
вместо
-1(mod n)
"подошло"
+1(mod n).
Ерунду вы написали. Вообще-то, если в математической формуле написано "a эквивалентно минус единице по модулю N" (значок такой ≡ из трех черточек), то в программе это будет выглядеть как "a % N == N-1", потому что -1 и N-1 попадают в один класс эквивалентности по модулю N.
26 авг 19, 04:34    [21957420]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1347
Возьмем например простое число N=13, N-1 = 4*3. d=3, s=2
Взяв a=3, получим 2^3 % 13 == 1 - выполнилось первое условие.
Взяв a=10, получим 10^3 % 13 == 12 это минус единица :) и тут сразу выполнилось второе условие, при r==0.
Взяв а=2, получим 2^3 %13 == 8. Надо возводить в квадрат. 8^2 % 13 == 12 вот она минус единица при r==1.

А если у нас составное число, например N=21, N-1 = 4*5, d=5, s=2
Берем а=8, 8^5 % 21 == 8. Первое не выполнено. Берем квадрат 8^2 % 21 == 1. И второе условие не выполнено, значит число составное.
26 авг 19, 04:53    [21957423]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1347
Последний случай кстати самый интересный - когда для какого-то числа а ≠ ±1 mod N оказывается что a² ≡ 1 mod N, то gcd(a+1, N) и gcd(a-1, N) дадут нам делители N.
26 авг 19, 05:11    [21957424]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1347
mayton
Вот Люка-Лемер на Питоне. Ничего сказать не могу т.к. не знаю этот язык. Но
информация - к сведенью

https://rosettacode.org/wiki/Lucas-Lehmer_test#Python
Не, это специализированный тест, для чисел Мерсенна. Есть вариант теста для произвольных чисел. Основа теста: для простого N при каких-то там правильно выбранных P,Q строится последовательность Люка Элемент с номером N+1 этой последовательности должен делиться на N. Если не делится - число признается составным.
Естественно, вся последовательность вычисляется по модулю N. Ну и используются формулы, выражающие Vn+m и Un+m через Vn, Vm, Un, Um
26 авг 19, 08:21    [21957453]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 5341
Gennadiy Usov
mayton
Полистал еще раз википедию чтоб понять вообще названия и терминологию. Нарисовал
mind-map. Прошу прощения. Имена благородных господ-математиков я мог исказить т.к. не везде
написано то как их правильно называть (Solovey или Solovay?)
Схема красивая!

14 тестов на простоту, не считая всякой мелочи, которая регулярно появляется в печати.
И что дальше?

Все эти тесты использовать?
Или всё-таки остановиться на некоторых?
ты же сам ответ дал 21957011
26 авг 19, 08:36    [21957460]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1836
kealon(Ruslan)
Gennadiy Usov
14 тестов на простоту, не считая всякой мелочи, которая регулярно появляется в печати.
И что дальше?
Все эти тесты использовать?
Или всё-таки остановиться на некоторых?
ты же сам ответ дал 21957011
Спасибо, что нашли мою цитату!

Но эта цитата только о " псевдопростых или вероятностно простых" числах.

Нам же нужно повысить степень, так называемой, "псевдопростоты",
которая должна, по каким-нибудь своим законам, стремиться к простоте.
26 авг 19, 11:17    [21957531]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1836
Barlone
mayton
Вот Люка-Лемер на Питоне. Ничего сказать не могу т.к. не знаю этот язык. Но
информация - к сведенью
https://rosettacode.org/wiki/Lucas-Lehmer_test#Python
Не, это специализированный тест, для чисел Мерсенна. Есть вариант теста для произвольных чисел. Основа теста: для простого N при каких-то там правильно выбранных P,Q строится последовательность Люка Элемент с номером N+1 этой последовательности должен делиться на N. Если не делится - число признается составным.
Естественно, вся последовательность вычисляется по модулю N. Ну и используются формулы, выражающие Vn+m и Un+m через Vn, Vm, Un, Um
Но это очень сложно.

Чтобы узнать, является ли число N, очень большое, надо найти (!) (N +1) число последовательности Люка!

То есть, если число 2^1024-1, то надо знать 2^1024 элемент последовательности Люка.
А эта последовательность может строиться только от первого числа!
26 авг 19, 11:25    [21957540]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 42897
Barlone
mayton
Вот Люка-Лемер на Питоне. Ничего сказать не могу т.к. не знаю этот язык. Но
информация - к сведенью

https://rosettacode.org/wiki/Lucas-Lehmer_test#Python
Не, это специализированный тест, для чисел Мерсенна. Есть вариант теста для произвольных чисел. Основа теста: для простого N при каких-то там правильно выбранных P,Q строится последовательность Люка Элемент с номером N+1 этой последовательности должен делиться на N. Если не делится - число признается составным.
Естественно, вся последовательность вычисляется по модулю N. Ну и используются формулы, выражающие Vn+m и Un+m через Vn, Vm, Un, Um

ОК. Спасибо. Может вы знаете готовую имплементацию подобного метода nextProbablePrime для Python?
26 авг 19, 12:30    [21957583]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1347
Gennadiy Usov
Чтобы узнать, является ли число N, очень большое, надо найти (!) (N +1) число последовательности Люка!

То есть, если число 2^1024-1, то надо знать 2^1024 элемент последовательности Люка.
А эта последовательность может строиться только от первого числа!
Ага, и чтобы повести тест Ферма для этого числа, надо посчитать а(21024-2) но это же не значит, что нужно 21024-3 умножений на а.

Barlone
Естественно, вся последовательность вычисляется по модулю N. Ну и используются формулы, выражающие Vn+m и Un+m через Vn, Vm, Un, Um
26 авг 19, 14:56    [21957686]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1836
Barlone
Gennadiy Usov
Чтобы узнать, является ли число N, очень большое, надо найти (!) (N +1) число последовательности Люка!То есть, если число 2^1024-1, то надо знать 2^1024 элемент последовательности Люка.
А эта последовательность может строиться только от первого числа!
Ага, и чтобы повести тест Ферма для этого числа, надо посчитать а(21024-2) но это же не значит, что нужно 21024-3 умножений на а.
Barlone
Естественно, вся последовательность вычисляется по модулю N. Ну и используются формулы, выражающие Vn+m и Un+m через Vn, Vm, Un, Um
Если я правильно понял, числа V2^1024-1 и U2^1024-1 нужно разложить на V и U.
А эти V и U разложить на следующие V и U. И т.д.

И сколько будет чисел в этой цепочке, пока мы не "дойдём" до вычисляемых чисел Люка?

Кстати, хорошо делить число, когда оно чётное. А если очередное число нечётное?
26 авг 19, 18:07    [21957827]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1347
Gennadiy Usov,
да всё так же, как с возведением в степень
Из U1,V1 получаем U2,V2, из них U4,V4, … и дальше по степеням двойки. Ну и по двоичному представлению нужного значения собираем результат - например, комбинируя пару U1,V1 c U4,V4 - получим U5,V5.
26 авг 19, 18:32    [21957840]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1347
Формулы есть в английской вики
Картинка с другого сайта.
26 авг 19, 18:39    [21957848]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1836
mayton
Вот Люка-Лемер на Питоне. Ничего сказать не могу т.к. не знаю этот язык. Но
информация - к сведенью
https://rosettacode.org/wiki/Lucas-Lehmer_test#Python
Спасибо за программу!

Есть, правда одно ограничение:
maximum requested number of decimal places of 2 ** MP-1 #

Это ограничение для Python?
26 авг 19, 19:16    [21957872]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 42897
Не знаю. Давайте Python-специфичные вопросы задавать тут https://www.sql.ru/forum/php-perl
26 авг 19, 19:35    [21957880]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1836
mayton
Вот Люка-Лемер на Питоне. https://rosettacode.org/wiki/Lucas-Lehmer_test#Python
Запустил программу на своём стареньком компьютере (лет 10), и нашел все числа Мерсенна до 9941 где-то за 40 минут.

Перед этим запустил программу с тестом Миллера-Рабина, и оказалось, что этот тест хорошо подходит для определения чисел Мерсенна.
На своём стареньком компьютере нашел все числа Мерсенна до 9941 где-то за 2 часа.
26 авг 19, 19:51    [21957887]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 42897
from sys import stdout
from math import sqrt, log
 
def is_prime ( p ):
  if p == 2: return True # Lucas-Lehmer test only works on odd primes
  elif p <= 1 or p % 2 == 0: return False
  else:
    for i in range(3, int(sqrt(p))+1, 2 ): 
      if p % i == 0: return False
    return True


Это знакомый мне фрагмент. Это брут-форс. Самый медленный и бестолковый алгоритм.
Мы с Димой его оптимизировали его добавляя переменный шаг.


       uint64_t step = 4;
        

        for (uint64_t c1 = min_prime; c1 <= max_prime; c1 += step) {
                step^=0x0006;


На первом шаге step=4. Потом step = step XOR (0110). Тоесть инвертируем 2 и третий биты. Получается чередование 4
и 2. Потом еще и найденные простые накапливаются в массиве и участвуют в проверке делителей.
26 авг 19, 20:17    [21957894]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 42897
В своих экспериментах я выкидывал квадратный корень и заменял его на линейную
функцию. Которая кусочно апроксимирует корень. Пилообразно. Собсно там пойдет
любая легко-вычислимая функция которая заведомо выше чем p для любых p.
26 авг 19, 20:45    [21957909]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1836
mayton
На первом шаге step=4. Потом step = step XOR (0110). Тоесть инвертируем 2 и третий биты. Получается чередование 4
и 2. Потом еще и найденные простые накапливаются в массиве и участвуют в проверке делителей.
Я уже приводил чередование 4 и 2 21952153.

Накопление простых в массиве может когда-то прекратиться.(на больших числах)
26 авг 19, 20:51    [21957913]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 42897
Gennadiy Usov
mayton
На первом шаге step=4. Потом step = step XOR (0110). Тоесть инвертируем 2 и третий биты. Получается чередование 4
и 2. Потом еще и найденные простые накапливаются в массиве и участвуют в проверке делителей.
Я уже приводил чередование 4 и 2 21952153.

Накопление простых в массиве может когда-то прекратиться.(на больших числах)

А тебе много и не надо. Накопи простых хотя-бы тыщу. Большая часть делителей
отбивается на самых ранних шагах.
26 авг 19, 20:54    [21957917]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Dima T
Member

Откуда:
Сообщений: 14090
mayton
В своих экспериментах я выкидывал квадратный корень и заменял его на линейную
функцию. Которая кусочно апроксимирует корень. Пилообразно. Собсно там пойдет
любая легко-вычислимая функция которая заведомо выше чем p для любых p.

Лучше переиначить алгоритм чтобы вместо извлечения корня было возведение в квадрат. Умножение намного быстрее происходит.
26 авг 19, 20:56    [21957920]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 42897
Согласен. Кстати я бы поднял отдельный топик. Быстрое умножение и быстрое возведение в квадрат
для arbitary precision. Просто для того чтобы провести ревизию текущих API и библиотек. Используют
они эти методы или нет.

А то меня терзают смутные сомнения.
26 авг 19, 21:50    [21957937]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 .. 3 4 5 6 7 8 [9] 10 11 12   вперед  Ctrl      все
Все форумы / Программирование Ответить