powered by simpleCommunicator - 2.0.49     © 2025 Programmizd 02
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Ещё раз о тесте Ферма
25 сообщений из 283, страница 11 из 12
Ещё раз о тесте Ферма
    #39854930
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovmaytonЕсли ты просто опубликуешь работающий
код на Питоне то ты имеешь шанс получить ответ на твой вопрос.Для сообщения 21959038 и 21959044 была сделана очень простенькая программа на Питоне:
Код: python
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
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) надо еще
Код: plaintext
1.
2.
z = 0
while z < s and x != 1 and x != p-1
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39854931
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
x = x*x % p
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39854932
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Недописанное ушло, 2 раза
Код: plaintext
1.
2.
3.
4.
z = 0
while z < s and x != 1 and x != p-1
   x = x*x % p 
   z = z + 1
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39855147
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
BarloneКод недоделанный.
После x = pow(y1, t1, p) надо еще
Код: plaintext
1.
2.
3.
4.
z = 0
while z < s and x != 1 and x != p-1
   x = x*x % p 
   z = z + 1
Это второе условие теста Миллера-Рабина?

В коде 21959374 я рассматривал только первое условие теста.
Этот код необходим для оценки показаний остатков по модулю после применения различных случайных чисел.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39855160
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovА как они пишут новую программу?
Подавляющее большинство делает это копипастом с гугля.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39855223
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovЭто второе условие теста Миллера-Рабина?

В коде 21959374 я рассматривал только первое условие теста.
Ну тогда у вас не тест Миллера-Рабина, а неведомая хрень.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39855251
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
BarloneGennadiy UsovЭто второе условие теста Миллера-Рабина?
В коде 21959374 я рассматривал только первое условие теста.
Ну тогда у вас не тест Миллера-Рабина, а неведомая хрень.Как в том анекдоте:
хрень, не хрень, а работает.

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

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

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

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

Была составлена программа, были получены результаты, в сообщении 21958523 показаны основные выводы,
а в сообщении 21959374 показан код такой программы на Питоне.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39855256
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Dimitry SibiryakovGennadiy UsovА как они пишут новую программу?Подавляющее большинство делает это копипастом с гугля.То есть, основополагающие алгоритмы никто не читает?

Была такая игра: каждый в цепочке на ухо сообщает другому в цепочке слово, и какое слово пролучается в конце цепочки.
Или что-то похожее...
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39855370
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Основные алгоритмы описаны в Википедии.

Но этот форум обычно обсуждает их реализации на конкретных языках и конфигурациях.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39855401
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovDimitry Sibiryakovпропущено...
Подавляющее большинство делает это копипастом с гугля.То есть, основополагающие алгоритмы никто не читает?очень редко кто, подавляющему большинству просто некогда, индустрия требует здесь и сейчас
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39855430
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry SibiryakovGennadiy UsovА как они пишут новую программу?
Подавляющее большинство делает это копипастом с гугля.Некоторые тут и даже и копипаст не могут.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39855434
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
kealon(Ruslan)очень редко кто, подавляющему большинству просто некогда, индустрия требует здесь и сейчасНу конечно, не рационально каждый раз писать всё с нуля. Есть готовые библиотеки, в том числе с открытыми исходниками. Можно посмотреть, оценить удобство api и качество кода, выбрать подходящее решение.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39855535
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Геннадий любит лично все обследовать.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39855606
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonГеннадий любит лично все обследовать. Кому-то надо обследовать процесс вычислений
для лучшего понимания этого процесса.

Может быть, что-то и найдётся...
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39855614
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovmaytonГеннадий любит лично все обследовать. Кому-то надо обследовать процесс вычислений
для лучшего понимания этого процесса.

Может быть, что-то и найдётся...Я уже говорил, 21958576 что "для понимания" надо смотреть на всю матрицу - каждое начальное значение во всех степенях, а не на результаты взятого с потолка кривого недотеста.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39855636
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
BarloneGennadiy Usov Кому-то надо обследовать процесс вычислений
для лучшего понимания этого процесса.
Может быть, что-то и найдётся...Я уже говорил, 21958576 что "для понимания" надо смотреть на всю матрицу - каждое начальное значение во всех степенях, а не на результаты взятого с потолка кривого недотеста.И что увидели на всей матрице? Жду ответа.

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

А насчет "кривого недотеста"? Кажется, это похвала в квадрате.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39855935
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Зашел в вики на https://ru.wikipedia.org/wiki/ - криптографический алгоритм RSA.
Для этого алгоритма требуются случайные простые числа.
Ищу https://ru.wikipedia.org/wiki/ , где указывается количество раундов k для теста Миллера–Рабина при поиске простых случайных чисел :
k – количество битов в двоичной записи проверяемого числа n.
С другой стороны, в тесте Миллера–Рабина количество раундов оговаривается log (n).

Так какое количество раундов выбрать?
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39855950
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Решил проверить с помощью простенькой программы на Питоне:
Код: python
1.
2.
3.
4.
iimport math
x = pow(2, 1024)
y = math.log( x )
print y

Получилось
709.782712893

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

А если уменьшить количество раундов в 2, 3, 4 раза?
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39855955
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Усов. У меня идея появилась.

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

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

Я же хочу иметь достаточный тест на определение простых чисел.
Пусть это будут не все простые числа, а, например, половина всех простых чисел (подмножество простых чисел).
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39855961
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovЯ же хочу иметь достаточный тест на определение простых чисел.
К слову "достаточный" требуется уточнение "для чего".
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39855962
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Dimitry SibiryakovGennadiy UsovЯ же хочу иметь достаточный тест на определение простых чисел.К слову "достаточный" требуется уточнение "для чего".Рассмотрим небольшую задачу.

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

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

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

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

Главное, мы получаем не псевдопростые числа, а простые числа.
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39855972
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovНадо найти несколько случайных чисел из серии 2^1024 (или 2^2048), допустим для RSA.

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

Почему 2000 ?
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39855975
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonGennadiy UsovНадо найти несколько случайных чисел из серии 2^1024 (или 2^2048), допустим для RSA.
Для "исследования" каждого случайного числа требуется около 1000 (2000) раундов теста Миллера–Рабина.Почему 2000 ?В вики записано про случайные простые числа для RSA:

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

У нас либо 1024, либо 2048
...
Рейтинг: 0 / 0
Ещё раз о тесте Ферма
    #39855981
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy Usov, будет детерминизм?
...
Рейтинг: 0 / 0
25 сообщений из 283, страница 11 из 12
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Ещё раз о тесте Ферма
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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