Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
|
Поясни 06.10.08 22:34 Число просмотров: 4887
Автор: amirul <Serge> Статус: The Elderman
|
> Поскольку не гарантировано получение нового простого числа
> по формуле N=SR+1, то возможно ли что генерилка
> "зациклится"?
Что за формула?
> Зависит ли вероятность "зацикливания" от исходного простого
> числа?
> Можно ли выбирать R не из диапазона S <= R<= 4S+2, а
> хотя бы меньше S? Чем это черевато?Гарантирует ли это то,
> что заново сгенеренное число заведомо не будет простым?
> Кто-нибудь сталкивался с решением подобных проблем? Есть ли
> опыт?
Вроде простые числа во всех RSA-сотоварищи реализациях генерятся просто случайным поиском с вероятностной проверкой на простоту.
|
|
<theory>
|
Возможно ли "зацикливание" при генерации простых чисел? 06.10.08 17:23
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
|
Поскольку не гарантировано получение нового простого числа по формуле N=SR+1, то возможно ли что генерилка "зациклится"?
Зависит ли вероятность "зацикливания" от исходного простого числа?
Можно ли выбирать R не из диапазона S <= R<= 4S+2, а хотя бы меньше S? Чем это черевато?Гарантирует ли это то, что заново сгенеренное число заведомо не будет простым?
Кто-нибудь сталкивался с решением подобных проблем? Есть ли опыт?
|
|
Поясни 06.10.08 22:34
Автор: amirul <Serge> Статус: The Elderman
|
> Поскольку не гарантировано получение нового простого числа
> по формуле N=SR+1, то возможно ли что генерилка
> "зациклится"?
Что за формула?
> Зависит ли вероятность "зацикливания" от исходного простого
> числа?
> Можно ли выбирать R не из диапазона S <= R<= 4S+2, а
> хотя бы меньше S? Чем это черевато?Гарантирует ли это то,
> что заново сгенеренное число заведомо не будет простым?
> Кто-нибудь сталкивался с решением подобных проблем? Есть ли
> опыт?
Вроде простые числа во всех RSA-сотоварищи реализациях генерятся просто случайным поиском с вероятностной проверкой на простоту.
|
| |
А я в поисковике набрал "генерация больших простых чисел",... 07.10.08 11:28
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
|
> > по формуле N=SR+1, то возможно ли что генерилка
> > "зациклится"?
>
> Что за формула?
А я в поисковике набрал "генерация больших простых чисел", там почти везде присутствуют именно такие обозначения.
Я даже ссылку к сообщению цеплял, только что-то она не прицепилась. Фраза оттуда: "Таким образом, в настоящее время никаких теоретических гарантий для существования простого числа N=SR+1, S < R < 4S+2 не существует."
То есть метод вероятностный, можно искать очень долго, слишком долго, а то и вообще не найти. Про это что-то в статьях совсем ничего.
> Вроде простые числа во всех RSA-сотоварищи реализациях
> генерятся просто случайным поиском с вероятностной
> проверкой на простоту.
Точно. Только не совсем "просто случайным", а есть случайный с достаточно вероятным получением желаемого результата. Правда нигде не описана насколько вероятность выше, чем просто случайный поиск.
Суть его в том, что каждую итерацию получаем простое число примерно в двое большей разрядности, умножая его на случайное четное такого же порядка, что и очередное простое и добавляя единицу. Начинается все с простого, которое выбирается случайно из таблицы или генерится обычным способом - поиском/перебором.
Вот ссылка, где наиболее доступно написано.
|
| | |
Не будем мы "искать долго" [upd] 07.10.08 23:29
Автор: amirul <Serge> Статус: The Elderman
Отредактировано 07.10.08 23:49 Количество правок: 1
|
> А я в поисковике набрал "генерация больших простых чисел",
> там почти везде присутствуют именно такие обозначения.
> Я даже ссылку к сообщению цеплял, только что-то она не
> прицепилась. Фраза оттуда: "Таким образом, в настоящее
> время никаких теоретических гарантий для существования
> простого числа N=SR+1, S < R < 4S+2 не существует."
> То есть метод вероятностный, можно искать очень долго,
> слишком долго, а то и вообще не найти. Про это что-то в
> статьях совсем ничего.
Вероятность того, что ты не наткнешься случайным образом на простое число примерно равна вероятности того, что ты пройдешь minesweeper случайным образом открывая клетки
Расстояние между соседними простыми числами растет логарифмически. На число сотого порядка надо будет проверить примерно сотню чисел. По ссылке - nextprime через веб-интерфейс к GMP.
-------------------
Хотя в общем согласен, если есть алгоритм позволяющий сузить пространство поиска и искать еще быстрее, то почему бы им не воспользоваться. Что же до первоначального вопроса, то может я чего не понимаю, но я не вижу даже принципиальной возможности зацикливания.
http://gmplib.org/cgi-bin/gmp_calc.pl?expr=nextprime%281000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000%29
|
| | | |
Последовательный поиск, действительно не такой уж и... 12.12.08 15:04
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
|
> Расстояние между соседними простыми числами растет
> логарифмически. На число сотого порядка надо будет
> проверить примерно сотню чисел. По ссылке - nextprime
> через веб-интерфейс к GMP.
Последовательный поиск, действительно не такой уж и медленный. Итерраций побольше немного, зато сама итеррация быстрая.
Круто, за одну секунду они ищут nextprime для 333 значного числа это ж килобит примерно.
Вопросов появилось еще больше.
Как они умудряются за секунду сотни чисел протестировать. Все таки полноценный тест на простоту не так уж и быстр?
GMP только под Линукс или или попроще есть?
Может есть что попроще GMP?
Среди Линкус дистрибов что-нибудь изменилось? Что сейча поинтереснее и где его лучше взять?
(Спрашивал на рынке/развале - чуть не побили).
|
| | | | |
А они используют "неполноценный" :-) (тест Рабина-Миллера)... 12.12.08 21:20
Автор: amirul <Serge> Статус: The Elderman
|
> Как они умудряются за секунду сотни чисел протестировать.
> Все таки полноценный тест на простоту не так уж и быстр?
А они используют "неполноценный" :-) (тест Рабина-Миллера). Основан на малой теореме Ферма.
x^(n - 1) mod n = 1 для любого простого n
Если случайно выбирать x и проверять равенство, то можно с любой заданной вероятностью проверить является ли число простым. Собственно если тест дает ответ составное, то число 100% составное, если тест дает ответ простое, то число простое с некоторой вероятностью (чем больше разных x-ов проверено - тем выше вероятность). Для какого нибудь Mersenne Sieve это не подходит, а вот для практических задач вероятность порядка 2^-100 гораздо меньше, чем вероятность того, что детерминированный тест выдаст неправильный результат из-за случайного глюка, наведенного внешним излучением
http://en.wikipedia.org/wiki/Miller–Rabin_primality_test
> GMP только под Линукс или или попроще есть?
Нет не только. http://letmegooglethatforyou.com/?q=gmp+windows
http://fp.gladman.plus.com/computing/gmp4win.htm
> Может есть что попроще GMP?
Есть другие. Но GMP ни фига не сложный В ИСПОЛЬЗОВАНИИ, так что попроще - вряд ли.
> Среди Линкус дистрибов что-нибудь изменилось? Что сейча
> поинтереснее и где его лучше взять?
Неа. Все такой же отстой, который "скоро захватит мир". Взять - смотря чего тебе надо. Если просто поковыряться с минимумом проблем (совсем без проблем не получится, хаха) - бери убунту и не слушай слишком красноглазых. Если хочется "полного контроля над системой" - генту как раз для тебя (disclaimer: тебе нужен будет очень мощный компьютер, чтобы он собирал @$илды быстрее, чем выходят новые, а глаза твои покраснеют от постоянного недосыпа).
> (Спрашивал на рынке/развале - чуть не побили).
:-)
Даже так? Неужто сейчас за вопросы про leenooks уже бить начинают? Определенно прогресс.
|
| | | | | |
Этот тест я прикрасно знаю. Точнее не знаю другого (кроме... 13.12.08 22:36
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
Отредактировано 13.12.08 22:41 Количество правок: 2
|
> А они используют "неполноценный" :-) (тест Рабина-Миллера).
> Основан на малой теореме Ферма.
> x^(n - 1) mod n = 1 для любого простого n
Этот тест я прикрасно знаю. Точнее не знаю другого кроме этого (кроме перебора, естественно :-).
Под "неполноценностью" я имел в виду не то, что он вероятностный, а то, что количество проверок может быть больше или меньше. Это сильно влияет на скорость, а требуемая точность параметр эфимерный. Короче, можно проверить для двух-трех значений "х" и это уже будет какая-то кому-то достаточная точность. Где-то я читал, что количество проверок должно быть примерно равно двоичному логарифму. То есть тысяча для килобитного ключа, а это в тысячу раз медленнее. Кроме того рекомендовалось зачем-то первоначально проверить делимость на маленькие простые числа.
> http://en.wikipedia.org/wiki/Miller–Rabin_primality_test
Я читал русскоязычную версию. И что они там везде мудрят, написали бы просто "вычислить то-то столько-то раз для такой-то точности, что хватит выше крыши".
> > GMP только под Линукс или или попроще есть?
> Нет не только.
> http://letmegooglethatforyou.com/?q=gmp+windows
> http://fp.gladman.plus.com/computing/gmp4win.htm
Это хорошо. Хотя я про gcc под винду (даже дос) слышал, но до "ввода в эксплуатацию" не дошло.
Мне всего то нужен С++ с нормальной поддержной 32/64 разрядности и хотелось бы добраться до gmp. А то самому с реализацией базового уровня надоело ковыряться.
> Неа. Все такой же отстой, который "скоро захватит мир".
> Взять - смотря чего тебе надо. Если просто поковыряться с
> минимумом проблем (совсем без проблем не получится, хаха) -
> бери убунту и не слушай слишком красноглазых. Если хочется
> "полного контроля над системой" - генту как раз для тебя
> (disclaimer: тебе нужен будет очень мощный компьютер, чтобы
> он собирал @$илды быстрее, чем выходят новые, а глаза твои
> покраснеют от постоянного недосыпа).
Спасиб. Я что-то в последнее время отстал от жизни. Мне ничего собирать не надо. Главное что gcc работал.
> > (Спрашивал на рынке/развале - чуть не побили).
> :-)
> Даже так? Неужто сейчас за вопросы про leenooks уже бить
> начинают? Определенно прогресс.
Там 90% игрушек + 9% полезного софта (офис, фотошоп, 1С, базы, утилитки ...), сам виндовс. Думали, что я ругаюсь или их за дураков считаю, оскорбить хочу. Благо не за сам линукс.
|
| | | | | | |
Для чего тебе быстрая генерация простых чисел?... 14.12.08 00:01
Автор: amirul <Serge> Статус: The Elderman
|
> Под "неполноценностью" я имел в виду не то, что он
> вероятностный, а то, что количество проверок может быть
> больше или меньше. Это сильно влияет на скорость, а
Для чего тебе быстрая генерация простых чисел? Реально рабин-миллер дает приемлемый (и по скорости и по вероятности) результат на практически применимых длинах чисел.
> количество проверок должно быть примерно равно двоичному
> логарифму. То есть тысяча для килобитного ключа, а это в
Натуральному. Я уже давал ссылку на распределение простых чисел. Расстояние между ними растет логарифмически (натурально логарифмически :-) )
> тысячу раз медленнее. Кроме того рекомендовалось зачем-то
> первоначально проверить делимость на маленькие простые
> числа.
Не знаю, по моему в случае рабина миллера это бессмысленно. Один gcd - это как минимум десяток делений. При этом число уменьшится незначительно и не слишком повлияет на скорость дальнейшей проверки.
> Я читал русскоязычную версию. И что они там везде мудрят,
> написали бы просто "вычислить то-то столько-то раз для
> такой-то точности, что хватит выше крыши".
Категорически не согласен. Если выбирать между примитивной реализацией и фундаментальными сведениями - то лучше пусть будет фундамент, а реализацию я как нибудь сам. С другой стороны лучше чтобы было и то и то.
> Это хорошо. Хотя я про gcc под винду (даже дос) слышал, но
> до "ввода в эксплуатацию" не дошло.
А при чем здесь gcc? gmp под цигвином/мингвом можно собирать и без всяких дополнительных телодвижений. То что я дал - это gmp для visual studio.
> Мне всего то нужен С++ с нормальной поддержной 32/64
> разрядности и хотелось бы добраться до gmp. А то самому с
> реализацией базового уровня надоело ковыряться.
Ну и vc и gcc умеют 32/64. Я кстати, используя вышеприведенный линк собирал 64-битный gmp для вычисления 9^(9^9)
Прирост в скорости от перехода 32->64 не очень большой, но процентов 10-15 есть.
> Спасиб. Я что-то в последнее время отстал от жизни. Мне
> ничего собирать не надо. Главное что gcc работал.
Бери бубунту и не слушай пингвинофанатов.
> Благо не за сам линукс.
Жаль :-)
|
| | | | | | | |
Не, быстрая не нужна, нужна не медленная. 15.12.08 18:17
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
Отредактировано 15.12.08 18:19 Количество правок: 2
|
> Для чего тебе быстрая генерация простых
> чисел? Реально рабин-миллер дает приемлемый (и по скорости
> и по вероятности) результат на практически применимых
> длинах чисел.
Сейчас уж не вспомню, то ли полкило, то ли килобит за минуту - обидно, понимаешь, умеючи и за 1-10 сек двухкилобитный генерится. Причем у меня скорость падает примерно как квадрат от разрядности. В смысле в два раза больше разраядность, в четыре (а то и больше) раза дольше генерится.
> Натуральному. Я уже давал ссылку на распределение простых
> чисел. Расстояние между ними растет логарифмически
> (натурально логарифмически :-) )
Ну это приятнее - раза в полтора будет быстрее.
> > тысячу раз медленнее. Кроме того рекомендовалось
> зачем-то
> > первоначально проверить делимость на маленькие простые
> > числа.
> Не знаю, по моему в случае рабина миллера это бессмысленно.
> Один gcd - это как минимум десяток делений. При этом число
> уменьшится незначительно и не слишком повлияет на скорость
> дальнейшей проверки.
Меня это смутило. Причина моих сомнений проста - получается, что Миллера-Рабина без такой проверки полный бред выдаст, ошибится сможет, особенно, если делители маленькие. Потом решил, что это рекомендовалось сделать, чтоб отсеить заведомо составные (кратные 2, 3, 5, ...). В принципе тест М-Р может быть достаточно сложным, длинным и долгим, если "отлуп" наступит на одном из последних раундов. Если же взять произведение десятка-другого маленьких простых и найти с ним НОД, то после первого же деления (по Евклиду) получаем уже достаточно небольшое число. Поэтому не десяток, а несколько делений вместо немалого количества умножений может быть оправдано.
> Категорически не согласен. Если выбирать между примитивной
> реализацией и фундаментальными сведениями - то лучше пусть
> будет фундамент, а реализацию я как нибудь сам. С другой
> стороны лучше чтобы было и то и то.
Пусть будет и то и то. Порой бывает надо быстро реализовать, а тут попадается теория, да еще оборваная на полуслове, типа додумай сам, для повышения соображалки.
> А при чем здесь gcc? gmp под цигвином/мингвом можно
А это разве не надстройки над gcc?
> собирать и без всяких дополнительных телодвижений. То что я
> дал - это gmp для visual studio.
Да, видел, 6 версии достаточно.
> Ну и vc и gcc умеют 32/64. Я кстати, используя
> вышеприведенный линк собирал 64-битный gmp для вычисления
> 9^(9^9)
> Прирост в скорости от перехода 32->64 не очень большой,
> но процентов 10-15 есть.
Странно, должно быть раза в четыре. Я для совместимости реализовывал на 16 битах - отсюда думаю и тормоза. 32 уже, полагаю хватило бы, если в четыре раза скорость бы поднялась. Жалко бросать, делал для себя, на с++ класс с перегрузкой операций, удобнее, чем структуры в функции передавать.
> > Благо не за сам линукс.
> Жаль :-)
Как много в этом мире добрых людей!
|
| | | | | | | | |
Если тебе для RSA, то они генерятся несколько иначе :-) 15.12.08 19:59
Автор: amirul <Serge> Статус: The Elderman
|
> Сейчас уж не вспомню, то ли полкило, то ли килобит за
> минуту - обидно, понимаешь, умеючи и за 1-10 сек
> двухкилобитный генерится. Причем у меня скорость падает
> примерно как квадрат от разрядности. В смысле в два раза
> больше разраядность, в четыре (а то и больше) раза дольше
> генерится.
Если тебе для RSA, то они генерятся несколько иначе :-)
Там ведь еще куча условий, необходимых для стойкости ключа.
http://en.wikipedia.org/wiki/RSA#Key_generation_2
> Меня это смутило. Причина моих сомнений проста -
> получается, что Миллера-Рабина без такой проверки полный
> бред выдаст, ошибится сможет, особенно, если делители
Нет, от делителей результат теста вообще не зависит.
> маленькие. Потом решил, что это рекомендовалось сделать,
> чтоб отсеить заведомо составные (кратные 2, 3, 5, ...). В
> принципе тест М-Р может быть достаточно сложным, длинным и
> долгим, если "отлуп" наступит на одном из последних
Ага, я протормозил - только что понял, что там используется модулярная арифметика - то бишь деление на N на каждом раунде возведения в степень. Таки да - лучше сразу отсеять лишнее. А в случае с nextprime - так вообще за один вызов gcd отсеять ВСЕ лишние числа. Тут даже и большое (хотя бы 1000) количество маленьких простых можно использовать.
> деления (по Евклиду) получаем уже достаточно небольшое
> число. Поэтому не десяток, а несколько делений вместо
> немалого количества умножений может быть оправдано.
В случае с nextprime - еще как оправдано. Но не при наивной реализации (проверка делимости на малые простые при каждой проверке на простоту).
> > А при чем здесь gcc? gmp под цигвином/мингвом можно
> А это разве не надстройки над gcc?
Нет. Это и есть gcc, собранный под винду.
> > собирать и без всяких дополнительных телодвижений. То
> что я
> > дал - это gmp для visual studio.
> Да, видел, 6 версии достаточно.
6-й версии студии? Выкинь ее срочно. :-)
Она ж появилась даже раньше, чем стандарт C++ (а стандарт с тех пор еще пару рас апдейтился), да и баги никто не отменял. Хочешь лицензионной чистоты - бери vs express и не мучайся
> Странно, должно быть раза в четыре. Я для совместимости
Не, не должно
Теоретический максимум - 2 раза. Это если все что ты будешь делать - перемалывать лимбы (лимб увеличился в 2 раза - тебе придется делать в 2 раза меньше работы): у умножения на таких числах сложность почти линейная: O(n (log n) (log log n)), но кроме самой работы с лимбами есть еще и куча вспомогательной работы - отсюда и 15%.
> реализовывал на 16 битах - отсюда думаю и тормоза. 32 уже,
> полагаю хватило бы, если в четыре раза скорость бы
> поднялась. Жалко бросать, делал для себя, на с++ класс с
> перегрузкой операций, удобнее, чем структуры в функции
> передавать.
Ну дык
# include <gmpxx.h>
и вперед. Там в частности реализованы отложенные вычисления, то бишь
a += b * c;
скомпилится не в 2 (или не дай бог 3) вызова, а в один mpz_addmul
|
| | | |
Кстати, в рукипедии описан именно поиск типа nextprime от произвольного случайного числа 08.10.08 01:43
Автор: amirul <Serge> Статус: The Elderman
|
При этом ускорять предлагается просто не пытаясь проверять заведомо составные числа (указан пример про сравнимость с 1 и 5 по модулю 6), что в три раза сокращает количество чисел для тестирования, но можно и еще больше проредить количество вариантов по аналогии с решетом эратосфена, но только с базой не от нуля, а от большого случайного числа.
http://ru.wikipedia.org/wiki_#.D0.A2.D0.B8.D0.BF.D0.BE.D0.B2.D0.BE.D0.B9D0.B0.D0.BB.D0.B3.D0.BE.D1.80.D0.B8.D1.82.D0.BC_1
|
| | | | |
Ссылка что-то не открывается, какое название статьи? 08.10.08 11:25
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
Отредактировано 08.10.08 11:26 Количество правок: 1
|
> При этом ускорять предлагается просто не пытаясь проверять
> заведомо составные числа (указан пример про сравнимость с 1
> и 5 по модулю 6), что в три раза сокращает количество чисел
> для тестирования, но можно и еще больше проредить
> количество вариантов по аналогии с решетом эратосфена, но
> только с базой не от нуля, а от большого случайного числа.
Ссылка что-то не открывается, какое название статьи?
Что-то я не ожидал, что на расстоянии 10 в 100 степени простые так часто находятся друг от друга - порядка сотни.
В принципе и без стати можно ускориться. Действительно - решето от базы большого числа и раз в десять-двадцать меньше проверок.
Кажется я догадываюсь, почему "циклился" и долго искал. Скорее всего это не "долго", а бесконечно. Просто попадал в режим генерации заведомо составных. Надо проверить.
Спасибо.
|
| | | | | |
"Случайное простое число" [upd] 08.10.08 21:51
Автор: amirul <Serge> Статус: The Elderman
Отредактировано 08.10.08 22:43 Количество правок: 2
|
> Ссылка что-то не открывается, какое название статьи?
Там два типовых алгоритма. Первый - просто nextprime, а вместо второго ссылка на бумажный источник - хрен знает, что они хотели там написать.
> Что-то я не ожидал, что на расстоянии 10 в 100 степени
> простые так часто находятся друг от друга - порядка сотни.
Ну это в принципе следствие Prime Number Theorem
http://en.wikipedia.org/wiki/Prime_number_theorem
pi(x) ~ x/ln(x)
Где pi(x) - http://en.wikipedia.org/wiki/Prime-counting_function
> В принципе и без стати можно ускориться. Действительно -
> решето от базы большого числа и раз в десять-двадцать
> меньше проверок.
Ага, причем "накрыть" решетом надо всего лишь полтыщи-тыщу чисел.
> Кажется я догадываюсь, почему "циклился" и долго искал.
> Скорее всего это не "долго", а бесконечно. Просто попадал в
> режим генерации заведомо составных. Надо проверить.
> Спасибо.
-----------------------------
В рукипедии есть ссылка типовой алгоритм 2 в электронном виде. По всей видимости это тот же самый алгоритм, что используешь ты
|
| | | | | | |
ссылка на электронную книгу 09.10.08 22:22
Автор: RElf <M> Статус: Member
|
> > Ссылка что-то не открывается, какое название статьи?
>
> Там два типовых алгоритма. Первый - просто nextprime, а
> вместо второго ссылка на бумажный источник - хрен знает,
> что они хотели там написать.
Смотрите лучше - там ссылка на электронный вариант книги в конце статьи приводится.
Вот она: http://nature.web.ru/db/msg.html?mid=1157083&uri=node33.html
|
| | | | | | | |
Вы тоже внимательнее смотрите :-) 10.10.08 01:40
Автор: amirul <Serge> Статус: The Elderman
|
|
Апдейт о том, что ссылка нашлась у меня в конце сообщения
|
| | | | | | | | |
Сдается мне что это "зеркала" или перепечатки. Суть... 10.10.08 10:16
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
|
|
Сдается мне что это "зеркала" или перепечатки. Суть остается: наиболее эффективный метод при помощи модифицированной малой теоремы Ферма. Хотя я сомневаюсь, что это наиболее эффективный. При случае посчитаю сколько "тяжелых" проверок выполняется в обоих случаях.
|
|
|
подробно о проекте
Анализ криптографических сетевых...
