P(простые)

У меня есть (ОЧЕНЬ БЫСТРЫЙ) метод при помощи которого можно со 100 % уверенностью сказать простое Р или нет.

Насколько мне известно (а мне кое-что известно), на сегодня нет ни одного способа, дающего ответ, является ли случайное p простым, а не составным, с вероятностью, равной единице. (Это не то же самое, что взаимная простота двух чисел. Она стопроцентно определяется по алгоритму старика Евклида.) В современных прикладных криптосистемах применяется ряд статистических тестов и алгоритмов, позволяющих "отловить" составное число, но всё равно остаётся небольшой шанс, что итоговый результат не будет простым. Степень вероятности зависит только от избыточности проверки.

Однако то, о чём говорите Вы, вообще не имеет отношения к простым числам. Простое число — это число, делящееся без остатка только на себя и на 1. Это значит, что у него нет других делителей. Но это НЕ значит, что оно обязательно должно быть чётным. Число 15 составное, но ни на 2, ни на 4 вы его не разделите. Как и число 17, являющееся простым.

Теперь по поставленным вопросам.

1. Так или иначе, ответ на вопрос, является ли конкретное p простым, ничего вам не даст для взлома асимметричного ключа. Простые p и q, используемые для формирования модуля m, после генерации ключа не подлежат компрометации. Чтобы взломать ключ, вам нужно узнать из каких p и q составлено m. На этом и основана надёжность RSA.

2. То есть числа каких порядков используются для формирования ключа? Примерно от тех самых 2^1000. И выше.

SATtva:
Однако то, о чём говорите Вы, вообще не имеет отношения к простым числам. Простое число — это число, делящееся без остатка только на себя и на 1. Это значит, что у него нет других делителей. Но это НЕ значит, что оно обязательно должно быть чётным. Число 15 составное, но ни на 2, ни на 4 вы его не разделите. Как и число 17, являющееся простым.

Помоему деление на два приведено только для оценки времени работы алгоритма, но само по себе деление именно на 2 тут не при чем.

Насколько мне известно (а мне кое-что известно), на сегодня нет ни одного способа, дающего ответ, является ли случайное p простым, а не составным, с вероятностью, равной единице.

А мне известен такой способ. Называется "решето Эратосфена".

А если вас не устраивает скорость, то можно применить алгоритм с полиномиальной сложностью, открытый в прошлом году индийцами (имён, увы, не помню, но дома у меня распечатка лежит).

1. Так или иначе, ответ на вопрос, является ли конкретное p простым, ничего вам не даст для взлома асимметричного ключа. Простые p и q, используемые для формирования модуля m, после генерации ключа не подлежат компрометации. Чтобы взломать ключ, вам нужно узнать из каких p и q составлено m. На этом и основана надёжность RSA.

Прошу прощение за долгое отсутствие
Если возможно то тут по подробнее как простые p и q, используются для формирования модуля m.
Что их перемножают или что с ними делают???
И Wizzard прав пример 2^1000 был приведен только для оценки времени работы алгоритма.

Что их перемножают или что с ними делают???

Перемножают и сразу отбрасывают (уничтожают). Краткое описание RSA здесь.

можно применить алгоритм с полиномиальной сложностью, открытый в прошлом году индийцами (имён, увы, не помню, но дома у меня распечатка лежит).

Manindra Agrawal, Neeraj Kayal, and Nitin Saxena: http://en.wikipedia.org/wiki/AKS_primality_test Btw, комментарий от 2004го года?! И уже тогда об этом здесь знали? Да-а-а, теперь pgpru уже не тот :-(

Да! Я то думал хоть SATtva чего-то соображает, а оказывается он тоже малограмотный.
Уважаемый SATtva, если алгоритм не используется в современной криптографии, то это не означает, что его нет! Детерминированных алгоритмов определения простоты больше, чем вероятностных. Ну, например, рассчет порядка элемента в циклической группе. Правда для осуществления такого теста надо кое-что разложить на множители, а это долго и неудобно (по меркам соременных реализаций). Вот и пользуются алгоритмами основанными на малой теореме Ферма (например Миллера-Рабина). Кстати из справедливости расширенной гипотезы Римана (пока не доказанной) следует, что алгорим Миллера-Рабина становится тоже детерминированным при условии проведения проверок до определенной границы.

Не стыдно чего-то не знать, стыдно — не хотеть учиться. ;-)

Специалисту по ИБ вполне простительно не знать последних достижений сугубо теоретической теории чисел, так же как математику – последних достижений во всяких cold boot атаках, так что к чему этот ваш троллинг? Btw, я не уверен, что детерминистичные алгоритмы быстрее вероятностных для больших чисел: в частности, какие алгоритмы используются при генерации ключей в том же GnuPG? В современной литературе про AKS пишут сносками – это ещё не перекочевало в традиционные учебники и монографии:

Первое серьёзное возражение против сильного тезиса Чёрча-Тьюринга появилось в середине 70-х гг., когда Роберт Солвей и Волкер Штрассен показали, что проверить, является ли целое число простым или составным, можно с помощью вероятностного алгоритма. В тесте Соловея-Штрассена случайность использовалась как существенная часть алгоритма. Алгоритм не давал достоверного ответа на вопрос, является ли данное целое число простым или составным, определяя это лишь с некоторой вероятностью. Повторяя тест Соловея-Штрассена несколько раз, можно определить это почти наверняка. Нужно особо отметить, что во время появления теста Соловея-Штрассена не было известно какого-либо эффективного детерминированного алгоритма для проверки целых чисел на простоту (такой алгоритм появился в июле 2002г. – Прим. ред.). Получалось, что компьютеры, имеющие доступ к генератору случайных чисел, могли эффективно выполнять вычислительные задачи, для которых не было эффективного решения на традиционной детерминированной машине Тьюринга. Это открытие послужило толчком к поиску других вероятностных алгоритмов, который полностью оправдал себя, приведя к созданию успешно развивающейся области исследований.

Нильсон & Чанг, переводное издание, 2006, стр. 24.

[offtop]

Я то думал хоть SATtva чего-то соображает, а оказывается он тоже малограмотный.

Грамотный, вы, наверно, уже сдали матминиум, прежде чем сеть в судейское место? :-)
[/offtop]

[offtop]

Я то думал хоть SATtva чего-то соображает, а оказывается он тоже малограмотный.

Вообще-то противопоставлять сообразительность и малограмотность не совсем грамотно :)
[/offtop]