Число возводится в степень 5 и делится на 1089671048441. После этого становится известен остаток от деления. Вопрос, как найти число? Т.е.

x^5 mod 1089671048441 = y;

Найти x при известном y.

Пример:

  • Остаток от деления = 252260378, число 956044873207;
  • Остаток от деления = 604222124, число 876582861739;
  • Остаток от деления = 622543887, число 251172385378;
  • Остаток от деления = 2418908791, число 196922307772;

задан 17 Ноя '12 22:38

изменен 18 Ноя '12 12:12

%D0%A5%D1%8D%D1%88%D0%9A%D0%BE%D0%B4's gravatar image


5525

ДОПОЛНЕНИЕ

однозначно восстановить первоначальное число - не требуется, любое которое подходит под условие.

Вот нашел "Китайская теорема об остатках". Попробую использовать.

(18 Ноя '12 17:39) Darkmaster

Ссылка неудачная, в Вики этой теоремы нет. Есть, например, здесь. Я думала об этом, но тогда дело упирается в разложение исходного числа (делителя) на множители. Что тоже, знаете ли, весьма непростая задача.
Тем более, что задача "извлечения корня 5 степени" остается.
Я думала, нельзя ли применить здесь малую теорему Ферма, но там речь идет об остатках при делении на простое число.

$%a^p\equiv a (mod p)$%. Но не вижу пока возможных связей...((

(19 Ноя '12 0:11) DocentI

Правильно делим на простое число 1089671048441 - простое число.

Да ссылку уже не могу отредактировать. просто в адресе браузера уберите в конце ")." попадете на статью в вике

А какая проблема с извлечением корня 5-й степени я не понял ? Цифры большие и считает их машина, мне надо только машине расказать как, а я никак не могу составить алгоритм :)

(19 Ноя '12 2:50) Darkmaster

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

(19 Ноя '12 3:16) DocentI

ДОПОЛНЕНИЕ

допустим x^5=y мы ищем Y, который при делении на известное целое положительное число C дает целое число + известный остаток (обозначим его OST) Фактически Y можно представить в виде Y=K*C+OST, где K-целые положительные числа, K=1,..., бесконечность Но нам нужно такие Y, чтоб корень 5-й степени дал целое число

Метод перебора K=1,..., 1830000000 не дал результатов (C=1089671048441, OST=3155979573)

уже больше 16ч пербирает

(23 Ноя '12 12:37) Darkmaster

@Darkmaster, Если вы получили исчерпывающий ответ, отметьте его как принятый.

(20 Апр '14 17:44) Angry Bird
показано 5 из 6 показать еще 1
10|600 символов нужно символов осталось
2

Если не известно разложение числа на простые множители, но эта задача не решается. Как раз на этом эффекте основан криптографический алгоритм RSA. Однако, если разложение получено, как в данном случае, то далее проще всего поступить так. У нас есть число $%n=pq$%, где $%p,q$% -- различные простые. Тогда можно найти значение функции Эйлера $%\varphi(n)=(p-1)(q-1)$%. Считая, что $%y$% не делится ни на $%p$%, ни на $%q$%, что легко проверить, имеем то же самое для числа $%x$%, которое нам пока не известно. Далее применяем теорему Эйлера: $%x^{\varphi(n)}\equiv1\pmod{n}$%. Поэтому для нахождения $%x$% достаточно возвести $%y$% в подходящую степень $%k$%, чтобы выполнялось условие $%x\equiv y^k\equiv x^{5k}\pmod n$%. Оно будет выполняться, если $%5k\equiv1\pmod{\varphi(n)}$%, а это есть линейное сравнение по известному нам модулю, которое легко решается.

ссылка

отвечен 20 Фев '13 19:15

10|600 символов нужно символов осталось
1

Для нахождения остатков при делении больших чисел на большие нужно использовать среду программирования. Там нужно реализовывать алгоритмы работы с большими натуральными числами. Один из способов реализации-использование массивов.

ссылка

отвечен 17 Ноя '12 23:27

Спасибо за ответ. Естественно вычислять будет машина :). Но не могли бы Вы подсказать алгоритм ? Или давайте предположим что числа маленькие.

(18 Ноя '12 0:04) Darkmaster
10|600 символов нужно символов осталось
1

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

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

ссылка

отвечен 18 Ноя '12 0:53

изменен 18 Ноя '12 15:28

Полный перебор это я стану старым пока он закончится :) однозначно восстановить первоначальное число - не требуется, любое которое подходит под условие

(18 Ноя '12 17:14) Darkmaster
10|600 символов нужно символов осталось
1

Если я правильно понял, Алгоритм такой:

  • для малых чисел: = `СТЕПЕНЬ((24*10+3);0,2), результат - 3
  • для вашего случая: = `СТЕПЕНЬ((956044873207*1089671048441+252260378);0,2), результат - 63614,29783
ссылка

отвечен 18 Ноя '12 10:59

изменен 19 Ноя '12 19:56

Нет, неправильно. Задача должна решаться в целых числах.

(18 Ноя '12 14:46) DocentI

Да задача решается в целых числах - совершенно верно

(18 Ноя '12 17:45) Darkmaster
10|600 символов нужно символов осталось
1

Подобные функции используются для алгоритма Диффи-Хеллмана ,и как известное для чисел больше 10^50 она не решаема и на супер компьютерах .Поэтому в общем виде нормального решение рассказать не могу.


Если числа именно такого порядка ,то можно попробовать частичный перебор : он может не принести результата в некоторых случаях , но если числа лежат хорошо - то мы быстро найдем решение.


$$x^5\ mod\ b \ =\ y$$

i = 1;  
t = b + y;  
while ( srqt_5(t) in R\Q )  
{  
  i++;  
  t = b * i + y;  
}  
return sqrt_5(t);
ссылка

отвечен 20 Ноя '12 21:55

изменен 21 Ноя '12 19:31

Deleted's gravatar image


126

А что, в Си есть встроенное средство проверки принадлежности числа множеству иррациональных чисел?!

(21 Ноя '12 22:26) Андрей Юрьевич

Сомневаюсь ,я старался код писать не на С ,а на псевдоязыке.
Но простая проверка - { ((int)a) < a => a in R\Q }

(21 Ноя '12 22:41) Balon

int - это целая часть? Неравенство int a < a показывает на дробное число, а не иррациональное.
В компе все числа записаны как рациональные (конечные десятичные дроби, например). Может, лучше проверить $%(\sqrt[5] a)^5 < a$%?

(21 Ноя '12 23:17) DocentI

Да, совершенно верно, все числа, реализуемые в компьютере, - рациональные, и более того, все они сводятся к "псевдоцелым", т.е. представляемым конечной десятичной (или двоичной) дробью с фиксированным числом знаков после запятой. Например, число с плавающей точкой - это упорядоченная пара двух псевдоцелых.

(22 Ноя '12 12:20) Андрей Юрьевич

Нам важно корень целый или нет, так как этот корень из целого числа, то он или целый или иррац. .

(22 Ноя '12 19:43) Balon

Да, это верно. Зачем же было писать про рациональность?

(23 Ноя '12 0:14) DocentI
показано 5 из 6 показать еще 1
10|600 символов нужно символов осталось
1

Разложим число 1089671048441 на простые множители: оно равно 1011077х1077733. Решим отдельно уравнения $%x_1^5$% mod 1011077=y mod 1011077 и $%x_2^5$% mod 1077733=y mod 1077733, для этого годится и полный перебор (если надо решать данную задачу для большого набора различных y, то стоит сделать таблицы или другое кэширование). Получим до пяти групп решений вида $%1011077n_1+x_1$% для первого уравнения и $%1077733n_2+x_2$% для второго. Уверен, что можно найти формулу, по которой сразу находится x из этих двух уравнений (как-то при помощи обратного по модулю, наверно), но даже банальный перебор $%n_1$% даст результат за приемлемое время.

ссылка

отвечен 23 Ноя '12 4:00

Спасибо за ответ. Допустим я нашел x1 и x2 что дальше ?

пример: x=5, 5^5 = 3125, остаток нужен например 10 число на которое делим 35 = 7*5 3125 mod 35 = 10 3125 mod 7 = 3 3125 mod 5 = 0

(23 Ноя '12 13:24) Darkmaster

Дальше - китайская теорема об остатках и алгоритм Гарнера (см. ссылку выше)

(23 Ноя '12 13:28) DocentI
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×112

задан
17 Ноя '12 22:38

показан
6691 раз

обновлен
20 Апр '14 17:44

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru