Разложение числа на множители.

← →
'<> (2010-05-05 13:57) [0]

Нахождение множителей числа.
Допустим есть число: 9,246490999e+37972
Оно получается в результате: 8546^9658+9684×68

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

Есть ли такой раздел математики, интересна любая информация по данной проблеме.

Не годятся методы которые раскладывают примерно так:
523525465472342364547= 17^2*433*4183618477926931
Так как степень задействуется всего на ^2, когда можно задействовать и сократить частично число 4183618477926931.

← →
Думкин © (2010-05-05 14:04) [1]

а сложение тут каким боком?

← →
brother © (2010-05-05 14:14) [2]

пишем самопальный архиватор? ;)

← →
Думкин © (2010-05-05 14:14) [3]

> Допустим есть число: 9,246490999e+37972
> Оно получается в результате: 8546^9658+9684×68

И это тоже вряд ли. Т.к. первое число оканчивается на гору нулей, а второе на 8.

← →
' (2010-05-05 14:19) [4]

> а сложение тут каким боком?

Сложение дабы добить по множителям нужное число

> пишем самопальный архиватор? ;)

Нет, задание по сокращению базы данных

> И это тоже вряд ли. Т.к. первое число оканчивается на гору
> нулей, а второе на 8.

Почему нельзя

← →
'<> (2010-05-05 14:26) [5]

Мне удалось найти, это вопросы Факториза́ции чисел.
http://ru.wikipedia.org/wiki/%D0%A4%D0%B0%D0%BA%D1%82%D0%BE%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F

Вопрос применим в криптографии RSA с открытым исходным ключем.

Так вот, зачастую все алгоритмы используют степень ^2.. есть мысли приблизить значение степени максимально к нужному числу, без перебора.

← →
Думкин © (2010-05-05 14:32) [6]

> "<> (05.05.10 14:19) [4]
>
> > а сложение тут каким боком?
>
> Сложение дабы добить по множителям нужное число

По слагаемым или по множителям? Каким боком сложение участвует в разложении на множители?

> Почему нельзя

Потому что. Если число оканчивается на 0, оно никак не может оканчиваться на 8.

← →
' (2010-05-05 14:40) [7]

> По слагаемым или по множителям? Каким боком сложение участвует
> в разложении на множители?

Мы разложили число по множителям, допустим изначально есть число "13619301793"

После чего мы каким-то образом находим это число:
23^7*4 = 13619301788

Еще нехватает 5

В результате: 23^7*4+5

---------
так сказать выводим нужные множители по средствам ^ и * и добиваем до нужного результата +

Меня интересует максимально использовать ^, затем *, затем + (такие приоритеты).

← →
Омлет © (2010-05-05 15:24) [8]

Хочешь взломать RSA?

← →
Jeer © (2010-05-05 15:27) [9]

> Меня интересует максимально использовать

"Иди и...учись" (С)

← →
brother © (2010-05-05 15:30) [10]

> После чего мы каким-то образом находим это число

а не об этом ли ты спрашиваешь?

← →
palva © (2010-05-05 15:42) [11]

Много материала о способах представления больших целых чисел можно прочитать у Кнута в Искусстве программирования т.2

← →
Sergey13 © (2010-05-05 16:03) [12]

> [4] "<> (05.05.10 14:19)
> Нет, задание по сокращению базы данных

Просто интересно. Что такое сокращение БД и как разложение на множители может этому способствовать?

← →
' (2010-05-05 16:03) [13]

palva
Спасибо. Это и надо по сабжу. Сразу подумал опираться на степень и на умножение.

← →
' (2010-05-05 16:05) [14]

Sergey13, научная работа, думаю над новой архитектурой хранения данных. То что я сейчас разбираю, очередной подход и эксперимент.

← →
Inovet © (2010-05-05 17:00) [15]

> [14] "<> (05.05.10 16:05)
> научная работа

Хм.

← →
pasha_golub © (2010-05-05 17:19) [16]

Архитектура хранения - это хорошо, а вычислительные затраты не зарубят всю идею на корню?

← →
Leonid Troyanovsky © (2010-05-05 18:13) [17]

> Inovet © (05.05.10 17:00) [15]

> Хм.

Тоже хочу такую работу - научную и без кнута.

--
Regards, LVT.

← →
Smile (2010-05-05 18:28) [18]

> Допустим есть число: 9,246490999e+37972

Не удосужил себя подсчетом значащих цифр в этом числе (с позиций Delphi), но мне кажется, что здесь необходима уже совсем другая арифметика (стринговая)

← →
'<> (2010-05-05 19:26) [19]

Для этого мне уже подсказали модуль RSA. Для работы с большими числами.

Вопрос открыт.

← →
Jeer © (2010-05-05 20:36) [20]

> Вопрос открыт.

Для тебя.

P.S.
Делать научную работу надо самому.

← →
' (2010-05-05 20:46) [21]

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

← →
oldman © (2010-05-05 20:55) [22]

> Вопрос, как имея любое подобное число, переделать его в
> порядок множителей

есть число а
получаешь число b - целая часть от корня квадратного из а
вычитаешь из а произведение b-1 и b, получаешь с

ответ: a=(b-1)*b+c

← →
Jeer © (2010-05-05 21:05) [23]

> как по моему сабжу вобще можно имея цисло, выцепить к нему
> приближену степень.. чтоб результат был приблизительно схож.
>

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

← →
' (2010-05-05 21:15) [24]

а = 386733 (целая часть от а 621) а=385020+с с=386733 - 385020 = 1713 (целая часть от корня 41) = 1640 с=1713-1640 = 73 Итог: 621^2+41^2+73

Это хорошо, oldman Но, ведь можно использовать

13^5 = 373248
c=386733 - 371293 = 15440
c=5^5 = 15625

Результат: 13^5+5^5+185 (Это я руками подобрал, видишь, за счет степеней выехал). Меня интересует это. Использовать такую степень и с такими числами, чтоб на степени выезжать и добавлять довесок.

Спасибо. Есть варианты.?

← →
TUser © (2010-05-05 21:16) [25]

Ну, собсно, если начальное число тебе задано точно (не double etc), то я бы перебрал для выражения a^b+c*d все мыслимые а, логарифмируем, ищем целое b, и находим разность, то есть c*d. Далее есть смыл перебирать только те а, для которых разность не велитка (степень явно сильно больше знаков экономит, чем произведение), ну а небольшие факторизовать можно.

← →
' (2010-05-05 21:25) [26]

TUser, если я понял, перебором только? а если число большое, то все это дело крякнет без диапазонов.. да и не факт, что подберется такая степень, с таким-то значанием.. так сказать идеально. Ведь как вариант на точность, можно степень задавать double от простого числа.

Какие еще варианты?

← →
oldman © (2010-05-05 21:29) [27]

http://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D1%84%D0%B0%D0%BA%D1%82%D0%BE%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8_%D0%A4%D0%B5%D1%80%D0%BC%D0%B0

← →
TUser © (2010-05-05 21:43) [28]

> Какие еще варианты?

Ты задачу поставь сначала. Что дано (число, точно или неточно оно дано), что найти (разложение в виде, чтобы было минимальным число знаков, или минимальной разность между значением получаемого выражения и исходным числом, должны ли числа быть целыми). А то, знаешь, любое n раскладывается в 1^1+1*1, число знаков минимально, только вот с точностью не всегда хорошо :)

← →
' (2010-05-05 21:55) [29]

Есть точное число, простое от 10 до 30 знаков. (Для работы с длинными числами RSA модуль). Задача, это число факторизовать в множители, которые используют Силу степени, чтобы записать нужное число в более короткое выражение.

Пример: 12^8 = 429981696 | а не 20736^2 (как используют многие методы факторизации).

Нужно максимально результативно использовать степень. Будет неточно, но точность будет дополняться операциями * + - к выражению.

Какие есть варианты? TUser, oldman

← →
' (2010-05-05 21:59) [30]

Кстати, за расшифровку RSA назначены крупные премии. От 30к$

> Будет неточно

Если тебе точность не важна, то 1^1.

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

А если тебе надо и того, и другого, то нас учили, что волки сыты и овцы целы - так не бывает. Оптимизировать можно только по какому-то одному параметру.

> Какие есть варианты? TUser, oldman

Да никаких. Не буду я больше за тебя гуглить.
Твоя же научная работа.
Имхо, все давно придумано. Читайте классиков математики. Только покруче, покруче.

> Кстати, за расшифровку RSA назначены крупные премии. От 30к$

жадины-говядины

← →
' (2010-05-05 22:07) [34]

> Если тебе точность не важна, то 1^1.

Что подразумевается под этим.

Как я понял, это подбор.

А - число
N - счетчик.
Р - количество знаков А-1

Подбор таков:
Пока N^A не будет приближенно равен А выполняем поиск.

← →
' (2010-05-05 22:09) [35]

Пока N^P не будет приближенно равен А выполняем поиск.

Ошибся, выше.

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

Это какой-то идиотизм. При чем тут разложение на множители автор так и не удосужился объяснится. Зачем для всего вот этого изложенного автором нужен Кнут еще более непонятно. Но народ пыхтит - чего-то помогает в этом помешательстве.

Это пипец дорогие гораждане.

Вот 28, например. Мне всю доргу казалось, что его разложение выглядит так:

28 = 7*2^2

Но оказывается, возможны варианты в виде:

28 = 3^3+1=5^2+3 и тп. Тту безусловно кнут поможет, но в виде оберток для курения конопли.

1. Если число разложить на несколько других чисел и операции между ними, то непонятно, каким образом это приведет к сокращению объема БД. Скорее, это приведет к обратному - к его увеличению (потому что вместо одного числа придется хранить несколько чисел и операций).

2. А наука-то в чем? Наука в обязательном порядке предполагает НОВИЗНУ - а где здесь новизна? В арифметике за курс средней школы?

Для кого-то и арифметика - наука непосильная. Автор скорее всего чего-то ломает, ну а научную основу под это подвести - святое дело

> Игорь Шевченко © (06.05.10 10:29) [39]

Ломает со сложением? Это чего такое сломать то можно? Он же разложением то так и не занимается. Тут только мозг собеседнику сломать и вынести можно. Не более.

Разложение числа на множители. Найти похожие ветки