Обратная операция к (a^5%43)

[wrest]

Выяснилось, что остатков от деления пятой степени на $43$ чисел от $1$ до $43$ как раз $43$, то есть $b=a^5 \mod 43$ (mod имеется в виду операция взятия остатка от деления, в данном случае на 43) даёт $b$ в диапазоне $0 \dots 42$ и не повторяется. В отличие от квадратичных вычетов, которых для модуля $43$ существует только половина ($21$).
Вопрос: может ли быть формула для вычисления $a$ если известно $b$ и известно, что $1\le a \le 43$
Никаких попыток самостоятельного решения кроме таблицы $b->a$ привести не могу в виду нехватки знаний. Но таблица у меня есть, в крайнем случае по ней буду.

1. a b 
2. 1 1 
3. 2 32 
4. 3 28 
5. 4 35 
6. 5 29 
7. 6 36 
8. 7 37 
9. 8 2 
10. 9 10 
11. 10 25 
12. 11 16 
13. 12 34 
14. 13 31 
15. 14 23 
16. 15 38 
17. 16 21 
18. 17 40 
19. 18 19 
20. 19 30 
21. 20 26 
22. 21 4 
23. 22 39 
24. 23 17 
25. 24 13 
26. 25 24 
27. 26 3 
28. 27 22 
29. 28 5 
30. 29 20 
31. 30 12 
32. 31 9 
33. 32 27 
34. 33 18 
35. 34 33 
36. 35 41 
37. 36 6 
38. 37 7 
39. 38 14 
40. 39 8 
41. 40 15 
42. 41 11 
43. 42 42 
44. 43 0 

[Dmitriy40]

PARI/GP позволяет вычислить прямо:

? a=sqrtn(Mod(b,43),5);

[wrest]

Dmitriy40 в сообщении #1631491 писал(а):

PARI/GP позволяет вычислить прямо:

А питон? В pari/gp mod это же такая спецструктура, наверное там что-то типа таблицы и делается?

[Null]

$a=b^{17}$?

(Оффтоп)

Решение учебной задачи, нужно вынести мне предупреждение

[venco]

$(a^5)^{17}=a \mod 43$

[wrest]

Null в сообщении #1631497 писал(а):

$a=b^{17}$?

venco в сообщении #1631499 писал(а):

$(a^5)^{17}=a \mod 43$

Спасибо!

[venco]

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

А так принцип решения такой:
Надо найти $n$-ный корень по модулю $p$.
По малой теореме Ферма $x^{p-1}=1 \mod p$, а значит $x^{k(p-1)+1}=x \mod p$
Т.е. надо найти такое $m$, чтобы $nm = 1 \mod (p-1)$, т.е. $m=n^{-1} \mod (p-1)$.

[wrest]

venco в сообщении #1631506 писал(а):

А так принцип решения такой:

И где там возникает 17?

[Dmitriy40]

wrest в сообщении #1631515 писал(а):

И где там возникает 17?

В самой последней формуле:

? Mod(1/5,42)
%1 = Mod(17, 42)

$n^{-1} \mod{p-1} = 5^{-1}\mod{42} = 17 \mod{42}$
$5 \cdot 17 = 85 = 1 \mod{42}$

[wrest]

Гениально! Спасибо всем!
Просто так оказалось, что букв в родном алфавите 33 и ещё 10 цифр а всего 43 символа (простое число, повезло). И вот остатков 5-х степеней от деления на 43 -- тоже 43 (с нулём). Можно операцией взятия остатка от 5 степени номера символа кодировать этот алфавит, и для декодирования удивительным образом не нужна таблица.

[Dmitriy40]

А почему 5-я степень? Не первая?
И повезло не только что 43 простое, но и что 42 не делится на 5 (41 не подошло бы, с ним остатков пятой степени не 41, а всего 9).

[wrest]

Dmitriy40 в сообщении #1631518 писал(а):

А почему 5-я степень? Не первая?

Ну первая степень это просто шифр путём ротации алфавита (если смещение задать). А так -- перестановочка прикольная.

[Dmitriy40]

Ну тогда подойдёт любая нечётная степень, не делящаяся и на 3 и на 7 (взаимно простая с 42).

[wrest]

Dmitriy40 в сообщении #1631523 писал(а):

Ну тогда подойдёт любая нечётная степень, не делящаяся и на 3 и на 7 (взаимно простая с 42).

А 13-я будет работать в обе стороны :)

[vicvolf]

wrest в сообщении #1631487 писал(а):

Выяснилось, что остатков от деления пятой степени на $43$ чисел от $1$ до $43$ как раз $43$, то есть $b=a^5 \mod 43$ (mod имеется в виду операция взятия остатка от деления, в данном случае на 43) даёт $b$ в диапазоне $0 \dots 42$ и не повторяется.

Разве это не известные индексы - Бухштаб "Теория чисел" стр. 152?