Client is expected to check whether p is a safe 2048-bit prime (meaning that both p and (p-1)/2 are prime, and that 2^2047 < p < 2^2048), and that g generates a cyclic subgroup of prime order (p-1)/2, i.e. is a quadratic residue mod p. Since g is always equal to 2, 3, 4, 5, 6 or 7, this is easily
Правда «i.e. is a quadratic residue mod p» зря дописали, т.к. 0 тоже квадратичный вычет :)
А то, что на клиенте недростаточные проверки — плохо, напишите им.
Вот тут собраны ссылки + короткие описания на 101 доказательство про P ?= NP, там есть доказательства и равенства, и неравенства, и даже недоказуемости.
После привыкания к множественному выделению в sublime, в других редакторах/IDE просто дико раздражает его отсутствие. Вроде небольшая фишка, но без неё жить никак
Неразрешимость будет, если память бесконечна. Понятное дело, перебирать все состояния памяти не вариант. Но ведь и выделять много памяти для этих предикатов в программу вряд ли захочется. Получается, что неразрешимость тут вообще никаким боком не стоит.
Что более важно, если выбирать произвольный предикат (будь то 3SAT-формула или предикат из любой другой NP-полной задачи), нет никаких гарантий, что данный экземпляр будет сложно решить. Я уверен, что подавляющее большинство случайных предикатов решается на ура. Выше уже писали, что те же 3SAT-формулы (особенно случайные) отлично решаются для достаточно больших размеров.
Я бы предложил попробовать использовать известные считающиеся сложными задачи — например взять какой-нибудь криптографический хэш и его код размазать (т.е. размазать проверку вида sha1(x) = y). Навскидку сложности: придумать, как замаскировать константы хэша; как сделать, чтобы все раунды хэширования выглядели по разному; плюс размер кода может получиться слишком большим для маленькой программы — а что если надо еще и несколько предикатов? (хотя можно попытаться использовать результаты одного и того же хэша).
А при переборе k не нужно ли проверять что r = g^k (mod p) (mod q)? А то получается, из первой пары нашли x, k для второй пары вычисляется через x. Получается для каждого x есть пара.
А если так, тогда достаточно для одного ключа найти такое k, чтобы r = g^k (mod p) (mod q) (и если таких будет несколько, можно проверить уже на второй паре).
Последовательность порождает только P, Q — просто преобразование на выходе.
Гарантий нету, и никто их дать не может. Но вероятность того, что породится последовательность с коротким циклом — крайне мала.
Q в любом случае зависит от P, Q=yP, как и P=xQ (потому что порядок группы простой). Определить состояние из выхода можно только дискретным логарифмом. Либо вычислить r=log(rQ, Q) и тогда rP=s', либо x=log(P, Q) и тогда xrQ = rP = s'.
Шанс выбрать случайно такие P и Q, что они окажутся «рядом» и дискретный логарифм легко возьмется, крайне маловероятен.
Правда «i.e. is a quadratic residue mod p» зря дописали, т.к. 0 тоже квадратичный вычет :)
А то, что на клиенте недростаточные проверки — плохо, напишите им.
Что выведет?
PS минус к IDE — тормознутость
Что более важно, если выбирать произвольный предикат (будь то 3SAT-формула или предикат из любой другой NP-полной задачи), нет никаких гарантий, что данный экземпляр будет сложно решить. Я уверен, что подавляющее большинство случайных предикатов решается на ура. Выше уже писали, что те же 3SAT-формулы (особенно случайные) отлично решаются для достаточно больших размеров.
Я бы предложил попробовать использовать известные считающиеся сложными задачи — например взять какой-нибудь криптографический хэш и его код размазать (т.е. размазать проверку вида sha1(x) = y). Навскидку сложности: придумать, как замаскировать константы хэша; как сделать, чтобы все раунды хэширования выглядели по разному; плюс размер кода может получиться слишком большим для маленькой программы — а что если надо еще и несколько предикатов? (хотя можно попытаться использовать результаты одного и того же хэша).
А если так, тогда достаточно для одного ключа найти такое k, чтобы r = g^k (mod p) (mod q) (и если таких будет несколько, можно проверить уже на второй паре).
Гарантий нету, и никто их дать не может. Но вероятность того, что породится последовательность с коротким циклом — крайне мала.
Шанс выбрать случайно такие P и Q, что они окажутся «рядом» и дискретный логарифм легко возьмется, крайне маловероятен.