Как выразить x из уравнения?

Question

[saf_dev]

У меня есть вот такое уравнение.
(y^x) mod z = с
Не могу выразить из него x. Помогите пожалуйста.

Comments

[Сергей Сергей]

log_y (c+z*i), i∈N

Answer 1

[AVKor]

Здесь

Comments

[saf_dev]

Вики предлагает решить методом перебора. А выразить было бы прикольно.
Интересной показалась тема с полиномиальным алгоритмом. Спасибо за ответ.

[AVKor]

А выразить было бы прикольно.

Что значит "выразить"? Вот в комментарии выше и ответе ниже "выражено" (с ошибкой одной и той же). Сильно полезно оказалось?

Answer 2

[Rsa97]

y^x mod z = c
y^x = c + z × i, i ∈ N
x = log_y(c + z × i), i ∈ N

Comments

[AVKor]

Вопрос из теории чисел, а не действительных функций.

[Rsa97]

AVKor, От этого преобразование не становится неправильным, добавляется только ограничение x ∈ N.

[AVKor]

Rsa97, Во-первых, это преобразование совершенно бессмысленно (оно ничего не даёт). Во-вторых, сравнения по модулю рассматриваются в кольце целых чисел (а не на множестве натуральных).

[Rsa97]

AVKor, Учитывая тэг RSA, речь идёт о криптографии. Значит x > 0. А множество целых чисел, больших нуля - это и есть множество натуральных чисел.

[AVKor]

Rsa97,

Учитывая тэг RSA, речь идёт о криптографии. Значит x > 0.

То, что x>0, RSA - не RSA, не имеет значения. Речь не о x.

y^x = c + z × i, i ∈ N

2¹ = 2 mod 3, 2¹ = 2 + 3*0;
2¹ = 5 mod 3, 2¹ = 5 + 3*(-1);...

[Rsa97]

AVKor, опять же, поскольку речь об RSA, то
x > 0, 0 ≤ y < z - из алгоритма RSA
0 ≤ c < z - из определения mod
y^x ≥ 0 => с + z × i ≥ 0
но если i < 0, то с + z × i < 0, что не соответствует условиям.
Значит i ≥ 0 или i ∈ N₀ (про N я слегка ошибся).

И кстати, 2¹ = 5 mod 3, 2¹ = 5 + 3*(-1) - тут ошибка. У вас c > z (5 > 3), чего быть не может.

[AVKor]

Rsa97,

0 ≤ c < z - из определения mod

Нет.

У вас c > z (5 > 3), чего быть не может.

Нет.
Учите теорию сравнений.
a = b mod m (m ∈ N, a, b ∈ Z) по определению тогда и только тогда, когда m | a-b. Или любое эквивалентное определение.
Ивана Матвеича вам в руки. Или любой другой учебник по теории чисел.

[Rsa97]

AVKor, То есть вы хотите сказать, что при делении неотрицательного целого числа на положительное целое остаток может быть больше делителя? Или меньше нуля?

[AVKor]

Rsa97,

То есть вы хотите сказать, что при делении неотрицательного целого числа на положительное целое остаток может быть больше делителя? Или меньше нуля?

Нет.

Я сказал ровно то, что хотел сказать, в комментарии выше:

Учите теорию сравнений.
a = b mod m (m ∈ N, a, b ∈ Z) по определению тогда и только тогда, когда m | a-b. Или любое эквивалентное определение.

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

[Rsa97]

AVKor,

Деление c остатком (деление по модулю) — арифметическая операция, играющая большую роль в арифметике, теории чисел и алгебре. Чаще всего эта операция определяется для целых или натуральных чисел следующим образом. Пусть a и b — целые числа, причём b ≠ 0. Деление с остатком a («делимого») на b («делитель») означает нахождение таких целых чисел q и r, что выполняется равенство:
a = b ⋅ q + r
Таким образом, результатами деления с остатком являются два целых числа: q называется неполным частным от деления, а r — остатком от деления. На остаток налагается дополнительное условие: 0 ⩽ r < |b|, то есть остаток от деления должен быть неотрицательным числом и по абсолютной величине меньше делителя. Это условие обеспечивает однозначность результатов деления с остатком для всех целых чисел, то есть существует единственное решение уравнения a = b ⋅ q + r при заданных выше условиях.

0 ⩽ r < |b| в нотации исходной задачи как раз и будет 0 ≤ c < z

Так что, батенька, попробуйте сами почитать учебники и найти свою ошибку.

[AVKor]

Rsa97, Вы вообще читать, похоже не умеете. Неспособны отличить определения сравнимости и остатка.

Определение сравнимости я выше давал.

Ещё одно (равносильное) определение: два числа a, b ∈ Z сравнимы по модулю m ∈ N по определению тогда и только тогда, когда их остатки при делении на m равны.

Если мало примеров выше, вот ещё один:
1 = -2 mod 3 (поскольку 3 | 1 - (-2) - по первому определению; 1 = 1 + 3*0, -2 = 1 + 3*(-1) - по второму определению).

А читать учебники мне нет необходимости, у меня специальность "теория чисел". У меня даже студенты-двоечники умели различать, сравнимы два числа или нет. А вам это ещё предстоит научиться делать.

В общем, учите матчасть. Читайте Главу третью, параграф 1, пункты a., b., c учебника Виноградова или в любом другом аналогичный материал.

[Rsa97]

AVKor, А где вы в алгоритме RSA увидели слово "сравнимость"?

[AVKor]

Rsa97, Хотите упорно продолжать ломать эту комедию?

Открываете любой материал, посвящённый RSA, и ищете там слова сравнимо/сравнение/сравнимость или (если на английском) congruent/congruence. Например, вот тут, чтобы далеко не ходить. И вот такая фиговина, где mod написано - это называется сравнением по модулю.