Как решить уравнение?

Цитата
puno
1) Нужно решить уравнение:

(a^k) mod N = a.

Нужно найти k, для заданных a и N. Какие способы решения?

2) Или хотя бы частный случай 2^k mod N = 2.
Какие способы найти k для больших N?

Вы наверно имеете в виду $(x^n)mod(x )$ ?

Автор предлагает решить сравнение по модулю. Это не уравнение..
При любом а и простом N данное сравнение является малой теоремой Ферма.,т.е.

k = N = p (простое)

Для решения в общем виде надо сначала найти зависимость N от a и k , а затем
решать обратную задачу. При k > 2

N = a^(k - 2) + a^(k - 3) + .....+ a^(k - k).

.



Редактировалось 1 раз(а). Последний 24.03.2022 22:29.

Цитата
alexx223344
a^(k - 2) + a^(k - 3)..........
Эта фигня добавляет к целым решениям еще и рациональные , дроби.
Но какой смысл ее решать в дробях пока не ясно.

Где вы увидели здесь дроби ???

Кстати, неясно (туманно) пишется слитно.

Цитата
alexx223344


Допустим нашли.
А как саму обратную задачу будете решать?

Не "допустим" , но нашли...
А дальше сплошная "фигня" для 5--го класса
модульной арифметики.

Дано (a^k) mod N = a.

Решение N = a^k - a

Находим все простые делители N.

N = p1*p2*p3*p4.......

Исключаем все делители p, начиная с первого, и до такого M = p1*p2*...*pi, что (M > a).

Тогда N = M*p(i+1)*p(i+2)....

Подставляем в N = a^k - a

Получаем a^k - a = M*p(i+1)*p(i+2)....

Получили множество произведений M*px, которое удовлетворяет условию.

Так можно даже все возможные N найти для заданного только одного a, умножив M на любое число.

Цитата
alexx223344
.

Дайте численный пример.

Цитата
ammo77
Пример 1;

$9^k mod 99 = 9$ где k=1+5n


Примеры зависят от кольца или поля .

Однако надо найти k из того что дано.
Как вы получили 1+5n из четырех девяток (9^k mod 99 = 9)?
Хотя все равно не скажете.

Цитата
alexx223344

Цитата
ammo77
Пример 1;

$9^k mod 99 = 9$ где k=1+5n


Примеры зависят от кольца или поля .

Однако надо найти k из того что дано.
Как вы получили 1+5n из четырех девяток (9^k mod 99 = 9)?
Хотя все равно не скажете.

Это легко и правильно но только для арифметической прогрессии 0mod9 ,для других кратных 3 это не работает при (a^k) mod N = a. хотя может и по другому модулю можно
получит не проверял . k=1+5n простая комбинаторика а как по другому доказать ВТФ ? не разбирать же 150 стр.никому непонятного док. Эндрю Уайлса которое точно не доказано моим методом..

Пример в обратную сторону : k = 30 n + 1, n element Z, n>=0 найдите a при (a^k) mod N = a

Если честно не знаю для чего понадобилось автору (a^k) mod N = a или по пятам идет к моему методу для ВТФ.Хотя не уверен что осилить постройку общей конструкции но это легко.

Wolfram + по сложнее вычисляет но конечно не может найти a и N для этого нужный свойства колец .
(dN(a, n))/(da) = -(N (1 - a^(30 n) - 30 a^(30 n) n + a^(30 n) ( piecewise | 0 | a^(1 + 30 n)/N>floor(a^(1 + 30 n)/N)
indeterminate | (otherwise)) + 30 a^(30 n) n ( piecewise | 0 | a^(1 + 30 n)/N>floor(a^(1 + 30 n)/N)
indeterminate | (otherwise))))/(N floor(a^(1 + 30 n)/N) - a^(1 + 30 n) ( piecewise | 0 | a^(1 + 30 n)/N>floor(a^(1 + 30 n)/N)
indeterminate | (otherwise)))


$a^(30 n + 1) - N floor(a^(30 n + 1)/N) = a$



Редактировалось 9 раз(а). Последний 27.03.2022 13:37.

Цитата
alexx223344
(a^k) mod N = a
годится только для 3 степени ВТФ
для других надо

(a^k) mod N = a^(k-2)

У меня есть все уравнения для кольца (a^k) mod N = a хотя этот вид можно по другому
представит . Я показывал таблицы степеней чтоб как раз мгновенно находит числовые подстановки для (a^k) mod N = a .

Тот же k = 30 n + 1 можно использовать для

$((5^k)mod99)=5$ только как вы это используете вне понимания ?

Здесь геометрия от кольца думаю Уайлс от них собирал доказательство.

https://www.facebook.com/photo/?fbid=7502332573125096&set=gm.3115437062073280



Редактировалось 1 раз(а). Последний 27.03.2022 17:06.