$300 вознаграждение- вроде это дискретная математика

[RomanS]

Задача

1. Боб знает пару простых чисел, $x_1,x_2$
2. Алиса знает пару простых чисел, $y_1,y_2$
3. Как Бобу проверить истинность выражения $f(x_1,y_1) \mod 53 == f(x_2,y_2) \mod 53$ с вероятностью $v$ при том, что никто из них не должен узнать пары чисел друг друга, а также значение выражений $f(x_1,y_1) \mod 53$ и $f(x_2,y_2) \mod 53$. Т.е. подобрать функцию $f$, а также протокол проверки.

Примечание:
Под "не должен узнать" подразумевается невозможность узнать за приемлемое время при том, что проверка истинности выражения должна выполняться за приемлемое время. Иными словами сложность алгоритма "узнавания" должна быть экспоненциальная, а сложность алгоритма сравнения - полиноминальная.

Идеи:
В качестве гипотетической надежды на возможность такой схемы послужило наличие схемы Шнорра (http://ru.wikipedia.org/wiki/%D0%A1%D1% ... 1%80%D0%B0). Т.е. направление, куда следует копать, это свойства простых чисел, а также сложность задачи факторизации произведения двух больших простых чисел, сложность вычисления дискретного логарифма при меньшей сложности задачи вычисления $a = b^c \mod n$

skype: easy88easy88

[provincialka]

Когда предлагают вознаграждение - это сильно подозрительно.

[RomanS]

ну могу не предлагать - и что тут может быть подозрительного ?

[provincialka]

Что вам надо сдавать работу (диплом, скажем) и вы хотите его купить.
Если же предлагаете совместную работу - другое дело.

[whitefox]

RomanS в сообщении #765298 писал(а):

ну могу не предлагать - и что тут может быть подозрительного ?

Подозрительно, что не заплатите

Уж больно модуль (53) маленький.
И что означает N?

[RomanS]

предлагаю совместную работу - это не диплом
нужен специалист математик -

могу перевести аванс на администратора форума... если будет решение получите оплату у своего гаранта
тут на форуме я новичек

[Aritaborian]

RomanS в сообщении #765303 писал(а):

тут на форуме я новичек

Оно и видно (аж по трём четырём пяти признакам). К сожалению, вы пришли не туда. Здесь помогают each other бесплатно, но при условии, что тот, кто просит помощи, сам готов работать.

[whitefox]

Коли Вы новичок, даю бесплатный совет
Начинайте изучать $\TeX$, ибо очень скоро Ваша тема уедет в Карантин.

[RomanS]

Aritaborian в сообщении #765305 писал(а):

RomanS в сообщении #765303 писал(а):

тут на форуме я новичек

Оно и видно (аж по трём четырём признакам). К сожалению, вы пришли не туда. Здесь помогают each other бесплатно, но при условии, что тот, кто просит помощи, сам готов работать.

согласен на бесплатную помощь и я сам готов работать

просто лучше ресурса по математике не нашел . с живым форумом как тут

[Aritaborian]

RomanS в сообщении #765307 писал(а):

я сам готов работать

Так начинайте! Какие есть идеи?

[whitefox]

Ну раз сами согласны работать, то начните с того, что приведите все свои формулы в соответствие с правилами форума то есть в $\TeX$
http://dxdy.ru/topic8355.html
http://dxdy.ru/topic183.html

[RomanS]

whitefox в сообщении #765309 писал(а):

Ну раз сами согласны работать, то начните с того, что приведите все свои формулы в соответствие с правилами форума то есть в $\TeX$
http://dxdy.ru/topic8355.html
http://dxdy.ru/topic183.html

хорошо сеичас разберусь и исправлю

[Deggial]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
Причина переноса: формулы не оформлены $\TeX$ом

RomanS, наберите все формулы и термы $\TeX$ом. Инструкции по оформлению формул здесь или здесь (или в этом видеоролике).
После исправлений сообщите в теме Сообщение в карантине исправлено, и тогда тема будет возвращена.

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»
вернул

[whitefox]

RomanS

(Оффтоп)

Для бинарной операции $\mod$ лучше использовать код

\bmod

http://dxdy.ru/post443191.html#p443191
Например,

f(x_1,y_1)\bmod 53=f(x_2,y_2)\bmod 53 или a=b^c\bmod n

$f(x_1,y_1)\bmod 53=f(x_2,y_2)\bmod 53$ или $a = b^c \bmod n$

В порядке занудства ещё один вопрос -- Вы избегаете прописных букв по религиозным идеологическим убеждениям?

Поймите правильно, я не против, но точка посреди потока строчных букв обескураживает

RomanS в сообщении #765307 писал(а):

просто лучше ресурса по математике не нашел . с живым форумом как тут

Приходится затрачивать несколько лишних наносекунд на понимание того, что это конец предложения.

Вы настаиваете на модуле 53?
Не помешает ли такой маленький модуль криптостойкости протокола?

[RomanS]

whitefox в сообщении #765476 писал(а):

RomanS

(Оффтоп)

Для бинарной операции $\mod$ лучше использовать код

\bmod

http://dxdy.ru/post443191.html#p443191
Например,

f(x_1,y_1)\bmod 53=f(x_2,y_2)\bmod 53 или a=b^c\bmod n

$f(x_1,y_1)\bmod 53=f(x_2,y_2)\bmod 53$ или $a = b^c \bmod n$

В порядке занудства ещё один вопрос -- Вы избегаете прописных букв по религиозным идеологическим убеждениям?

Поймите правильно, я не против, но точка посреди потока строчных букв обескураживает

RomanS в сообщении #765307 писал(а):

просто лучше ресурса по математике не нашел . с живым форумом как тут

Приходится затрачивать несколько лишних наносекунд на понимание того, что это конец предложения.

Вы настаиваете на модуле 53?
Не помешает ли такой маленький модуль криптостойкости протокола?

Модуль 53 - обязательное условие. Это константа. Криптостойкость должна оставаться на приемлемом уровне, несмотря на это условие. Точнее она должна зависеть от разрядности чисел $x_1,x_2,x_3,x_4$.

Также решением может являться доказательство невозможности подобного.