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

← →
'<> (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к$

← →
TUser © (2010-05-05 21:59) [31]

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

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

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

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

← →
oldman © (2010-05-05 22:00) [32]

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

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

← →
TUser © (2010-05-05 22:00) [33]

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

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

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

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

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

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

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

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

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

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

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

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

← →
Думкин © (2010-05-06 05:27) [36]

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

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

← →
Думкин © (2010-05-06 05:31) [37]

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

28 = 7*2^2

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

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

← →
Юрий Зотов © (2010-05-06 06:15) [38]

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

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

← →
Игорь Шевченко © (2010-05-06 10:29) [39]

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

← →
Думкин © (2010-05-06 10:45) [40]

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

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

← →
Игорь Шевченко © (2010-05-06 10:47) [41]

Думкин © (06.05.10 10:45) [40]

> Ломает со сложением? Это чего такое сломать то можно? Он
> же разложением то так и не занимается.

как умеет :))

← →
Rouse_ © (2010-05-06 11:03) [42]

Ломать RSA разложением паблик ключа на множители при длине ключа от 768 достаточно бесперспективная задача и более того практическое применение при успешном разложении достаточно смутно видится. Если задача состоит в декрипте блока данных, то обычно это дают делать приложению, после чего дампят открытые данные :)

← →
имя (2010-05-06 11:23) [43]

Удалено модератором

← →
'<> (2010-05-06 11:37) [44]

> Вот 28, например. Мне всю доргу казалось, что его разложение
> выглядит так:
>
> 28 = 7*2^2
>
> Но оказывается, возможны варианты в виде:
>
> 28 = 3^3+1=5^2+3 и тп. Тту безусловно кнут поможет, но в
> виде оберток для курения конопли.

=) Пойми же, мне надо максимально использовать степень!
(28 = 7*2^2) - тут используется только степень ^2, ведь можно как раз использовать такое выражение (3^3+1) и получим тот же результат, но это будет удовлетворять моим нуждам.

Я ничего не ломаю, это эксперимент. По сабжу необходимо, то что я зацитатил (использовать степень отличную от ^2, а максимально эффективную), обертки тут не причем, разве так сложно вообразить степень больше ^2 при разложении.

← →
Anatoly Podgoretsky © (2010-05-06 11:45) [45]

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

Научная основа - это навешать лапши на уши?

← →
Думкин © (2010-05-06 11:47) [46]

> Пойми же, мне надо максимально использовать степень!

Ну, значит сабж не соответствует запросу. И пока это похоже на заклинание

"Люк, используй СИЛУ СТЕПЕНИ!!, максимально эффективную"

Люк, наверное, просечет в чем эта максимальная эффективность силы, но мне с моим ограниченным образованием подобное не под силу. Так надо то чего в итоге все-таки, Йода?

← →
' (2010-05-06 11:56) [47]

Может это реализуемо через НОД НОК? Может подбор как-то через это можно наладить?

← →
Думкин © (2010-05-06 12:01) [48]

> "<> (06.05.10 11:56) [47]

Подбор чего? Задача то так и не сформулирована.

← →
' (2010-05-06 12:07) [49]

Задача в том. Допустим, есть число:

28 = 7*2^2 (это находится как Корень из 28 в степени 2)

Но можно разложить так:

28 = 3^3+1 (тут уже засчет степени мы приблизились к исходному числу)

Так сказать степень и число под степенью чтоб было максимально близкое в результате к исходному числу.
Может найти можно как-то через НОД НОК?

Это основная задача. Пожалуйста помогите. Что-то типа колмогоровского числа.

> Так сказать степень и число под степенью чтоб было максимально
> близкое в результате к исходному числу

a = a^1+0 Гы. :)

Логарифмирование перебором.

> "<> (06.05.10 12:07) [49]

Начиная с 1 и до бесконечности извлекаешь корень степени n из искомого числа до того момента, пока результат не станет меньше двойки.
Ты нашел максимальную степень, поздравляю.
Потратив уйму времени.
Даже для четырехзначного 1024 надо дойти до n=10
А у тебя 30...40 значное число
Успехов в переборе!!! :)))

> Думкин © (06.05.10 12:12) [50]
> > Так сказать степень и число под степенью чтоб было максимально
> > близкое в результате к исходному числу
> a = a^1+0 Гы. :)

Неа.
a = 1^(бесконечность)+a
Два раза Гы :)

> Начиная с 1 и до бесконечности извлекаешь корень степени
> n из искомого числа до того момента, пока результат не станет
> меньше двойки.
> Ты нашел максимальную степень, поздравляю.
> Потратив уйму времени.
> Даже для четырехзначного 1024 надо дойти до n=10
> А у тебя 30...40 значное число

Можно применить половинное деление (или как оно называется). Наподобие поиска числа в отсортированном массиве.

Автору,
Самый простой способ:
1. Делаешь тупым перебором, отлаживая на маленьких числах.
2. Оптимизируешь то, что у тебя получилось.

А пока складывается ощущение, что ты сам не понял чего хочешь.

N=sum(a[k]^b[k])+sum(c[k]*d[k])
max( min(a[k],b[k],c[k],d[k], for all k)) -> min?

> Alx2 © (06.05.10 14:03) [54]

Я так думаю, что там типо хитрым вывинтом рассыпав бисер хочется собрать Бородино.

Берем число 99^99+98*97 получаем кучу цифр и радуемся, что выразить его смогли используя лишь 4 байта. Думаем, что таким финтом сможем поступит с любым числом которое имеет такое же хитрое и большое написание в десятричной системе.

Допустим смотрим на числа в виде a^b+c*d и {a,b,c,d}<=100

В итоге получаем максимальное в виде 100^100+100*100, что впечатляет, а чисел помечаем лишь 100^4, притом получаем дырки непомеченных в среднем уровня 10^98. Вот последнего, видимо, пока и не понятно автору.

ТО есть при заданном мной, я беру число (99^100+100^100+1)/2 и ищу ео выражение в указаном виде. Ну и все. Можно поднять величину числа a, а потом и других. В итоге приходим, что банальная запись в виде двоичного куда экономнее. Потому чего хочет автор - только Йода знает.

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

Интересно, а вообще есть какой-нибудь способ сжать число, представленное в обычном двоичном виде, а не в виде текста? Если появление всех чисел равновероятны, то и появление всех цифр в определенной позиции определенного числа тоже равновероятны. ИМХО такое просто нельзя сжать, т.к. избыточности нет.

> Интересно, а вообще есть какой-нибудь способ сжать число,
> представленное в обычном двоичном виде

zip вот сжимает

> zip вот сжимает

Ну там, наверное, несколько чисел. И архиватор находит какую-нибудь закономерность - кто-то встречается в 49% случаях, а что-то в 51%. Или нет? Если нет, то интересно было бы знать - как это делается?

Удалено модератором

← →
Конформист (2010-05-06 21:19) [63]

> "<> (05.05.10 13:57)

Тоже "4исла" смотрел? Лимон, как Перельман хочешь?

← →
' (2010-05-06 23:00) [65]

................................................................................ ..........
................................................................................ ..........
..............................Тема закрыта.
................................................................................ ..........
................................................................................ ..........

Все перетекло совсем в другое русло.

Тему закроют тогда, когда захотят другие. Русло то самое. Но задачу так и не услышали. Жаль. А ведь верная постановка - уже полдела. До науки тут как известным методом до Луны, да.

>Думкин © (06.05.10 16:18) [56]

При таком подходе - да, конечно :)

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

> Alx2 © (07.05.10 09:07) [68]

Да про сжатие чисел - мол к шарлатанам надо обращаться (про биективные отображения не счел нужным и видимо зря). :) А потом просто нотацию прочитал про весенне-юношеское обострение. :)

А интерес ради интереса понятен, но я хотел таки автора подтолкнуть к формулированию своей задачи и осознанию ее. Но этого не произошло. Он просто обиделся.

Кстати, здесь еще лишь один шаг, и будет задачка поиска сложности по-Колмогорову (у него это минимальная по длине программа (на Паскале ;-) ), генерирующая заданное число).

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