Добро пожаловать в форум, Guest >> Войти | Регистрация | Поиск | Правила | | В избранное | Подписаться | ||
Все форумы / Программирование |
![]() ![]() |
Топик располагается на нескольких страницах: ←Ctrl назад 1 .. 3 4 5 6 7 8 9 10 [11] 12 вперед Ctrl→ все |
Barlone Member Откуда: Сообщений: 1448 |
После x = pow(y1, t1, p) надо еще z = 0 |
||||
29 авг 19, 06:16 [21959501] Ответить | Цитировать Сообщить модератору |
Barlone Member Откуда: Сообщений: 1448 |
x = x*x % p |
29 авг 19, 06:17 [21959502] Ответить | Цитировать Сообщить модератору |
Barlone Member Откуда: Сообщений: 1448 |
Недописанное ушло, 2 раза
|
29 авг 19, 06:18 [21959503] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2275 |
В коде 21959374 я рассматривал только первое условие теста. Этот код необходим для оценки показаний остатков по модулю после применения различных случайных чисел. |
||
29 авг 19, 13:51 [21959832] Ответить | Цитировать Сообщить модератору |
Dimitry Sibiryakov Member Откуда: Сообщений: 52117 |
Подавляющее большинство делает это копипастом с гугля. |
||
29 авг 19, 14:06 [21959848] Ответить | Цитировать Сообщить модератору |
Barlone Member Откуда: Сообщений: 1448 |
|
||
29 авг 19, 15:18 [21959927] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2275 |
хрень, не хрень, а работает. Я просто спросил, а тут такие выводы... Я предупреждал, что в сообщении 21958523 рассматриваю только первое условие теста Миллера-Рабина, причем было оговорено: "какой перечень остатков выдаёт этот тест". Поскольку случайное число получается от 2 до (n - 2 ), то, естественно, было интересно: а что получится, если все случайные числа 2 до (n - 2 ) будут "применены". Таким образом, я посчитал все остатки по модулю при подстановке всех возможных случайных чисел для чисел от 5 до 115. Была составлена программа, были получены результаты, в сообщении 21958523 показаны основные выводы, а в сообщении 21959374 показан код такой программы на Питоне. |
||||
29 авг 19, 15:55 [21959963] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2275 |
Была такая игра: каждый в цепочке на ухо сообщает другому в цепочке слово, и какое слово пролучается в конце цепочки. Или что-то похожее... |
||||
29 авг 19, 16:00 [21959971] Ответить | Цитировать Сообщить модератору |
mayton Member Откуда: loopback Сообщений: 50489 |
Основные алгоритмы описаны в Википедии. Но этот форум обычно обсуждает их реализации на конкретных языках и конфигурациях. |
29 авг 19, 21:40 [21960154] Ответить | Цитировать Сообщить модератору |
kealon(Ruslan) Member Откуда: Нижневартовск Сообщений: 6228 |
|
||||
30 авг 19, 00:18 [21960200] Ответить | Цитировать Сообщить модератору |
Barlone Member Откуда: Сообщений: 1448 |
|
||||
30 авг 19, 08:34 [21960247] Ответить | Цитировать Сообщить модератору |
Barlone Member Откуда: Сообщений: 1448 |
|
||
30 авг 19, 08:45 [21960251] Ответить | Цитировать Сообщить модератору |
mayton Member Откуда: loopback Сообщений: 50489 |
Геннадий любит лично все обследовать. |
30 авг 19, 11:19 [21960385] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2275 |
для лучшего понимания этого процесса. Может быть, что-то и найдётся... |
||
30 авг 19, 12:35 [21960478] Ответить | Цитировать Сообщить модератору |
Barlone Member Откуда: Сообщений: 1448 |
|
||||
30 авг 19, 12:47 [21960489] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2275 |
А можно посмотреть на отдельные столбцы матрицы. Найти логику и выработать эвристическое решение (с проверкой на деление на сколько хватит мощности компьютера). А насчет "кривого недотеста"? Кажется, это похвала в квадрате. |
||||
30 авг 19, 13:25 [21960519] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2275 |
Зашел в вики на https://ru.wikipedia.org/wiki/ - криптографический алгоритм RSA. Для этого алгоритма требуются случайные простые числа. Ищу https://ru.wikipedia.org/wiki/ , где указывается количество раундов k для теста Миллера–Рабина при поиске простых случайных чисел : k – количество битов в двоичной записи проверяемого числа n. С другой стороны, в тесте Миллера–Рабина количество раундов оговаривается log (n). Так какое количество раундов выбрать? |
31 авг 19, 11:44 [21961058] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2275 |
Решил проверить с помощью простенькой программы на Питоне:iimport math x = pow(2, 1024) y = math.log( x ) print yПолучилось 709.782712893 И 1024 и 709 - числа большие. А если уменьшить количество раундов в 2, 3, 4 раза? |
31 авг 19, 12:48 [21961079] Ответить | Цитировать Сообщить модератору |
mayton Member Откуда: loopback Сообщений: 50489 |
Усов. У меня идея появилась. Есть формула которая оценивает количество простых на интервале от 2 до n. Разумеется приближенная. От нее легко перейти к любому интервалу. Далее можно методом Монте Карло оценить как сильно Рабин Миллер отклоняется от оценочной величины простых. И добавить разные эксперименты с разным числом раундов. 1,2,4,8...etc |
31 авг 19, 13:00 [21961088] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2275 |
Конечно, можно оценить с помощью перебора случайных чисел любой процесс, но это будет вероятностное определение. Я же хочу иметь достаточный тест на определение простых чисел. Пусть это будут не все простые числа, а, например, половина всех простых чисел (подмножество простых чисел). |
||
31 авг 19, 13:21 [21961108] Ответить | Цитировать Сообщить модератору |
Dimitry Sibiryakov Member Откуда: Сообщений: 52117 |
К слову "достаточный" требуется уточнение "для чего". |
||
31 авг 19, 13:39 [21961112] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2275 |
Надо найти несколько случайных чисел из серии 2^1024 (или 2^2048), допустим для RSA. Для "исследования" каждого случайного числа требуется около 1000 (2000) раундов теста Миллера–Рабина. Пусть имеется подмножество простых чисел, которые определяются с помощью 100 раундов теста Миллера–Рабина (а может быть и меньше). Причем, числа этого подмножества имеют достаточное условие для простых чисел. Количество элементов в подмножестве в 2 раза меньше, чем количество простых чисел (для определённого N рассматриваемых чисел). Элементы подмножества встречаются реже, чем элементы множества, но зато за определённый промежуток времени можно проверить в несколько раз больше чисел. Главное, мы получаем не псевдопростые числа, а простые числа. |
||||
31 авг 19, 13:55 [21961117] Ответить | Цитировать Сообщить модератору |
mayton Member Откуда: loopback Сообщений: 50489 |
Почему 2000 ? |
||
31 авг 19, 15:57 [21961176] Ответить | Цитировать Сообщить модератору |
Gennadiy Usov Member Откуда: Сообщений: 2275 |
"В криптографии под случайным простым числом понимается простое число, содержащее в двоичной записи заданное количество битов k... ... Выполнить тест Миллера — Рабина с количеством раундов не меньше k.". У нас либо 1024, либо 2048 |
||||
31 авг 19, 16:10 [21961179] Ответить | Цитировать Сообщить модератору |
mayton Member Откуда: loopback Сообщений: 50489 |
Gennadiy Usov, будет детерминизм? |
31 авг 19, 16:44 [21961192] Ответить | Цитировать Сообщить модератору |
Топик располагается на нескольких страницах: ←Ctrl назад 1 .. 3 4 5 6 7 8 9 10 [11] 12 вперед Ctrl→ все |
Все форумы / Программирование | ![]() |