мод, простое -> возможно обратное

Question

Мне было интересно, можно ли сделать следующее:

У нас есть:

• X является продуктом N -прм, поэтому я предполагаю уникальным.
• C является константой. Мы можем заверить, что C - это число, которое является частью N -прим или нет. Что будет работать лучше всего.
• X mod C = Z

У нас есть Z и C, и мы знаем, что X был продуктом N -прим, где ограничено N, скажем, первые 100 простых чисел.

Есть ли в любом случае, мы можем вернуться X?

Answer 1

Нет. Вот контрпример:

Предположим, X = 105 (= 3x5x7).

Взять C = 13, чтобы X mod C = Z = 1.

Однако X = 118 (= 2x59) также дает Z = 1 с C = 13.

Answer 2

Я так не думаю. Поскольку C не является частью X, вы теряете информацию, когда выполняете операцию X mod C. Кроме того, мод возвращает только часть операции и требует div для получения другой части результата.

Пример: (3 * 5)% 7 = 1. Поскольку вы потеряли информацию, я не вижу способа вернуться к 15 с 1 и 7 без прямой части div. Вам нужно было бы начать складывать 7 и добавлять остаток и сравнивать, чтобы смоделировать недостающую часть div в уравнении.

Answer 3

Существует бесконечное число простых чисел (и, следовательно, бесконечное произведение простых чисел N), но только C возможных значений X mod C. Таким образом, с подавляющей вероятностью, будет бесконечное действительное значение X, которое удовлетворяет X mod C = Z.

Итак, если вы хотите определить, какой из них был вашим оригиналом X, то нет, этого нельзя сделать.

Answer 4

Я не уверен, правильно ли я понимаю ваш вопрос, но если вам заданы Z и C, и вы хотите вычислить X.

Если X mod C = Z, то это означает, что для некоторого натурального числа q справедливо, что qC + Z = X, поскольку q неизвестно, в общем случае невозможно точно рассчитать X, однако существует бесконечное множество чисел, удовлетворяющих этому уравнению. Это тоже не странно. Предположим, у вас есть некоторый X ', который может быть решением, тогда также X' '= X' + C является решением, одинаково действительным.

Является ли C и X взаимно простыми (т.е. они (не имеют) общих простых факторов), не имеет значения, если я не ошибаюсь. Однако это делает ваше решение немного меньшим, потому что если X и C имеют общие простые множители, скажем, p1, p2, ... pn, то каждое допустимое решение также должно делиться на p1 * p2 * ... * pn.

Answer 5

Нам понадобится дополнительная информация, чтобы выяснить это для вас. Например, если вы имеете в виду, что X является произведением первых N простых чисел, N <= 100, то поиск методом перебора будет работать для вас. </p>

Если вы имеете в виду X произведение некоторого подмножества первых 100 простых чисел, то это сложнее. По сути, вы спрашиваете, можете ли вы сказать, является ли X гладким или нет для данного X mod Z. Если бы вы могли это сделать, вы, вероятно, сможете улучшить наиболее известные алгоритмы целочисленного факторинга, поскольку они зависят от обнаружения гладких чисел различных форм. .

Конечно, если вы можете выбрать достаточно большой C, чтобы X mod C = X, то это легко.

См. http://en.m.wikipedia.org/wiki/Smooth_number для обсуждения гладких чисел.

Answer 6

Ваш вопрос довольно сложен для понимания, но, возможно, вы хотите прочитать о Китайской теореме об остатках .