Рейтинг:1

Существует ли общая формула для количества различных последовательностей, созданных с помощью $x\mapsto x^\alpha \mod N$?

флаг at

В зависимости от $\альфа,N,х$ последовательность $x\mapsto x^\alpha \mod N$ может иметь разную длину. Если первый элемент $x_0$ инициализируется с $x_0 = x_r^\alpha$ для случайного $x_r$ последовательность почти всегда будет иметь один и тот же постоянный размер.
Мы сосредоточимся здесь только на наиболее распространенных последовательностях с максимальным размером $N_L$ (для данного $\альфа,N$).

В зависимости от выбранного $x_0$ это может привести к различным непересекающимся последовательностям с тем же максимальным размером последовательности.


Вопрос: Есть ли какая-то общая формула для вычисления количества этих последовательностей (для заданного $\альфа,N$)?

Изменить: опубликованный и принятый ответ не ответил на этот вопрос, но был очень полезен.
Ответ на этот вопрос по-прежнему приветствуется. (окончание редактирования)


Пока возился, я уже нашел формулу для некоторых $N, \альфа$ особого строения. Длина цикла $\альфа$ по модулю некоторых простых множителей $\фи(N)$ а также факторы $\фи(\фи(N))$ кажется, имеют некоторое влияние на этот счет.
Это также связано с количеством различных значений $N_{\alpha}=|\{x^\alpha \bmod N\}|$ и максимальная длина этой последовательности $N_L$.

За $N_\альфа$ он получил ответ в другом нить. Если $N$ является произведением уникальных простых множителей: $$N = \prod_{i=1}^n p_i$$ Количество различных значений $N_\альфа$ было бы $$N_{\alpha} =\prod_{i=1}^n\left(1+\frac{p_i-1}{\mathrm{gcd}(\alpha,p_i-1)}\right)$$ За $N_L$ Я только составил некоторые уравнения, которые действительно работают для некоторых $N, \альфа$. Общая формула также приветствуется.
Оба вместе могут привести к приблизительному количеству последовательностей.

Побочный вопрос: есть ли у этих последовательностей особое имя? Это и другие свойства где-то описаны (в компактной форме)?


Цель $N$ также будет $2$,$3$ или же $4$ нечетные уникальные простые множители.

Рейтинг:2
флаг sa

Это очень сложно и нерешенной в общем математической задаче. Возможно, вам следует сфокусировать свой вопрос на конкретный случаев и, возможно, задайте их на mathoverflow, но всегда есть риск, что они могут быть проигнорированы, если вы не продемонстрируете предварительное исследование и не зададите хорошо продуманные вопросы.

Конкретный случай $N$ Prime рассматривал Игорь Шпарлинский. Лучше всего начать с поиска ссылок на его работы. Как поясняется в аннотации к упомянутой ниже статье, эта проблема тесно связана с другими задачами и приложениями теории чисел.

Чуа и Шпарлински, О структуре цикла повторного возведения в степень по простому модулю, Журнал теории чисел, том. 107 (2004), стр. 345–356.

Я мог получить доступ к копии через

Эльзевир здесь

Отметим, что некоторые результаты были получены в предположении, что обобщенная гипотеза Римана которую удалили Шпарлинский и его соавтор, уже одно это должно сказать вам, насколько сложна эта проблема в той общности, которую вы, кажется, хотите. В этой статье оцениваются некоторые моменты длины цикла и числа циклов.

Я полагаю, что вам может быть полезнее, если вы проведете дополнительные исследования и посмотрите, какие другие связанные результаты были получены в литературе, прежде чем снова задать связанный очень общий и математический вопрос здесь, на криптостековой бирже.

J. Doe avatar
флаг at
Спасибо за информацию и ссылку. Проблема заключается в том, что особый случай потенциальной цели зависит от длины и количества последовательности.Создание $\alpha,N$ для некоторых свойств действительно сработало. Объединять их не стал - почти уверен, что не получится в самом конце. Я искал некоторую ясность по этому поводу. Слишком длинные потоки, включающие все, что было сделано, также в большинстве случаев игнорируются. А на mathoverflow вам понадобится дополнительная порция удачи. Вы никогда не узнаете, является ли это неразрешимым/сложным или просто нет ответа.
J. Doe avatar
флаг at
Эта $x^\alpha$ является одной из попыток решения более общей проблемы проецирования случайных значений в как можно меньшую трехмерную область с зашифрованным отношением между этими точками. Все вопросы, сделанные здесь, касаются испытаний, решающих эту проблему. Они являются частью многих различных тем. Полное понимание каждой из этих тем и обнаружение того, что они не сработают, займет много времени, если вы не криптограф/математик. Поэтому я благодарен за любые рекомендации по темам, которые могут сработать.
kodlu avatar
флаг sa
не беспокойтесь, рад помочь, когда я могу. что именно вы подразумеваете под 3D?
J. Doe avatar
флаг at
Что-то похожее на трехмерный тор, то есть набор значений, который является циклическим в трех направлениях (+ их обратное направление и примерно одинаковый размер в каждом направлении). Не обязательно иметь каждое из этих 6 направлений для каждого члена (например, для $x^{\alpha_i} \bmod N$ с 6 подходящими $\alpha_i$). Некоторые сети с узлами, имеющими от $1$ до $n$ соседей, также будут работать. Однако окрестность одного элемента должна быть представлена ​​в трех двумерных плоскостях (точнее, в трех двумерных торах) с точкой пересечения этого элемента. Плотность узлов должна быть примерно одинаковой везде. ..
J. Doe avatar
флаг at
... Должен существовать какой-то детерминированный способ сопоставления соседей с плоскостью. Что-то вроде соседнего радиуса должно существовать — узел не может иметь соседей по всей поверхности.Графически говоря, если случайные точки на листе бумаги представляют разные элементы, то ближайшие члены, скорее всего, будут его соседями (или соседями соседей) (мы оборачиваем границу листа - так что сеть циклична в двух измерениях, как в 2- тор). Чтобы описать то, что я ищу, мы даем всем точкам/узлам на этом листе также номер. Таким образом, каждое число на этом листе имеет набор чисел в качестве двунаправленных соседей.
J. Doe avatar
флаг at
..Кроме того, у числа могут быть и (другие) соседи на 2-х дополнительных листах (по 2-тора на каждом). Если несколько чисел находятся на двух разных листах (2-тора), то все они лежат на одной линии (1-тор) — как на пересечении двух 2-торов. При этом расстояния между узлами/соседние ребра равны между этими узлами. Не менее $2^{32}$ узлов на 3 листах. Учитывая два случайных элемента, должно быть максимально сложно (относительно общего количества элементов) найти существующее соединение от одного узла к другому (цель около $2^{100}$ шагов вычисления)...
J. Doe avatar
флаг at
..Противник также может запускать программу и генерировать случайные значения/узлы. Не очень приятно, но может существовать несколько экземпляров примерно одной и той же структуры (не намного больше 10), поэтому для случайных узлов есть только (приблизительно постоянный) шанс быть подключенными. Лучше всего, если случайные узлы одного целевого экземпляра могут быть сгенерированы без утечки информации, связанной с безопасностью. Общий размер участников (включая экземпляры) должен быть как можно меньше (в лучшем случае $\приблизительно 2^{100}$ участников (может работать только с узлами), $\приблизительно 2^{150}$ участников, если проблема не сводится к 1D каждый)...
J. Doe avatar
флаг at
.. Я думаю, что это самое общее описание проблемы. Если мы вернемся к выровненной $6$-окрестности, это будет $x^{\alpha_i} \bmod N$ с 6 подходящими $\alpha_i$ снова. Для элементов большего размера, таких как 2^{218}$ элементов, EC может быть субоптимальным решением (не 3-тор).С $2^{300}$ участниками $x^\alpha$ выполняет свою работу, но так бывает со многими участниками...
J. Doe avatar
флаг at
... Они будут служить евклидовым и случайным, но последовательным расположением начальных чисел для ГСЧ, которое может быть построено итеративно, начиная со случайной точки и продолжая с евклидовыми ближайшими соседями и, наконец, приводя (после бесконечного времени для генерации) к одному и тому же согласованному ( секрет) структура. ....и снова слишком долго. Спасибо за чтение, если вы достигли этого момента.

Ответить или комментировать

Большинство людей не понимают, что склонность к познанию нового открывает путь к обучению и улучшает межличностные связи. В исследованиях Элисон, например, хотя люди могли точно вспомнить, сколько вопросов было задано в их разговорах, они не чувствовали интуитивно связи между вопросами и симпатиями. В четырех исследованиях, в которых участники сами участвовали в разговорах или читали стенограммы чужих разговоров, люди, как правило, не осознавали, что задаваемый вопрос повлияет — или повлиял — на уровень дружбы между собеседниками.