ReSQL.ru
     
powered by simpleCommunicator - 2.0.49     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Ещё раз о тесте Ферма
25 сообщений из 283, страница 9 из 12
  9  все
Ещё раз о тесте Ферма
    #39853574
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
maytonВот Люка-Лемер на Питоне. Ничего сказать не могу т.к. не знаю этот язык. Но
информация - к сведенью
https://rosettacode.org/wiki/Lucas-Lehmer_test#Python На самом деле меня интересует алгоритм, на основании которого построены эти программы.

Люка-Лемер предполагает использование показателя степени 2 исследуемого числа (числа Мерсенна).
А какой показатель степени 2 у числа, например, 12345678901?
...
Рейтинг: 0 / 0
25.08.2019, 19:03
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39853575
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
maytonПолистал еще раз википедию чтоб понять вообще названия и терминологию. Нарисовал
mind-map. Прошу прощения. Имена благородных господ-математиков я мог исказить т.к. не везде
написано то как их правильно называть (Solovey или Solovay?)Схема красивая!

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

Все эти тесты использовать?
Или всё-таки остановиться на некоторых?
...
Рейтинг: 0 / 0
25.08.2019, 19:07
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39853576
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Надо рисовать матрицу. Например имя теста. Его асимптоматика. И практическое время работы на
небольшой выборке чисел. На разрых порядках. На миллиардах. На триллионах. И так далее.
И есть у меня предположение что истинные тесты простоты слишком долго работают.
Может долгие часы. Или дни. Или годы.

При таком раскладе Миллер+Люка будут выгоднее. Никто не хочет ждать годы для проверки числа.
...
Рейтинг: 0 / 0
25.08.2019, 19:17
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39853577
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Gennadiy UsovmaytonВот Люка-Лемер на Питоне. Ничего сказать не могу т.к. не знаю этот язык. Но
информация - к сведенью
https://rosettacode.org/wiki/Lucas-Lehmer_test#Python На самом деле меня интересует алгоритм, на основании которого построены эти программы.

Люка-Лемер предполагает использование показателя степени 2 исследуемого числа (числа Мерсенна).
А какой показатель степени 2 у числа, например, 12345678901?
Алгоритм - перед вами. Реверс-инжинеринг - это процесс извлечения алгоритма из кода.
Он - тоже работает. А вот за уточняющими вопросами типа показателей степени надо
читать книжки. Я так думаю.
...
Рейтинг: 0 / 0
25.08.2019, 19:19
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39853621
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
Gennadiy UsovПри этом пришлось изменить уравнение второго условия теста Миллера-Раввина
https://ru.wikipedia.org/wiki/
вместо
-1(mod n)
"подошло"
+1(mod n).Ерунду вы написали. Вообще-то, если в математической формуле написано "a эквивалентно минус единице по модулю N" (значок такой ≡ из трех черточек), то в программе это будет выглядеть как "a % N == N-1", потому что -1 и N-1 попадают в один класс эквивалентности по модулю N.
...
Рейтинг: 0 / 0
26.08.2019, 04:34
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39853622
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
Возьмем например простое число 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. И второе условие не выполнено, значит число составное.
...
Рейтинг: 0 / 0
26.08.2019, 04:53
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39853623
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
Последний случай кстати самый интересный - когда для какого-то числа а ≠ ±1 mod N оказывается что a² ≡ 1 mod N , то gcd(a+1, N) и gcd(a-1, N) дадут нам делители N.
...
Рейтинг: 0 / 0
26.08.2019, 05:11
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39853636
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
maytonВот Люка-Лемер на Питоне. Ничего сказать не могу т.к. не знаю этот язык. Но
информация - к сведенью

https://rosettacode.org/wiki/Lucas-Lehmer_test#Python Не, это специализированный тест, для чисел Мерсенна. Есть вариант теста для произвольных чисел. Основа теста: для простого N при каких-то там правильно выбранных P,Q строится последовательность Люка Элемент с номером N+1 этой последовательности должен делиться на N. Если не делится - число признается составным.
Естественно, вся последовательность вычисляется по модулю N. Ну и используются формулы, выражающие V n+m и U n+m через V n , V m , U n , U m
...
Рейтинг: 0 / 0
26.08.2019, 08:21
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39853640
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
Gennadiy UsovmaytonПолистал еще раз википедию чтоб понять вообще названия и терминологию. Нарисовал
mind-map. Прошу прощения. Имена благородных господ-математиков я мог исказить т.к. не везде
написано то как их правильно называть (Solovey или Solovay?)Схема красивая!

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

Все эти тесты использовать?
Или всё-таки остановиться на некоторых?ты же сам ответ дал 21957011
...
Рейтинг: 0 / 0
26.08.2019, 08:36
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39853678
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
kealon(Ruslan)Gennadiy Usov14 тестов на простоту, не считая всякой мелочи, которая регулярно появляется в печати.
И что дальше?
Все эти тесты использовать?
Или всё-таки остановиться на некоторых?ты же сам ответ дал 21957011 Спасибо, что нашли мою цитату!

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

Нам же нужно повысить степень, так называемой, "псевдопростоты",
которая должна, по каким-нибудь своим законам, стремиться к простоте.
...
Рейтинг: 0 / 0
26.08.2019, 11:17
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39853685
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
BarlonemaytonВот Люка-Лемер на Питоне. Ничего сказать не могу т.к. не знаю этот язык. Но
информация - к сведенью
https://rosettacode.org/wiki/Lucas-Lehmer_test#Python Не, это специализированный тест, для чисел Мерсенна. Есть вариант теста для произвольных чисел. Основа теста: для простого N при каких-то там правильно выбранных P,Q строится последовательность Люка Элемент с номером N+1 этой последовательности должен делиться на N. Если не делится - число признается составным.
Естественно, вся последовательность вычисляется по модулю N. Ну и используются формулы, выражающие V n+m и U n+m через V n , V m , U n , U m Но это очень сложно.

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

То есть, если число 2^1024-1, то надо знать 2^1024 элемент последовательности Люка.
А эта последовательность может строиться только от первого числа!
...
Рейтинг: 0 / 0
26.08.2019, 11:25
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39853702
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
BarlonemaytonВот Люка-Лемер на Питоне. Ничего сказать не могу т.к. не знаю этот язык. Но
информация - к сведенью

https://rosettacode.org/wiki/Lucas-Lehmer_test#Python Не, это специализированный тест, для чисел Мерсенна. Есть вариант теста для произвольных чисел. Основа теста: для простого N при каких-то там правильно выбранных P,Q строится последовательность Люка Элемент с номером N+1 этой последовательности должен делиться на N. Если не делится - число признается составным.
Естественно, вся последовательность вычисляется по модулю N. Ну и используются формулы, выражающие V n+m и U n+m через V n , V m , U n , U m
ОК. Спасибо. Может вы знаете готовую имплементацию подобного метода nextProbablePrime для Python?
...
Рейтинг: 0 / 0
26.08.2019, 12:30
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39853749
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
Gennadiy UsovЧтобы узнать, является ли число N, очень большое, надо найти (!) (N +1) число последовательности Люка!

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

BarloneЕстественно, вся последовательность вычисляется по модулю N. Ну и используются формулы, выражающие V n+m и U n+m через V n , V m , U n , U m
...
Рейтинг: 0 / 0
26.08.2019, 14:56
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39853848
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
BarloneGennadiy UsovЧтобы узнать, является ли число N, очень большое, надо найти (!) (N +1) число последовательности Люка!То есть, если число 2^1024-1, то надо знать 2^1024 элемент последовательности Люка.
А эта последовательность может строиться только от первого числа!Ага, и чтобы повести тест Ферма для этого числа, надо посчитать а (21024 -2) но это же не значит, что нужно 2 1024 -3 умножений на а.
BarloneЕстественно, вся последовательность вычисляется по модулю N. Ну и используются формулы, выражающие V n+m и U n+m через V n , V m , U n , U m Если я правильно понял, числа V 2^1024-1 и U 2^1024-1 нужно разложить на V и U.
А эти V и U разложить на следующие V и U. И т.д.

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

Кстати, хорошо делить число, когда оно чётное. А если очередное число нечётное?
...
Рейтинг: 0 / 0
26.08.2019, 18:07
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39853856
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
Gennadiy Usov,
да всё так же, как с возведением в степень
Из U1,V1 получаем U2,V2, из них U4,V4, … и дальше по степеням двойки. Ну и по двоичному представлению нужного значения собираем результат - например, комбинируя пару U1,V1 c U4,V4 - получим U5,V5.
...
Рейтинг: 0 / 0
26.08.2019, 18:32
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39853860
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
Формулы есть в английской вики
...
Рейтинг: 0 / 0
26.08.2019, 18:39
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39853876
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
maytonВот Люка-Лемер на Питоне. Ничего сказать не могу т.к. не знаю этот язык. Но
информация - к сведенью
https://rosettacode.org/wiki/Lucas-Lehmer_test#Python Спасибо за программу!

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

Это ограничение для Python?
...
Рейтинг: 0 / 0
26.08.2019, 19:16
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39853882
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Не знаю. Давайте Python-специфичные вопросы задавать тут https://www.sql.ru/forum/php-perl
...
Рейтинг: 0 / 0
26.08.2019, 19:35
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39853888
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
maytonВот Люка-Лемер на Питоне. https://rosettacode.org/wiki/Lucas-Lehmer_test#Python Запустил программу на своём стареньком компьютере (лет 10), и нашел все числа Мерсенна до 9941 где-то за 40 минут.

Перед этим запустил программу с тестом Миллера-Рабина, и оказалось, что этот тест хорошо подходит для определения чисел Мерсенна.
На своём стареньком компьютере нашел все числа Мерсенна до 9941 где-то за 2 часа.
...
Рейтинг: 0 / 0
26.08.2019, 19:51
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39853893
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Код: python
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
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



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


Код: plaintext
1.
2.
3.
4.
5.
       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. Потом еще и найденные простые накапливаются в массиве и участвуют в проверке делителей.
...
Рейтинг: 0 / 0
26.08.2019, 20:17
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39853901
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
В своих экспериментах я выкидывал квадратный корень и заменял его на линейную
функцию. Которая кусочно апроксимирует корень. Пилообразно. Собсно там пойдет
любая легко-вычислимая функция которая заведомо выше чем p для любых p.
...
Рейтинг: 0 / 0
26.08.2019, 20:45
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39853904
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
maytonНа первом шаге step=4. Потом step = step XOR (0110). Тоесть инвертируем 2 и третий биты. Получается чередование 4
и 2. Потом еще и найденные простые накапливаются в массиве и участвуют в проверке делителей.Я уже приводил чередование 4 и 2 21952153 .

Накопление простых в массиве может когда-то прекратиться.(на больших числах)
...
Рейтинг: 0 / 0
26.08.2019, 20:51
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39853906
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Gennadiy UsovmaytonНа первом шаге step=4. Потом step = step XOR (0110). Тоесть инвертируем 2 и третий биты. Получается чередование 4
и 2. Потом еще и найденные простые накапливаются в массиве и участвуют в проверке делителей.Я уже приводил чередование 4 и 2 21952153 .

Накопление простых в массиве может когда-то прекратиться.(на больших числах)
А тебе много и не надо. Накопи простых хотя-бы тыщу. Большая часть делителей
отбивается на самых ранних шагах.
...
Рейтинг: 0 / 0
26.08.2019, 20:54
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39853909
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonВ своих экспериментах я выкидывал квадратный корень и заменял его на линейную
функцию. Которая кусочно апроксимирует корень. Пилообразно. Собсно там пойдет
любая легко-вычислимая функция которая заведомо выше чем p для любых p.
Лучше переиначить алгоритм чтобы вместо извлечения корня было возведение в квадрат. Умножение намного быстрее происходит.
...
Рейтинг: 0 / 0
26.08.2019, 20:56
| Ответить | Цитировать | Написать  
Ещё раз о тесте Ферма
    #39853920
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Согласен. Кстати я бы поднял отдельный топик. Быстрое умножение и быстрое возведение в квадрат
для arbitary precision. Просто для того чтобы провести ревизию текущих API и библиотек. Используют
они эти методы или нет.

А то меня терзают смутные сомнения.
...
Рейтинг: 0 / 0
26.08.2019, 21:50
| Ответить | Цитировать | Написать  
25 сообщений из 283, страница 9 из 12
  9  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Ещё раз о тесте Ферма
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
NoSQL.ru       Новости, Чат       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=39853882&tid=1339906]:
 0ms
get settings:
 10ms
get forum list:
 13ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 177ms
get topic data:
 9ms
get forum data:
 2ms
get page messages:
 63ms
get tp. blocked users:
 1ms
others: 276ms
total:  557ms
созд. / загр.: 557ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]