Comments 35
Нобелевскую этому парню!
Филдсовку тогда уж
Раз python то Нобелевскую по биологии
А мы точно не зря смеемся? Вдруг работает быстрее стандартных средств?
А где вы тут увидели стандартные средства? Автор измеряет три своих реализации. Первое очевидное предположение - что все измерения неверные. Второе почти столь же очевидное предположение - что две других реализации написаны не оптимально.
return sorted(set(divs)) # set() нужен, потому что по непонятной мне причине на степенях двойки появляется лишняя единица
Третье очевидное предположение - а откуда мы вообще знаем, что реализации дают верные результаты?
Я совсем не математик и не уверен полностью, но такие штуки(с категоричными заявлениями типа самый быстрый) обычно доказываются в общем виде. Ведь не доказав это математически, вы максимум можете сказать что это самый быстрый способ, который известен вам на данный момент. Причем автор вполне может быть прав и это действительно самый быстрый способ из возможных. Это, конечно, душнилово, но к такому быстро приучаешся имея даже очень небольшой опыт с научными статьями.
Посмотрели бы для чего используется разложение на множители. Я самым частым вариантом задачи встречаю атаку на RSA - найти разложение числа N=pq, где p и q - простые. Чем ваш способ поможет?
Да и вообще, чем ваш способ отличается от решета Эратосфена?
Круто, а что будет если n=10^50+151 или n=10^50-57 ?
А я почему-то думал, что в python:
10^5=15
10^10=0
10^50=56
Заголовок звучит так будто Вы собрались перевернуть мир криптографии.
На деле похоже речь идёт о школьных упражнениях на Питоне. Извините за прямоту, но так делать не надо. Старайтесь чтобы заголовок соответствовал содержанию и не производил фальшивых сенсаций.
Ну и в целом школьная домашка - не совсем контент для хабра.
Логично, что mydiv отрабатывает очень шустро. Ведь там первым этапом идёт факторизация, а выбранные «огромные» тестовые числа являются степенями 10, то есть состоят из простых делителей 2 и 5, отчего факторизация проходит за O(log N). Последующему циклу, который находит все комбинации простых множителей, приходится при этом оперировать небольшим массивом из 2*lg(n) элементов, то есть максимум 100 при n=10^50. При этом sqrtdiv честно делает sqrt(N) итераций, а prchoosediv хоть и факторизует число, но оперирует строками, а это ужасно неоптимально.
Тем не менее я не поленился и проверил работу алгоритмов на других значениях:
10000000011 = 10**10+11
mydiv: 0.0008652210235595703
sqrtdiv: 0.011649847030639648
prchoosediv: 0.000293731689453125
999999999999943 = 10**15-57
mydiv: 0.06576704978942871
sqrtdiv: 1.0241758823394775
prchoosediv: 0.025871992111206055
1000000000000157 = 10**15+157
mydiv: 0.004744768142700195
sqrtdiv: 1.0612590312957764
prchoosediv: 0.0011668205261230469
621993868801161359 = 907 * 911 * 919 * 929 * 937 * 941
mydiv: 0.0004470348358154297
sqrtdiv: 25.041913747787476
prchoosediv: 0.00017499923706054688Легко видеть, что даже неоптимальная реализация prchoosediv примерно в 3 раза быстрее, чем (неоптимальная) реализация авторского алгоритма.
Пусть попробует найти разложение такого числа:
RSA-129 = 114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541
ответ
RSA-129 = 3490529510847650949147849619903898133417764638493387843990820577
× 32769132993266709549961988190834461413177642967992942539798288533
А за разложение этого числа вообще предлагают солидный приз:
RSA-2048 = 2519590847565789349402718324004839857142928212620403202777713783604366202070 7595556264018525880784406918290641249515082189298559149176184502808489120072 8449926873928072877767359714183472702618963750149718246911650776133798590957 0009733045974880842840179742910064245869181719511874612151517265463228221686 9987549182422433637259085141865462043576798423387184774447920739934236584823 8242811981638150106748104516603773060562016196762561338441436038339044149526 3443219011465754445417842402092461651572335077870774981712577246796292638635 6373289912154831438167899885040445364023527381951378636564391212010397122822 120720357
Интересно, когда наступит момент, что пропуск подобного числа через жирную нейросеть даст результат быстрее, чем перебор.
Идея в том, что такая сеть может выявить очень неочевидные корреляции, которые может даже и не формулируемы на человеческом языке, но которые дают возможность раскладывать вот такое вот на простые множители за адекватное время.
Нейросети умножение то не осилят никогда, а вы про разложение на множители говорите
никогда
Посмотрим :) И кстати — откуда такая уверенность, что для разложения на множители нужно знать умножение? Это ведь именно для человеческого мышления так.
Зачем ей учить умножение, если по факту она просто хэш функция
ChatGPT всегда правильно решает если описать алгоритм умножения в столбик.
Да и без него часто правильно. Это как бы емержент способность. LLM не должны были иметь такую способность.
Wolfram плагин ещё в первые месяцы решил это проблему.
Как математик и ML инженер уверенно заявляю, текущие подходы в нейронках оперируют приблизительными значениями (float point), и big int math прикрутить не видится (пока) разумным
Моя мысль в том, что мы не пытаемся запустить big int math на нейронке, то есть не повторяем паттерны человеческого мышления даже на базовому уровне (вплоть до концепции чисел, математики и прочего), не копируем эту логику и воплощение этой логики в алгоритмах.
Мы берём саму задачу и заставляем эту штуку саму найти нужные способы решения. И тогда есть вероятность, что она выявит какой‑то путь, который непонятен нашему мышлению, и, возможно неформулируем вообще на человеческих языках (включая математику) и даже не подлежит какому‑либо осмыслению, то есть для человеческого мозга этот путь будет выглядеть как хаотичные действия, но этот путь будет решать задачу качественно.
DeepFake же не просчитывает распознавание лиц и рендеринг теней и подповерхностного рассеивания для реалистичной замены этих лиц так, как это делает написанный человеком алгоритм со всякими треугольниками и трасировками лучей. Но при этом справляется лучше, чем если это будут делать 3D‑моделеры (вспомним Трон: Наследие). И волосы рендерит с физикой.
Вот я думаю, что вот это вот может простираться дальше графики. Что те концепции, которые мы осмысляем нашим абстрактным мышлением (в том числе «числа», «вычисления» и прочее), могут быть «осмыслены» этим «думающим» объектом в иной, недоступной нам форме, но такой, в которой решение этих сложных задач (как разложение длинных чисел на простые множетели) окажется намного проще и быстрее.
Когда кошка прыгает на стул, она расчитывает параболическую траекторию, но при этом неспособна понять концепцию «параболы» и «траектории». Но задачу решает. Так и тут — возможно, для разложения на множители этой штуке даже «числа» понимать не нужно.
Нейронки обычно устроены по принципу обработки паттернов одинакового размера. Они не могут масштабировать свой вход. Именно потому человеческий мозг прибегает к разделению задачи на части и логике.
Вопрос правильной токенизации. Картинки или текст любого размера ты же можешь ей скормить
Именно. Только вот если стоит задача разложения на множители очень большого числа, то правильная токенизация представляет собой, внезапно, разложение этого числа на множители.
Разница состоит в том, что в рендеринге картинок/видео приблизительный результат, полученный с некоторой достаточной точностью, является приемлемым. В чисто математических задачах возможны два результата: правильный и неправильный.
Так тут тоже — нам же целые числа нужны, если ошибка будет меньше 1, то есть если весь шум будет после запятой, нас это устраивает. Даже если точность, например, ±100 — мы же можем просто после нейросети поставить классический алгоритм, который тупо проверит 200 ближайших чисел, и найдёт математически точный ответ.
Я думаю, что так и надо — нейросеть «интуитивно» говорит, что вот оно где‑то вот тут, и дальше результат добивают уже классические алгоритмы, но в предельно минимальной окрестности. В таком дуэте нейросеть даже может выдавать не одно, а несколько предполагаемых мест, где может быть ответ, и даже ошибаться в 50% случаев.
В том и дело, что ошибка ±100 никак не приближает к результату. 1000 = 2³×5³. 1001=7×11×13. Тут ошибка вообще 1. Как из одного разложения получить другое?
Я не математик, и могу ошибаться, но в моём представлении сие выглядит как‑то так.
Мы пихаем в нейросеть число большое 2048-битное число A. Она выдаёт нам набор пар m и n, в окрестности которых, по мнению нейросети, лежат искомые простые множители. При этом нейросеть неточная, и m * n не равно A — нейросеть ошибается на ±миллион.
Нетрудно банальным перебором (проходим от [m-10⁶] до [m+10⁶], если A делится без остатка на него и результат лежит в диапазоне от [n-10⁶] до [n+10⁶] — это оно) отсканировать окрестность чисел m или n и найти реально два множителя, произведение которых равно A.
Осталось проверить, являются ли оба множителя простыми.
Берём кластер из 100 видеокарт уровня RTX 5090. Кластер будет проверять числа на простоту. У кластера есть очередь. В очередь кладутся числа, и он по очереди их проверяет.
Оцениваем вероятность простоты каждого из множителей (каким‑нибудь тестом Миллера — Рабина, или чем‑то подобным, или комбинацией). Перемножаем вероятности простоты обоих множителей — получаем «рейтинг». Добавляем пару чисел в очередь на кластер, причём не в конец, а между парами чисел с похожим рейтингом. То есть вся очередь всегда отсортирована по вероятности простоты, в начале стоят пары множителей, вероятность простоты которых максимальна.
Сам кластер проверяет каждое число на простоту методом эллиптических кривых (это который https://en.wikipedia.org/wiki/Elliptic_curve_primality). Если я не ошибаюсь, этот метод спокойно жрёт числа в несколько тысяч десятичных цифр, поэтому кластер из 100 видеокарт циферки порядка 2²⁰⁴⁸ (хотя там будет наверно ближе к 2¹⁰²⁴, а это где‑то 500–700 цифр) спокойно переварит за несколько недель, может даже за одну.
Она выдаёт нам набор пар m и n, в окрестности которых, по мнению нейросети, лежат искомые простые множители.
Вот этот момент - абсолютный бред. Разложение на множители так не работает. У близких чисел, наоборот, не будет близких множителей. В этом и есть сложность.
У близких чисел, наоборот, не будет близких множителей
Не совсем понимаю, может мы говорим о разных задачах? Я говорю не об общей задаче факторизации, а о частном случае — когда мы точно знаем, что число есть произведение двух простых чисел. Не трёх и более, а именно двух.
Сетка нам выдаёт набор гипотез, мы их сначала уточняем (что делается просто), а затем полученные пары проверяем на простоту.
Когда кошка прыгает на стул, она исходит из того, что она уже прыгала на разные объекты и примерно помнит с какой силой надо прыгнуть и в каком направлении (и вполне себе может не запрыгнуть с первого раза на объект необычной формы).
На квантовых?!
Если внимательно прочитать статью, то будет ясно, что, возможно, речь идёт о самом быстром способе среди учеников своей группы. Просто автор забыл это добавить, но точно предполагал.
Не буду как Очередной комментатор издеваться над автором, но добавлю пару слов - посыл хороший, жирный плюс за то, что не побоялся быть высмеянным и интерес к теме. Желаю сохранить все выше.
А теперь должна дёгтя. Есть такое понятие, как научный подход и его не спроста нужно придерживаться (нужно исследовать, что вы не изобретаете велосипед и то, что вы используете - актуально). До нас было много дяденек и тётенек, которые умнее нас и имеют большие ресурсы для, разных исследований, поэтому мы не изобретаем велосипеды заново, а используем те, что уже есть. (В целом, умные дяденьки и тётеньки, не смогли бы тоже многого достичь, если бы не стояли на плечах предшественников).
Найдите лучше новый способ факторизации, эта штука посильнее "Фауста" Гёте будет
Прочитал заголовок, ужаснулся! Если действительно найден быстрый способ нахождения делителей - это конец всему, конец ssl, https, всему ассиметричному шифрованию. Все криптокошельки и даже банковские переводы - автоматически считаются взломаными.
А тут - пф..... А потом увидел что это что то на петухончике.
Я создал самый быстрый способ поиска делителей числа