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

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

А то меня терзают смутные сомнения.
https://ru.wikipedia.org/wiki/Умножение_Карацубы
27 авг 19, 05:15    [21958018]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1836
mayton
Gennadiy Usov
Я уже приводил чередование 4 и 2 21952153.
Накопление простых в массиве может когда-то прекратиться.(на больших числах)
А тебе много и не надо. Накопи простых хотя-бы тыщу.
Большая часть делителей отбивается на самых ранних шагах.
Можно применить "ленивый алгоритм накопленных простых чисел".
О нём уже было сказано21954752.
Поскольку там ошибка, привожу ещё раз (без ошибки)
#p - исходное число			
prost_list = [22,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,79,83,89]			
s1 = 1			
sn = prost_list[0]			
while s1 <= sn:			
	q = prost_list[s1]		
	w2 = p % q		
		if w2 == 0:	
			 и т.д.
В массив можно записать хоть 1000 чисел.
27 авг 19, 07:50    [21958033]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 42897
Почему 22 ?
27 авг 19, 13:05    [21958260]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

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

Квадраты последовательных чисел N и (N + 1) отстоят друг от друга на (2*N+1).
Поскольку делители - только нечётные числа, то N и (N + 2) отстоят друг от друга на (4*N+4).

Итак, в начале находим корень минимума диапазона, от целого этого числа получаем "квадрат N",
и это будет точкой отсчета по смене величины, которая ограничивает количество делителей.

Осталось проверять расстояние исследуемого числа от предыдущего "квадрата N",
и если получаемое расстояние превышает (4*N+4) от этого "квадрата N",
то определяется новый "квадрат N+1", равный увеличению предыдущего "квадрата N" на (4*N+4).
27 авг 19, 13:14    [21958264]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1836
mayton
Почему 22 ?
Очень удобно в одном массиве в ячейке [0] помещать длину массива данных,
и "работать" с массивом, начиная с ячейки [1].

Мы ведь привыкли считать: 1,2,,,,,,n,
а не 0,1,2,,,,,(n-1)

И притом, нужна будет отдельная переменная для хранения количества данных в массиве.

Кстати, я уже это демонстрировал на предыдущих топиках.
27 авг 19, 13:19    [21958268]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 42897
Почитал про Питон.

Длину массива берут так.
>>> prost_list = [22,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,79,83,89]
>>> len(prost_list)
23
>>>

Только в интенсивных циклах я-бы все равно поместил это число в отдельную переменную.
Просто так и яснее и не будет потенциальных проблем с перформансом. Мы ведь не знаем
как дорого для питона стоит эта операция взятия длины. Для С++ ASCIIZ-массивов она стоила
линейно от длины самой строчки. Тоесть чем длиннее строка тем дольше ждать.
27 авг 19, 14:12    [21958333]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1836
Решил ещё раз поработать с тестом Миллера-Рабина с точки зрения:
какой перечень остатков выдаёт этот тест.

Пока поработал с числами до 115.

Есть простые числа, для которых только 1 или n-1 по двум условиям теста:
7, 11,19,23,31,43,47,59,67,71,79,83,103,107

Есть простые числа, для которых только 1 или n-1 по двум условиям теста не для всех случайных чисел:
29,37,41,61,73,89,101,109,113

Есть простые числа, для которых только 1 или n-1 только по второму условию:
5,13,17(не все),53,97(не все),

Есть составные числа, для которых только 1 только по второму условию:
39, 105.
Поэтому по второму условию значение 1 не подходит.
27 авг 19, 18:17    [21958523]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1347
Gennadiy Usov,

Выпишите несколько табличек для разных простых n: в первый столбец все числа от 1 до n-1, а в строку их степени по модулю n.
Например для 5 так
1 1 1 1 1
2 4 3 1 2
3 4 2 1 3
4 1 4 1 4
Почитайте про первообразный корень.

А потом выпишите такую же табличку для составного числа. Только надо как-то еще мелкими циферками в каждую клеточку дописать остатки по каждому сомножителю этого числа. Прочитайте про китайскую теорему об остатках.
А чтобы понять, как получаются псевдопростые, надо сделать такую табличку для составного числа, у которого большой НОД(φ(n), n-1). Ну например 91=7*13, НОД(90, 72)=18. Правда, табличка большая получится, но если над ней помедитировать, то озарение обязательно придет.
27 авг 19, 20:35    [21958576]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1836
Barlone,

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

Вопрос в том, как можно применять тест Миллера-Рабина, на каких числах, на каких остатках.

Хотя это и вероятностный тест, для каких-то чисел он может быть достаточным.
27 авг 19, 21:16    [21958593]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 42897
Если бы мы знали как разделить область определения Миллера-Раввина на детерминированную и случайную то получили бы две функции. Причем одна из них была бы строго детерминирована по определению.
27 авг 19, 21:23    [21958596]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1347
Gennadiy Usov,

Нормально можно применять, на любых числах. Раудов побольше и всё. Вот при количестве раундов порядка log(n) от становится детерминированным.
27 авг 19, 21:25    [21958598]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1347
Gennadiy Usov
Barlone,

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

Вопрос в том, как можно применять тест Миллера-Рабина, на каких числах, на каких остатках.

Хотя это и вероятностный тест, для каких-то чисел он может быть достаточным.
Вопрос как раз в том, как получаются псевдопростые.
27 авг 19, 21:34    [21958599]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1347
Я могу привести критерий, для каких оснований k по модулю составного числа n тест гарантированно покажет, что число составное. Только этот критерий будет абсолютно бесполезным :)
27 авг 19, 21:38    [21958601]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1836
mayton
Если бы мы знали как разделить область определения Миллера-Раввина на детерминированную и случайную то получили бы две функции.
Причем одна из них была бы строго детерминирована по определению.
Пример 21957887 показал, что тест Миллера-Раввина находит среди чисел Мерсенна только простые числа без пропусков,
причем только с помощью первого условия.
Правда, медленнее теста Люка-Лемера раза в 2-3.
Это уже область применения без появления составных чисел.
Barlone
Gennadiy Usov,
Нормально можно применять, на любых числах. Раудов побольше и всё. Вот при количестве раундов порядка log(n) от становится детерминированным.
Увеличение количества раундов приведёт к тому, что для некоторых составных чисел может появиться 1 или (n - 1) (пример -21956300),
из-за которых эти числа принимаются тестом как простые.
Barlone
Gennadiy Usov
Barlone,
Вопрос не в том, как получаются псевдопростые числа.
Вопрос в том, как можно применять тест Миллера-Рабина, на каких числах, на каких остатках.
Хотя это и вероятностный тест, для каких-то чисел он может быть достаточным.
Вопрос как раз в том, как получаются псевдопростые.
При исследовании теста Миллера-Рабина (может быть и других тестов)
необходимо для каждого составного небольшого числа (как примера) отследить появление условий 1 или (n - 1),
частоту их появления и тогда принимать какие-то решения по этим результатам.
Например, есть числа 21958523, для которых тест Миллера-Рабина показывает только 1 или (n - 1) по двум условиям.

Здесь можно говорить о подмножестве простых чисел, для которых существует достаточное условие (примерно как в 21907153).
Barlone
Я могу привести критерий, для каких оснований k по модулю составного числа n тест гарантированно покажет, что число составное. Только этот критерий будет абсолютно бесполезным :)
С удовольствием прочитаю.
28 авг 19, 07:01    [21958707]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1347
Gennadiy Usov
Увеличение количества раундов приведёт к тому, что для некоторых составных чисел может появиться 1 или (n - 1) (пример -21956300),
из-за которых эти числа принимаются тестом как простые.
Не так это работает. Каждый раунд говорит либо "число точно составное", либо "не уверен, может быть простым." Если хотя бы один из раундов сказал, что число точно составное - то оно таки составное.
А чтобы доказать, что число простое, надо очень много раундов, порядка log(n) - это уже детерминированный вариант теста.
28 авг 19, 07:58    [21958728]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 42897
Gennadiy Usov,

Ты как то по своему понял смысл раунда.
Там нет голосования. Там - право вето.

Первый раунд который детектировал составное - отменяет все результаты до этого.
28 авг 19, 08:01    [21958731]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1836
У меня 2 вопроса ( с учетом примера 21956300) для чисел 2047 и 2053:

Пока для первого условия теста Миллера-Рабина:

для числа 2047 (составное) после нескольких раундов (выбор случайного числа) появляется 1.
Это означает, что число 2047 псевдопростое?

для числа 2053 (простое) в течении нескольких раундов (выбор случайного числа) не будет появляться 1.
Это означает, что число 2053 составное?
28 авг 19, 09:01    [21958763]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1836
Решил "отбросить" поиск случайного числа для первого условия теста Миллера-Рабина
и заменил этот поиск на перебор вариантов от 2 до (n - 2). Для чисел до 115 - не так много информации.

Оказалось, что:

1. Есть числа, у которых в остатке (по модулю) получается только 1 и (n - 1).
Множество таких чисел уже может быть подмножеством простых чисел.

2. Есть числа, которые мы считаем простыми,
у которых в остатке (по модулю) значения 1 и (n - 1) составляют от 70% до 5% от общего перечня остатков.
Для некоторых из этих чисел трудно будет найти значение 1.

3. Есть числа, которые мы считаем составными, у которых в остатке (по модулю) получается только 1.
В разных числах 1, 2, 5 значений.

4. Есть числа, у которых при переборе от 2 до (n - 2) остатки (по модулю) то же плавно возрастают от 2 до (n - 2).
28 авг 19, 13:31    [21959038]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1836
Ошибся.
пункт 3 предыдущего сообщения надо читать так:

3. Есть числа, которые мы считаем составными, у которых в остатке (по модулю) получается иногда 1.
В разных числах 1, 2, 5 значений.
28 авг 19, 13:38    [21959044]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

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

Поэтому код с комментариями эффективнее чем просто текст который все не поняли
или интерпретировали по разному. Вот такие они... программисты.
28 авг 19, 16:15    [21959227]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1836
mayton
Я давно наблюдаю за форумом. И заметил что программисты очень не любят читать прозу.
Зато исходник вызывает у них живой интерес. Если ты просто опубликуешь работающий
код на Питоне то ты имеешь шанс получить ответ на твой вопрос.
Поэтому код с комментариями эффективнее чем просто текст который все не поняли
или интерпретировали по разному. Вот такие они... программисты.
А как они пишут новую программу?

По другому коду или по алгоритму?
28 авг 19, 16:20    [21959233]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 42897
Не могу сказать. Это очень творческий процесс. Впрочем как и всё чем мы тут занимаемся.
28 авг 19, 16:25    [21959240]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1836
mayton
Если ты просто опубликуешь работающий
код на Питоне то ты имеешь шанс получить ответ на твой вопрос.
Для сообщения 21959038 и 21959044 была сделана очень простенькая программа на Питоне:
import random					
import math					
aaa1 = 0					
aaa2 = 0					
p =5					
P = p + 110					
while p <=P:					
	print (p)				
	t = p - 1				
	s = 0				
	while (t % 2 == 0):				
		t //= 2;			
		s += 1;			
	t1 = t//1				
	y = math.log( p )				
	#print (t,s)				
	y1 = 2				
	while y1 <= p-2:				
		#c = random.randint(2, p-2)			
		#print (c,y1)			
		x = pow(y1, t1, p)			
		print ("y",x,t1,y1)			
		y1 +=1			
	p +=2		
28 авг 19, 19:19    [21959374]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 42897
Gennadiy Usov
	y = math.log( p )				

		x = pow(y1, t1, p)			

Мне кажется тут ослаблен контроль над типами. Кажется что натуральный логарифм и степень
возвращают число с плавающей точкой. А это не очень согласуется с решаемой задачей где
везде и всегда будут целые числа произвольной точности (arbitrary precision).
28 авг 19, 23:34    [21959443]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 42897
Почитал Википедию.

Этот исходник 21954899 - это не Люка-Лемьер.

Это Люка-Лемьер-Ризель (LLT) предположительно. Поэтому все что я писал надо читать с поправкой по этому названию.
28 авг 19, 23:45    [21959450]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 .. 3 4 5 6 7 8 9 [10] 11 12   вперед  Ctrl      все
Все форумы / Программирование Ответить