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

Откуда:
Сообщений: 1348
Gennadiy Usov
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		
Код недоделанный.
После x = pow(y1, t1, p) надо еще
z = 0
while z < s and x != 1 and x != p-1
29 авг 19, 06:16    [21959501]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1348
x = x*x % p
29 авг 19, 06:17    [21959502]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1348
Недописанное ушло, 2 раза

z = 0
while z < s and x != 1 and x != p-1
x = x*x % p
z = z + 1
29 авг 19, 06:18    [21959503]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
Barlone
Код недоделанный.
После x = pow(y1, t1, p) надо еще
z = 0
while z < s and x != 1 and x != p-1
x = x*x % p
z = z + 1
Это второе условие теста Миллера-Рабина?

В коде 21959374 я рассматривал только первое условие теста.
Этот код необходим для оценки показаний остатков по модулю после применения различных случайных чисел.
29 авг 19, 13:51    [21959832]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 48659
Gennadiy Usov
А как они пишут новую программу?

Подавляющее большинство делает это копипастом с гугля.
29 авг 19, 14:06    [21959848]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1348
Gennadiy Usov
Это второе условие теста Миллера-Рабина?

В коде 21959374 я рассматривал только первое условие теста.
Ну тогда у вас не тест Миллера-Рабина, а неведомая хрень.
29 авг 19, 15:18    [21959927]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
Barlone
Gennadiy Usov
Это второе условие теста Миллера-Рабина?
В коде 21959374 я рассматривал только первое условие теста.
Ну тогда у вас не тест Миллера-Рабина, а неведомая хрень.
Как в том анекдоте:
хрень, не хрень, а работает.

Я просто спросил, а тут такие выводы...

Я предупреждал, что в сообщении 21958523 рассматриваю только первое условие теста Миллера-Рабина,
причем было оговорено: "какой перечень остатков выдаёт этот тест".

Поскольку случайное число получается от 2 до (n - 2 ),
то, естественно, было интересно:
а что получится, если все случайные числа 2 до (n - 2 ) будут "применены".

Таким образом, я посчитал все остатки по модулю при подстановке всех возможных случайных чисел для чисел от 5 до 115.

Была составлена программа, были получены результаты, в сообщении 21958523 показаны основные выводы,
а в сообщении 21959374 показан код такой программы на Питоне.
29 авг 19, 15:55    [21959963]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
Dimitry Sibiryakov
Gennadiy Usov
А как они пишут новую программу?
Подавляющее большинство делает это копипастом с гугля.
То есть, основополагающие алгоритмы никто не читает?

Была такая игра: каждый в цепочке на ухо сообщает другому в цепочке слово, и какое слово пролучается в конце цепочки.
Или что-то похожее...
29 авг 19, 16:00    [21959971]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 42946
Основные алгоритмы описаны в Википедии.

Но этот форум обычно обсуждает их реализации на конкретных языках и конфигурациях.
29 авг 19, 21:40    [21960154]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 5345
Gennadiy Usov
Dimitry Sibiryakov
пропущено...
Подавляющее большинство делает это копипастом с гугля.
То есть, основополагающие алгоритмы никто не читает?
очень редко кто, подавляющему большинству просто некогда, индустрия требует здесь и сейчас
30 авг 19, 00:18    [21960200]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1348
Dimitry Sibiryakov
Gennadiy Usov
А как они пишут новую программу?

Подавляющее большинство делает это копипастом с гугля.
Некоторые тут и даже и копипаст не могут.
30 авг 19, 08:34    [21960247]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1348
kealon(Ruslan)
очень редко кто, подавляющему большинству просто некогда, индустрия требует здесь и сейчас
Ну конечно, не рационально каждый раз писать всё с нуля. Есть готовые библиотеки, в том числе с открытыми исходниками. Можно посмотреть, оценить удобство api и качество кода, выбрать подходящее решение.
30 авг 19, 08:45    [21960251]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 42946
Геннадий любит лично все обследовать.
30 авг 19, 11:19    [21960385]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
mayton
Геннадий любит лично все обследовать.
Кому-то надо обследовать процесс вычислений
для лучшего понимания этого процесса.

Может быть, что-то и найдётся...
30 авг 19, 12:35    [21960478]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Barlone
Member

Откуда:
Сообщений: 1348
Gennadiy Usov
mayton
Геннадий любит лично все обследовать.
Кому-то надо обследовать процесс вычислений
для лучшего понимания этого процесса.

Может быть, что-то и найдётся...
Я уже говорил, 21958576 что "для понимания" надо смотреть на всю матрицу - каждое начальное значение во всех степенях, а не на результаты взятого с потолка кривого недотеста.
30 авг 19, 12:47    [21960489]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

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

А можно посмотреть на отдельные столбцы матрицы. Найти логику и выработать эвристическое решение
(с проверкой на деление на сколько хватит мощности компьютера).

А насчет "кривого недотеста"? Кажется, это похвала в квадрате.
30 авг 19, 13:25    [21960519]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
Зашел в вики на https://ru.wikipedia.org/wiki/ - криптографический алгоритм RSA.
Для этого алгоритма требуются случайные простые числа.
Ищу https://ru.wikipedia.org/wiki/ , где указывается количество раундов k для теста Миллера–Рабина при поиске простых случайных чисел :
k – количество битов в двоичной записи проверяемого числа n.
С другой стороны, в тесте Миллера–Рабина количество раундов оговаривается log (n).

Так какое количество раундов выбрать?
31 авг 19, 11:44    [21961058]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
Решил проверить с помощью простенькой программы на Питоне:
iimport math
x = pow(2, 1024)
y = math.log( x )
print y
Получилось
709.782712893

И 1024 и 709 - числа большие.

А если уменьшить количество раундов в 2, 3, 4 раза?
31 авг 19, 12:48    [21961079]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 42946
Усов. У меня идея появилась.

Есть формула которая оценивает количество простых на интервале от 2 до n. Разумеется приближенная.
От нее легко перейти к любому интервалу.

Далее можно методом Монте Карло оценить как сильно Рабин Миллер отклоняется от оценочной величины простых. И добавить разные эксперименты с разным числом раундов. 1,2,4,8...etc
31 авг 19, 13:00    [21961088]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
mayton
Усов. У меня идея появилась.
Есть формула которая оценивает количество простых на интервале от 2 до n. Разумеется приближенная.
От нее легко перейти к любому интервалу.
Далее можно методом Монте Карло оценить как сильно Рабин Миллер отклоняется от оценочной величины простых. И добавить разные эксперименты с разным числом раундов. 1,2,4,8...etc
Монте-Карло - это случайность, вероятность.
Конечно, можно оценить с помощью перебора случайных чисел любой процесс, но это будет вероятностное определение.

Я же хочу иметь достаточный тест на определение простых чисел.
Пусть это будут не все простые числа, а, например, половина всех простых чисел (подмножество простых чисел).
31 авг 19, 13:21    [21961108]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 48659
Gennadiy Usov
Я же хочу иметь достаточный тест на определение простых чисел.

К слову "достаточный" требуется уточнение "для чего".
31 авг 19, 13:39    [21961112]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
Dimitry Sibiryakov
Gennadiy Usov
Я же хочу иметь достаточный тест на определение простых чисел.
К слову "достаточный" требуется уточнение "для чего".
Рассмотрим небольшую задачу.

Надо найти несколько случайных чисел из серии 2^1024 (или 2^2048), допустим для RSA.

Для "исследования" каждого случайного числа требуется около 1000 (2000) раундов теста Миллера–Рабина.

Пусть имеется подмножество простых чисел, которые определяются с помощью 100 раундов теста Миллера–Рабина (а может быть и меньше). Причем, числа этого подмножества имеют достаточное условие для простых чисел. Количество элементов в подмножестве в 2 раза меньше, чем количество простых чисел (для определённого N рассматриваемых чисел).

Элементы подмножества встречаются реже, чем элементы множества, но зато за определённый промежуток времени можно проверить в несколько раз больше чисел.

Главное, мы получаем не псевдопростые числа, а простые числа.
31 авг 19, 13:55    [21961117]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 42946
Gennadiy Usov
Надо найти несколько случайных чисел из серии 2^1024 (или 2^2048), допустим для RSA.

Для "исследования" каждого случайного числа требуется около 1000 (2000) раундов теста Миллера–Рабина.

Почему 2000 ?
31 авг 19, 15:57    [21961176]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1842
mayton
Gennadiy Usov
Надо найти несколько случайных чисел из серии 2^1024 (или 2^2048), допустим для RSA.
Для "исследования" каждого случайного числа требуется около 1000 (2000) раундов теста Миллера–Рабина.
Почему 2000 ?
В вики записано про случайные простые числа для RSA:

"В криптографии под случайным простым числом понимается простое число, содержащее в двоичной записи заданное количество битов k...
...
Выполнить тест Миллера — Рабина с количеством раундов не меньше k.".

У нас либо 1024, либо 2048
31 авг 19, 16:10    [21961179]     Ответить | Цитировать Сообщить модератору
 Re: Ещё раз о тесте Ферма  [new]
mayton
Member

Откуда: loopback
Сообщений: 42946
Gennadiy Usov, будет детерминизм?
31 авг 19, 16:44    [21961192]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 .. 3 4 5 6 7 8 9 10 [11] 12   вперед  Ctrl      все
Все форумы / Программирование Ответить