Ещё раз о тесте Ферма / Страница 11 / Программирование / Sql.ru

Добро пожаловать в форум, 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
Кому-то надо обследовать процесс вычислений для лучшего понимания этого процесса. Может быть, что-то и найдётся...

И что увидели на всей матрице? Жду ответа.

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

А насчет "кривого недотеста"? Кажется, это похвала в квадрате.

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→ все

Все форумы / Программирование

Ссылка на сообщение

Ссылка (включая название темы)

Ссылка (URL)