В качестве разминки мозга иногда занимаюсь проблемой быстрого разложения большого числа на простые множители(достаточно двух), эта задача имеет важное практическое значение в криптографии. До сих пор не известно, имеет ли данная задача решение на уровне математики.
Сегодня появилась новость, конечно не такого масштаба но тем не менее.
http://lenta.ru/articles/2013/05/17/primes/

Итан Джан. Да, истинный американец... У них там не понаехалы есть вобще умные?)
http://www.google.ru/imgres?imgurl=http://icdn.lenta.ru/images/0000/0300/000003000855/preview_1368717969.jpg&imgrefurl=http://lenta.ru/articles/2013/05/17/primes/&h=279&w=240&sz=16&tbnid=p4L489mn1-RQMM:&tbnh=114&tbnw=98&zoom=1&usg=__QTR8sC927U9D0qmafWi1YrPL080=&docid=NJidIEjJIwDDcM&sa=X&ei=pvqVUde9MqSD4ATDu4DICg&ved=0CG4Q9QEwCQ&dur=533

(2) У них только понаехалы и есть...

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

странно, что на ленте такой текст опубликовали :)

Если бы решили проблему и опубликовали проблему в (0). Я думаю и на ленте, и на rbc написали бы. А что творилось бы на биржах это сложно представить. :)

(0) Молодцы, долго ждал.

"Итан Джан"...
сразу напомниило
http://litvinovs.net/pantry/migunov_monday_begins_on_saturday/glossary_jan_(new).jpg

(10) Сарказм?

(0)
"Я ничего не понял, но на всякий случай удачи!"

(0)
"достаточно двух" - это оттого, что сейчас для ключей два простых используют?

(12) Ваш комментарий как автора можно услышать?

(7) Да. Алгоритм Шора.

(16) Я же написал, математическими средствами.
Квантовые вычисления это еще бабка на двое сказала.(точнее с точки зрения математики все правильно , только вот устройство пока гипотетически-фантастическое). Может впоследствии будет обнаружено что это была тупиковая ветвь.(хотя может и обратное)
(15) Мне просто было интересно, кто нибудь из одинэсников вообще этим интересуется?

тоже недавно заинтересовался данной темой. понравилась эта, немного детская, статья https://sites.google.com/site/viktortsekunov/popularly/delimost

Пытаюсь составить подобные алгоритмы для шестнадцетиричной системы исчисления. Нужно время, которым к сожалению не располагаю :(

(0)Это, например, 1200 разложить на простые множители 12 и 100?

А какая приктическая польза в применении к криптографии?
Мне интересно, я без стеба.

(19) 12 и 100 - не простые множители

(20)ага, погуглил

(21) Об этом в школе рассказывают :)

1200 = 2^4 * 3 * 5^2
http://www.webmath.ru/web/prog34_1.php

(0)Интересная статейка.

(23) А 574765939757391049237567326717858693919610293958687800494868783742767398079508382461068432165953137 не разложишь?

(25) 574765939757 = 91757*6264001

(26) фигня получилась...
(25) могу перевести в шестнадцатиричное. Надо?
10D16393E4D4C383331282DFE92D19235922813CF79155131A8CBDC313AFEBD74B40F148FCC801DDE71

(25) 17 x 23 x 1063 x 7433 x 3 020189
x 17 943019 x 3433 106143 833212 737403 736763 662977 252174 213245 267653
288360 488607 773303 390663
Последний множитель в процессе разложения.

Готово.
574 765939 757391 049237 567326 717858 693919 610293 958687 800494 868783
742767 398079 508382 461068 432165 953137 = 17 x 23 x 1063 x 7433 x 3 020189
x 17 943019 x 2205 013216 353719 212857 847118 994959 x 1 556954 905472
316168 550758 164999 519323 642057

ОФФТОП:
Можно ли разбить числа 1, 2, ..., n на два множества так, чтобы произведение чисел одного из них равнялось произведению чисел другого?

(30) Нет, для этого их произведение (факториал) должно быть квадратом некоторого числа.

(31) а почему оно не может быть квадратом?

А факториал числа больше 1 не может быть точным квадратом исходя из постулата Бертрана.

(31) "должно быть квадратом некоторого числа" почему?

(34) Мы разложили на две группы. В первой и второй одно и тоже произведение. Значит произведение двух групп - квадрат.
А произведение двух групп это факториал.

(33) да, а если без постулата?

(35) угу. только в мат вики поступлат Бертрана по другому звучит.

(36) А зачем без постулата? Между n/2 и n всегда есть простое число. Значит n! делится на это простое число, и не делится на его квадрат. Значит не может быть квадратом.

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

ух...

(39) ясно :)

Всегда поражался математикам.

(42) угу, это круто!
пару раз удавалось словить кайф от математики... особенно от всяких динамических/линейных программирований. исследования операций и прочего.
.
жалко что сейчас это почти никому не нужно... в загоне...

(43) Не поверишь. Когда сейчас программисты со спец заводов разбирают мат модель, заложенную при СССР, в управление ракетой, то не могут понять как оно вообще летает. А летает превосходно.
Есть огромный разрыв между советской школой программистов и современными :(
Печалька однако.

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

(43) Когда что-нибудь сделал - всегда приятно.

(44) а почему печалька? просто раньше дешево стоили мозги, а теперь ресурсы компа. Радоваться надо.

(47) +1. До сих пор жалею что не пошел в свое время на математика...

(47) ну да, только мозги запускают/программируют ракеты, а компы - нет.

(47) а если эти ресурсы компа, да на те ресуры мозгов...
как вспомню, как по тактам высчтывали ДПФ - на корвете спектроанализатор делали - офигеваю.
А сейчас на асме даже писать лениво....

Дикое Преобразование Фурье...?

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

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

(9) а почему биржи должны бурно реагировать на решение проблемы?

(54) потому что дикое количество очень умных людей тут же бросятся ломать всякие криптографии

(51) ога. точнее, БПФ.
И ведь, млин, для развлечения писали, для интереса - рассказали нам на лекции - а мы "для души" повторили...
пиписьками мерились, у кого программа короче, у кого бОльшую частоту возьмет....

(56) раньше были времена, а теперь - моменты...

(57) Иэх,  буду на даче "понедельник" перечитывать Дождь тут обещают, да непогоду всякую - вот и буду валяться и читать

(8) а что не так с этим текстом? на ленте вобщем-то научный раздел есть http://lenta.ru/rubrics/science/science

(55) тю, я думал че-нить поглавнее случится,
а тут обыкновенный взлом. Блеать!
Ну из всего надо изготовить фомку! :(

(0) ну слава богу. теперь заживем..

пойду открою шампанскова..

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

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

(63) Ну так конечно будут еще некоторые алгоритмы шифровки сверху но это все семечки. Самое сложная первая часть.

Во общем мельчает нынче программист.:)

программасты...

(0) Ура! Я джва года ждал..