Лучший алгоритм факторизации чисел

Skipper · 05.01.2026, 01:16

Dmitriy40 в сообщении #1714011 писал(а):

И опять не справилась за 214 кривых в 23% случаев.

Что-то мне кажется, что чем больше число, тем меньше вероятность неразложения его, количеством кривых, в приведённой выше таблице,
для поиска делителей разной длины.
Я ищу 39-значные, для чисел 78-значных (это и есть 256-битные), так вот там, округленно, для 40-значных,
хоть и всего на 1 цифру больше, кривых 2350 , с B1 равным 3 миллиона.

Я уже их штук 25 факторизовал, и И НИ ОДНОГО случая не было, чтобы программа не нашла делителей!
Так что складывается смутное впечатление, что тут не то что 23%, тут даже и 5% вероятности, близко нет.
Я уже не понимаю, когда я вообще дождусь такого случая! :)

(факторизую полупростые, содержат два рандомных простых одинаковой длины)

-- Пн янв 05, 2026 00:19:42 --

Dmitriy40 в сообщении #1714011 писал(а):

Цитата:

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

Да, если указать соответствующий pretest-ratio, то переключится

Так а какой смысл так переключаться если там заведомо не может быть минимальных делителей более чем 39-значные?
(45-значных быть не может, значит B1 будет увеличен впустую, и впустую потрачено время?)

-- Пн янв 05, 2026 00:24:50 --

Dmitriy40 в сообщении #1714009 писал(а):

ECM примерно так:
yafu-x64.exe "ecm(82049548511544548685847575944819807072619055726693,214)" -B1ecm 50000
214 здесь это количество кривых, хотите до упора - ставьте побольше (миллионы) и ждите.

Спасибо, надо будет попробовать, разные варианты..

Dmitriy40 · 05.01.2026, 11:53

Skipper в сообщении #1714025 писал(а):

Так а какой смысл так переключаться если там заведомо не может быть минимальных делителей более чем 39-значные?
(45-значных быть не может, значит B1 будет увеличен впустую, и впустую потрачено время?)

По моему значность делителя и величина B1 связаны не жестко: смотрите сами, ведь находятся же делители и при других значениях B1, как больше, так и меньше. Обоснование: вот 30 запусков для того же числа выше 82049548511544548685847575944819807072619055726693 с B1=11000, т.е. якобы недостаточно для обнаружения делителя, однако ни разу не потребовалось более 4721 кривых, а почти все были найдены и и до 2000 кривых:

код: [ скачать ] [ спрятать ]

Используется синтаксис Text

01/05/26 11:23:35, prp25 = 9061920555519325508797997 (curve 770 stg2 B1=11000 sigma=2228788259 thread=0)

01/05/26 11:23:41, prp25 = 9061920555519325508797997 (curve 812 stg2 B1=11000 sigma=3372511243 thread=2)

01/05/26 11:23:46, prp25 = 9061920555519325508797997 (curve 603 stg2 B1=11000 sigma=1019725288 thread=2)

01/05/26 11:24:10, prp25 = 9061920555519325508797997 (curve 2959 stg2 B1=11000 sigma=3318772844 thread=1)

01/05/26 11:24:17, prp25 = 9061920555519325508797997 (curve 844 stg2 B1=11000 sigma=1007381437 thread=2)

01/05/26 11:24:19, prp25 = 9061920555519325508797997 (curve 174 stg2 B1=11000 sigma=2931826254 thread=2)

01/05/26 11:24:28, prp25 = 9061920555519325508797997 (curve 1108 stg2 B1=11000 sigma=3707636703 thread=1)

01/05/26 11:24:43, prp25 = 9061920555519325508797997 (curve 1836 stg2 B1=11000 sigma=3057412360 thread=3)

01/05/26 11:24:49, prp25 = 9061920555519325508797997 (curve 745 stg2 B1=11000 sigma=3897867965 thread=0)

01/05/26 11:24:56, prp25 = 9054322205635625129311769 (curve 818 stg2 B1=11000 sigma=3138021824 thread=0)

01/05/26 11:24:58, prp25 = 9061920555519325508797997 (curve 265 stg1 B1=11000 sigma=4116638060 thread=0)

01/05/26 11:25:05, prp25 = 9054322205635625129311769 (curve 895 stg2 B1=11000 sigma=2409389884 thread=2)

01/05/26 11:25:08, prp25 = 9061920555519325508797997 (curve 369 stg2 B1=11000 sigma=3915025911 thread=0)

01/05/26 11:25:45, prp25 = 9061920555519325508797997 (curve 4610 stg2 B1=11000 sigma=1116402364 thread=1)

01/05/26 11:25:48, prp25 = 9054322205635625129311769 (curve 306 stg2 B1=11000 sigma=3377248508 thread=0)

01/05/26 11:25:54, prp25 = 9054322205635625129311769 (curve 710 stg2 B1=11000 sigma=2242231226 thread=0)

01/05/26 11:26:02, prp25 = 9054322205635625129311769 (curve 984 stg2 B1=11000 sigma=110859984 thread=1)

01/05/26 11:26:02, prp25 = 9054322205635625129311769 (curve 4 stg2 B1=11000 sigma=1010161166 thread=1)

01/05/26 11:26:18, prp25 = 9061920555519325508797997 (curve 1921 stg2 B1=11000 sigma=2368769061 thread=0)

01/05/26 11:26:33, prp25 = 9054322205635625129311769 (curve 1851 stg1 B1=11000 sigma=125710284 thread=0)

01/05/26 11:26:40, prp25 = 9061920555519325508797997 (curve 851 stg2 B1=11000 sigma=466609663 thread=3)

01/05/26 11:26:45, prp25 = 9054322205635625129311769 (curve 642 stg2 B1=11000 sigma=2454992643 thread=2)

01/05/26 11:26:48, prp25 = 9061920555519325508797997 (curve 300 stg2 B1=11000 sigma=3514710632 thread=0)

01/05/26 11:27:27, prp25 = 9061920555519325508797997 (curve 4721 stg2 B1=11000 sigma=3073297263 thread=0)

01/05/26 11:27:35, prp25 = 9061920555519325508797997 (curve 1072 stg2 B1=11000 sigma=1304829488 thread=3)

01/05/26 11:27:44, prp25 = 9054322205635625129311769 (curve 1062 stg2 B1=11000 sigma=1085427074 thread=2)

01/05/26 11:27:55, prp25 = 9061920555519325508797997 (curve 1266 stg1 B1=11000 sigma=4156869136 thread=2)

01/05/26 11:28:01, prp25 = 9054322205635625129311769 (curve 749 stg2 B1=11000 sigma=1310695057 thread=0)

01/05/26 11:28:06, prp25 = 9061920555519325508797997 (curve 612 stg2 B1=11000 sigma=2328010584 thread=0)

01/05/26 11:28:13, prp25 = 9061920555519325508797997 (curve 901 stg2 B1=11000 sigma=2037401355 thread=1)

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

Вот например 100 запусков ECM для того же числа с B1=250000 вместо 50000:

код: [ скачать ] [ спрятать ]

Используется синтаксис Text

01/05/26 10:59:51, prp25 = 9054322205635625129311769 (curve 11 stg2 B1=250000 sigma=1085692284 thread=2)

01/05/26 10:59:52, prp25 = 9061920555519325508797997 (curve 2 stg2 B1=250000 sigma=2454567377 thread=2)

01/05/26 10:59:54, prp25 = 9054322205635625129311769 (curve 13 stg2 B1=250000 sigma=802994776 thread=3)

01/05/26 10:59:55, prp25 = 9054322205635625129311769 (curve 7 stg2 B1=250000 sigma=864667320 thread=2)

01/05/26 11:00:02, prp25 = 9054322205635625129311769 (curve 65 stg2 B1=250000 sigma=668827690 thread=3)

01/05/26 11:00:04, prp25 = 9061920555519325508797997 (curve 10 stg2 B1=250000 sigma=3602597782 thread=2)

01/05/26 11:00:09, prp25 = 9061920555519325508797997 (curve 48 stg2 B1=250000 sigma=2553154689 thread=3)

01/05/26 11:00:10, prp25 = 9054322205635625129311769 (curve 10 stg2 B1=250000 sigma=3755922387 thread=2)

01/05/26 11:00:12, prp25 = 9061920555519325508797997 (curve 12 stg2 B1=250000 sigma=1073361939 thread=1)

01/05/26 11:00:14, prp25 = 9054322205635625129311769 (curve 18 stg2 B1=250000 sigma=2071262073 thread=2)

01/05/26 11:00:19, prp25 = 9054322205635625129311769 (curve 40 stg2 B1=250000 sigma=2368871630 thread=3)

01/05/26 11:00:26, prp25 = 9061920555519325508797997 (curve 67 stg2 B1=250000 sigma=4281936613 thread=0)

01/05/26 11:00:29, prp25 = 9054322205635625129311769 (curve 21 stg2 B1=250000 sigma=2505389792 thread=0)

01/05/26 11:00:35, prp25 = 9061920555519325508797997 (curve 57 stg2 B1=250000 sigma=2199010321 thread=2)

01/05/26 11:00:38, prp25 = 9054322205635625129311769 (curve 24 stg2 B1=250000 sigma=2061363308 thread=0)

01/05/26 11:00:40, prp25 = 9054322205635625129311769 (curve 12 stg2 B1=250000 sigma=3316003293 thread=2)

01/05/26 11:00:43, prp25 = 9054322205635625129311769 (curve 22 stg2 B1=250000 sigma=211556084 thread=3)

01/05/26 11:00:49, prp25 = 9061920555519325508797997 (curve 54 stg2 B1=250000 sigma=610144881 thread=2)

01/05/26 11:00:57, prp25 = 9061920555519325508797997 (curve 76 stg2 B1=250000 sigma=4230886258 thread=2)

01/05/26 11:00:58, prp25 = 9061920555519325508797997 (curve 6 stg2 B1=250000 sigma=145700160 thread=1)

01/05/26 11:00:59, prp25 = 9054322205635625129311769 (curve 5 stg2 B1=250000 sigma=3397195412 thread=2)

01/05/26 11:01:01, prp25 = 9061920555519325508797997 (curve 11 stg2 B1=250000 sigma=943208306 thread=1)

01/05/26 11:01:02, prp25 = 9061920555519325508797997 (curve 8 stg2 B1=250000 sigma=930537352 thread=3)

01/05/26 11:01:05, prp25 = 9054322205635625129311769 (curve 18 stg2 B1=250000 sigma=2515752479 thread=1)

01/05/26 11:01:06, prp25 = 9061920555519325508797997 (curve 7 stg2 B1=250000 sigma=3872551547 thread=0)

01/05/26 11:01:07, prp25 = 9054322205635625129311769 (curve 12 stg2 B1=250000 sigma=3760439108 thread=2)

01/05/26 11:01:09, prp25 = 9054322205635625129311769 (curve 11 stg2 B1=250000 sigma=630468138 thread=1)

01/05/26 11:01:20, prp25 = 9054322205635625129311769 (curve 105 stg2 B1=250000 sigma=4845419 thread=3)

01/05/26 11:01:21, prp25 = 9054322205635625129311769 (curve 5 stg2 B1=250000 sigma=514496322 thread=0)

01/05/26 11:01:24, prp25 = 9061920555519325508797997 (curve 21 stg2 B1=250000 sigma=161638497 thread=0)

01/05/26 11:02:00, prp25 = 9054322205635625129311769 (curve 2 stg1 B1=250000 sigma=3846144073 thread=3)

01/05/26 11:02:04, prp25 = 9054322205635625129311769 (curve 30 stg2 B1=250000 sigma=3922292529 thread=1)

01/05/26 11:02:05, prp25 = 9054322205635625129311769 (curve 4 stg2 B1=250000 sigma=3205493620 thread=1)

01/05/26 11:02:12, prp25 = 9054322205635625129311769 (curve 62 stg2 B1=250000 sigma=12004596 thread=3)

01/05/26 11:02:13, prp25 = 9054322205635625129311769 (curve 4 stg2 B1=250000 sigma=2931181963 thread=1)

01/05/26 11:02:15, prp25 = 9054322205635625129311769 (curve 21 stg2 B1=250000 sigma=1468147668 thread=2)

01/05/26 11:02:16, prp25 = 9061920555519325508797997 (curve 3 stg2 B1=250000 sigma=3710597911 thread=0)

01/05/26 11:02:17, prp25 = 9054322205635625129311769 (curve 9 stg2 B1=250000 sigma=4200665702 thread=3)

01/05/26 11:02:23, prp25 = 9061920555519325508797997 (curve 48 stg2 B1=250000 sigma=4169032026 thread=3)

01/05/26 11:02:26, prp25 = 9061920555519325508797997 (curve 19 stg2 B1=250000 sigma=4019402079 thread=3)

01/05/26 11:02:27, prp25 = 9061920555519325508797997 (curve 12 stg2 B1=250000 sigma=1416079282 thread=1)

01/05/26 11:02:30, prp25 = 9061920555519325508797997 (curve 17 stg2 B1=250000 sigma=4019086655 thread=1)

01/05/26 11:02:36, prp25 = 9054322205635625129311769 (curve 51 stg2 B1=250000 sigma=766445195 thread=1)

01/05/26 11:02:38, prp25 = 9054322205635625129311769 (curve 14 stg2 B1=250000 sigma=3926510716 thread=1)

01/05/26 11:02:40, prp25 = 9061920555519325508797997 (curve 11 stg2 B1=250000 sigma=1087835127 thread=1)

01/05/26 11:02:46, prp25 = 9061920555519325508797997 (curve 59 stg2 B1=250000 sigma=847009125 thread=3)

01/05/26 11:02:49, prp25 = 9054322205635625129311769 (curve 20 stg1 B1=250000 sigma=387715830 thread=3)

01/05/26 11:02:49, prp25 = 9061920555519325508797997 (curve 2 stg2 B1=250000 sigma=3261169361 thread=2)

01/05/26 11:02:50, prp25 = 9061920555519325508797997 (curve 4 stg2 B1=250000 sigma=2408071233 thread=0)

01/05/26 11:02:56, prp25 = 9061920555519325508797997 (curve 52 stg2 B1=250000 sigma=2993285683 thread=3)

01/05/26 11:03:00, prp25 = 9054322205635625129311769 (curve 39 stg2 B1=250000 sigma=262149277 thread=2)

01/05/26 11:03:01, prp25 = 9054322205635625129311769 (curve 3 stg2 B1=250000 sigma=2524844628 thread=0)

01/05/26 11:03:02, prp25 = 9054322205635625129311769 (curve 6 stg1 B1=250000 sigma=3587051056 thread=0)

01/05/26 11:03:15, prp25 = 9061920555519325508797997 (curve 115 stg2 B1=250000 sigma=1938694935 thread=0)

01/05/26 11:03:20, prp25 = 9061920555519325508797997 (curve 51 stg2 B1=250000 sigma=1040068216 thread=1)

01/05/26 11:03:23, prp25 = 9061920555519325508797997 (curve 19 stg2 B1=250000 sigma=932896861 thread=3)

01/05/26 11:03:24, prp25 = 9061920555519325508797997 (curve 7 stg2 B1=250000 sigma=1048535078 thread=0)

01/05/26 11:03:29, prp25 = 9054322205635625129311769 (curve 40 stg2 B1=250000 sigma=914565332 thread=1)

01/05/26 11:03:32, prp25 = 9054322205635625129311769 (curve 21 stg2 B1=250000 sigma=141986146 thread=3)

01/05/26 11:03:34, prp25 = 9054322205635625129311769 (curve 16 stg2 B1=250000 sigma=3653895563 thread=0)

01/05/26 11:03:35, prp25 = 9061920555519325508797997 (curve 7 stg2 B1=250000 sigma=3914181659 thread=0)

01/05/26 11:03:40, prp25 = 9061920555519325508797997 (curve 33 stg2 B1=250000 sigma=2164801221 thread=1)

01/05/26 11:03:47, prp25 = 9061920555519325508797997 (curve 72 stg2 B1=250000 sigma=3967974147 thread=2)

01/05/26 11:03:59, prp25 = 9054322205635625129311769 (curve 103 stg2 B1=250000 sigma=458496992 thread=3)

01/05/26 11:04:02, prp25 = 9061920555519325508797997 (curve 25 stg2 B1=250000 sigma=3748643032 thread=3)

01/05/26 11:04:03, prp25 = 9061920555519325508797997 (curve 7 stg2 B1=250000 sigma=675086369 thread=3)

01/05/26 11:04:04, prp25 = 9054322205635625129311769 (curve 5 stg2 B1=250000 sigma=837008744 thread=0)

01/05/26 11:04:05, prp25 = 9054322205635625129311769 (curve 5 stg2 B1=250000 sigma=2745539274 thread=3)

01/05/26 11:04:13, prp25 = 9061920555519325508797997 (curve 77 stg2 B1=250000 sigma=1898237357 thread=1)

01/05/26 11:04:18, prp25 = 9054322205635625129311769 (curve 38 stg2 B1=250000 sigma=826087153 thread=2)

01/05/26 11:04:19, prp25 = 9054322205635625129311769 (curve 3 stg2 B1=250000 sigma=1260031626 thread=2)

01/05/26 11:04:19, prp25 = 9061920555519325508797997 (curve 3 stg2 B1=250000 sigma=3714571446 thread=0)

01/05/26 11:04:20, prp25 = 9054322205635625129311769 (curve 5 stg2 B1=250000 sigma=3191525278 thread=2)

01/05/26 11:04:24, prp25 = 9054322205635625129311769 (curve 33 stg2 B1=250000 sigma=2570021142 thread=2)

01/05/26 11:04:28, prp25 = 9061920555519325508797997 (curve 34 stg2 B1=250000 sigma=64590548 thread=1)

01/05/26 11:04:29, prp25 = 9054322205635625129311769 (curve 5 stg2 B1=250000 sigma=806232008 thread=0)

01/05/26 11:04:34, prp25 = 9061920555519325508797997 (curve 43 stg2 B1=250000 sigma=2358657049 thread=1)

01/05/26 11:04:43, prp25 = 9054322205635625129311769 (curve 84 stg2 B1=250000 sigma=3230624663 thread=1)

01/05/26 11:04:45, prp25 = 9054322205635625129311769 (curve 10 stg2 B1=250000 sigma=960669440 thread=1)

01/05/26 11:04:45, prp25 = 9054322205635625129311769 (curve 2 stg1 B1=250000 sigma=568607431 thread=2)

01/05/26 11:04:50, prp25 = 9054322205635625129311769 (curve 36 stg2 B1=250000 sigma=2425871166 thread=0)

01/05/26 11:04:55, prp25 = 9061920555519325508797997 (curve 52 stg2 B1=250000 sigma=1004290243 thread=0)

01/05/26 11:04:58, prp25 = 9054322205635625129311769 (curve 27 stg2 B1=250000 sigma=3968776237 thread=0)

01/05/26 11:05:06, prp25 = 9061920555519325508797997 (curve 67 stg2 B1=250000 sigma=946561278 thread=1)

01/05/26 11:05:09, prp25 = 9054322205635625129311769 (curve 30 stg2 B1=250000 sigma=594798084 thread=3)

01/05/26 11:05:12, prp25 = 9061920555519325508797997 (curve 26 stg2 B1=250000 sigma=3335212399 thread=1)

01/05/26 11:05:15, prp25 = 9061920555519325508797997 (curve 23 stg2 B1=250000 sigma=3231912053 thread=3)

01/05/26 11:05:21, prp25 = 9054322205635625129311769 (curve 45 stg2 B1=250000 sigma=2255415705 thread=3)

01/05/26 11:05:26, prp25 = 9061920555519325508797997 (curve 42 stg2 B1=250000 sigma=149151982 thread=3)

01/05/26 11:05:28, prp25 = 9061920555519325508797997 (curve 14 stg2 B1=250000 sigma=2751084804 thread=1)

01/05/26 11:05:29, prp25 = 9061920555519325508797997 (curve 10 stg1 B1=250000 sigma=3325642711 thread=3)

01/05/26 11:05:31, prp25 = 9054322205635625129311769 (curve 11 stg2 B1=250000 sigma=4146988615 thread=1)

01/05/26 11:05:32, prp25 = 9061920555519325508797997 (curve 2 stg2 B1=250000 sigma=2609597300 thread=0)

01/05/26 11:05:32, prp25 = 9061920555519325508797997 (curve 2 stg2 B1=250000 sigma=620323433 thread=0)

01/05/26 11:05:37, prp25 = 9054322205635625129311769 (curve 43 stg1 B1=250000 sigma=379707166 thread=3)

01/05/26 11:05:39, prp25 = 9054322205635625129311769 (curve 14 stg2 B1=250000 sigma=3159163266 thread=3)

01/05/26 11:05:56, prp25 = 9061920555519325508797997 (curve 166 stg2 B1=250000 sigma=228418205 thread=2)

01/05/26 11:05:59, prp25 = 9061920555519325508797997 (curve 20 stg2 B1=250000 sigma=291105205 thread=1)

01/05/26 11:06:02, prp25 = 9061920555519325508797997 (curve 24 stg2 B1=250000 sigma=557483595 thread=2)

01/05/26 11:06:05, prp25 = 9054322205635625129311769 (curve 24 stg2 B1=250000 sigma=3235043001 thread=0)

Всего 4 раза из 100 не уложились в 84 кривых, три раза уложились в 115 кривых, и лишь один раз потребовалось 166 кривых. Сравните с почти 900 кривых для B1=50000.

30 запусков для того же числа с B1=1М:

код: [ скачать ] [ спрятать ]

Используется синтаксис Text

01/05/26 11:13:35, prp25 = 9061920555519325508797997 (curve 2 stg2 B1=1000000 sigma=3760502221 thread=2)

01/05/26 11:15:26, prp25 = 9061920555519325508797997 (curve 2 stg2 B1=1000000 sigma=782210884 thread=2)

01/05/26 11:13:37, prp25 = 9061920555519325508797997 (curve 3 stg2 B1=1000000 sigma=226253689 thread=3)

01/05/26 11:14:22, prp25 = 9054322205635625129311769 (curve 4 stg2 B1=1000000 sigma=1231894363 thread=1)

01/05/26 11:13:11, prp25 = 9054322205635625129311769 (curve 5 stg2 B1=1000000 sigma=1612453017 thread=3)

01/05/26 11:13:09, prp25 = 9061920555519325508797997 (curve 6 stg2 B1=1000000 sigma=2671302113 thread=2)

01/05/26 11:13:50, prp25 = 9054322205635625129311769 (curve 6 stg1 B1=1000000 sigma=1152147852 thread=2)

01/05/26 11:16:36, prp25 = 9054322205635625129311769 (curve 6 stg2 B1=1000000 sigma=2145651825 thread=2)

01/05/26 11:15:05, prp25 = 9054322205635625129311769 (curve 7 stg2 B1=1000000 sigma=674798042 thread=1)

01/05/26 11:16:23, prp25 = 9054322205635625129311769 (curve 9 stg2 B1=1000000 sigma=1231180881 thread=3)

01/05/26 11:15:11, prp25 = 9054322205635625129311769 (curve 10 stg2 B1=1000000 sigma=17214327 thread=2)

01/05/26 11:16:41, prp25 = 9061920555519325508797997 (curve 10 stg2 B1=1000000 sigma=21932978 thread=2)

01/05/26 11:16:46, prp25 = 9061920555519325508797997 (curve 10 stg2 B1=1000000 sigma=228140109 thread=1)

01/05/26 11:15:17, prp25 = 9061920555519325508797997 (curve 11 stg2 B1=1000000 sigma=4215558281 thread=3)

01/05/26 11:14:28, prp25 = 9061920555519325508797997 (curve 13 stg2 B1=1000000 sigma=528955476 thread=1)

01/05/26 11:15:23, prp25 = 9054322205635625129311769 (curve 13 stg2 B1=1000000 sigma=1199354779 thread=2)

01/05/26 11:13:56, prp25 = 9054322205635625129311769 (curve 14 stg1 B1=1000000 sigma=2926036371 thread=0)

01/05/26 11:16:13, prp25 = 9061920555519325508797997 (curve 14 stg1 B1=1000000 sigma=74729425 thread=2)

01/05/26 11:16:20, prp25 = 9061920555519325508797997 (curve 14 stg2 B1=1000000 sigma=1395589145 thread=3)

01/05/26 11:16:31, prp25 = 9061920555519325508797997 (curve 16 stg2 B1=1000000 sigma=699272173 thread=2)

01/05/26 11:13:20, prp25 = 9061920555519325508797997 (curve 18 stg1 B1=1000000 sigma=3440093269 thread=3)

01/05/26 11:16:06, prp25 = 9061920555519325508797997 (curve 18 stg2 B1=1000000 sigma=29389588 thread=1)

01/05/26 11:13:46, prp25 = 9054322205635625129311769 (curve 20 stg2 B1=1000000 sigma=1472993899 thread=0)

01/05/26 11:14:07, prp25 = 9061920555519325508797997 (curve 23 stg2 B1=1000000 sigma=2098850188 thread=0)

01/05/26 11:13:32, prp25 = 9061920555519325508797997 (curve 29 stg2 B1=1000000 sigma=920833640 thread=3)

01/05/26 11:14:19, prp25 = 9054322205635625129311769 (curve 30 stg2 B1=1000000 sigma=889152238 thread=0)

01/05/26 11:15:01, prp25 = 9061920555519325508797997 (curve 30 stg2 B1=1000000 sigma=2202773671 thread=2)

01/05/26 11:15:39, prp25 = 9061920555519325508797997 (curve 33 stg2 B1=1000000 sigma=1686991267 thread=3)

01/05/26 11:15:58, prp25 = 9054322205635625129311769 (curve 47 stg2 B1=1000000 sigma=1222987905 thread=3)

01/05/26 11:14:48, prp25 = 9061920555519325508797997 (curve 50 stg2 B1=1000000 sigma=3778191881 thread=0)

Ни разу не потребовалось более 50 кривых, и лишь 2 раза больше 33 кривых.
Причём такой поиск оказался даже быстрее предыдущего: 1м13с на 30 итераций против 1м33с тех 30 первых итераций. На самом деле этот даже ещё чуть быстрее потому что нередко не нужно было запускать все 4 потока, делитель находился прямо на первой-второй кривой в каком-нибудь потоке.

Почему сразу не ставят B1 в миллионы или миллиарды? Так чем больше B1, тем медленнее расчёт каждой кривой, потому и не ставят, есть вполне обоснованная надежда что делитель будет найден и при меньших B1. И выбор количества кривых и величины B1 думаю очень даже обоснован. И вряд ли именно для проверки точно полупростых, как Вы тут накинулись, всё же программа универсальная, а не оптимизирована для взлома RSA.

Skipper в сообщении #1714025 писал(а):

Я уже их штук 25 факторизовал, и И НИ ОДНОГО случая не было, чтобы программа не нашла делителей!
Так что складывается смутное впечатление, что тут не то что 23%, тут даже и 5% вероятности, близко нет.
Я уже не понимаю, когда я вообще дождусь такого случая! :)

Это говорит скорее о плохом выборе факторизуемых чисел, чем о качестве ECM. Я же показывал выше как из 100 разных чисел 23 не уложились в расчётные 214 кривых. Впрочем, если взять делители не 25 цифр, а 24, может вероятность и упадёт ...

Skipper · 05.01.2026, 13:42

Dmitriy40 в сообщении #1714040 писал(а):

Почему сразу не ставят B1 в миллионы или миллиарды? Так чем больше B1, тем медленнее расчёт каждой кривой, потому и не ставят, есть вполне обоснованная надежда что делитель будет найден и при меньших B1. И выбор количества кривых и величины B1 думаю очень даже обоснован. И вряд ли именно для проверки точно полупростых, как Вы тут накинулись, всё же программа универсальная, а не оптимизирована для взлома RSA.

Вот это и интересно, если считать, что число полупростое, с делителями одинаковой длины (т.е. порядка корня квадратного), то видимо, в таком случае есть какие то другие: 1) оптимальные B1 и 2) число кривых, для любой длины ("значности") делителей, хотелось это узнать, или как то вывести, если нет точной информации,

-- Пн янв 05, 2026 12:48:03 --

Dmitriy40 в сообщении #1714040 писал(а):

Это говорит скорее о плохом выборе факторизуемых чисел,

Рандомные они, сгенерированные с помощью т.н. "криптостойкого" генератора случайных байт, и разбавленного xor-ом, с нагенерированным белым шумом с "человеческой энтропией" (порабабанил пальцами по клавиатуре, и прочитал это всё в байты,
затем сдвинул на шаг вперед для каждого значения, по алгоритму линейно-конгруэнтного метода).
То есть фактически- настоящий белый шум, в который могло попасть равновероятно, любое число.
Уже кстати, 30 штук я их факторизовал, до сих пор нет случая, чтобы не был найден делитель, пройдя "табличные" 2350 кривые,
для поиска делителей 40-значных (B1 равен 3 миллиона), притом что у меня делители 39-значные, факторизуемые числа-
78-значные- это 256-битные числа,

Цитата:

40 3e6 5.7e9 2541 2350 [D(6)]

-- Пн янв 05, 2026 13:13:29 --

Dmitriy40 в сообщении #1714040 писал(а):

Впрочем, если взять делители не 25 цифр, а 24, может вероятность и упадёт ...

Интересно, выясню. Сейчас буду пробовать факторизовать не 256-битные числа, а 264-битные.

Все они в десятичной записи действительно 80-значные, ещё и с "2" начинаются,
(в отличие от 256-битных, которые были 78-значными, и начинались с "1").

Все делители от моих 264-битных полупростых, будут действительно 40-значные и начинаться с "4" или "5",
(в отличие от делителей 256-битных полупростых, которые были 39-значными, и начинались с "2" или "3").

Если там есть 23% вероятность неразложения 2350 кривыми, то из десятка, два-три таких числа должны появиться,

Dmitriy40 · 05.01.2026, 19:36

Запустил у себя тест, случайные 39+39=78 цифр, B1=3М, 2350 кривых, 17 итераций: >2350, 2269, 2123, 1323, 1301, 1121, 818, 777, 668, 395, 265, 213, 87, 37, 37, 33, 29.
Всего один раз не хватило, на числе:
816961596487035153808521370726340812479135539732870244997478848571366454193709 = 902050502583221677542019905166933490831 * 905671682624736010363440819360298942339
Да, на 37% ну совсем не похоже.

И мне всё же непонятно зачем страдать такой фигнёй: ECM это число не разложил за 1.25 часа, а SIQS разложил за 24 секунды.

Skipper · 05.01.2026, 20:17

Dmitriy40 в сообщении #1714073 писал(а):

И мне всё же непонятно зачем страдать такой фигнёй: ECM это число не разложил за 1.25 часа, а SIQS разложил за 24 секунды.

Так я хочу сначала изучить ECM . А то, что нет 37%, так это я и хочу проанализировать статистически:
возможно, верно что,

Skipper в сообщении #1714025 писал(а):

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

Skipper в сообщении #1713986 писал(а):

digits D optimal B1 default B2 expected curves
N(B1,B2,D)
-power 1 default poly
20 11e3 1.9e6 74 74 [x^1]
25 5e4 1.3e7 221 214 [x^2]
30 25e4 1.3e8 453 430 [D(3)]
35 1e6 1.0e9 984 904 [D(6)]
40 3e6 5.7e9 2541 2350 [D(6)]
45 11e6 3.5e10 4949 4480 [D(12)]
50 43e6 2.4e11 8266 7553 [D(12)]
55 11e7 7.8e11 20158 17769 [D(30)]
60 26e7 3.2e12 47173 42017 [D(30)]
65 85e7 1.6e13 77666 69408 [D(30)]

Table 1: optimal B1 and expected number of curves to find a
factor of D digits with GMP-ECM.

mathpath · 06.01.2026, 13:36

Dmitriy40 в сообщении #1714073 писал(а):

И мне всё же непонятно зачем страдать такой фигнёй: ECM это число не разложил за 1.25 часа, а SIQS разложил за 24 секунды.

И неудивительно
SIQS — детерминированный алгоритм, а ECM — вероятностный алгоритм.
Если SIQS запустить и дать ему достаточно времени и памяти, он гарантированно найдет полную факторизацию числа.
ECM — вероятностный алгоритм. Он может неожиданно найти делитель очень быстро (если повезет с выбором кривой), в то время как SIQS всегда требует выполнения полного объема предсказуемой работы.

Dmitriy40 · 06.01.2026, 13:58

mathpath
Я это понимаю.
Непонятно зачем часами использовать ECM для больших чисел если разобраться как работает ECM можно и с сильно меньшими.

Skipper · 06.01.2026, 14:02

mathpath в сообщении #1714130 писал(а):

ECM — вероятностный алгоритм. Он может неожиданно найти делитель очень быстро (если повезет с выбором кривой)

Ну, как выше установили, если факторизуемое число имеет наименьший делитель порядка корня квадратного (в таком случае оно полупростое, всего 2 делителя одинаковой длины в записи), то ECM может сработать и в 200-400 раз медленнее чем SIQS.
Если минимальный делитель- порядка корня кубического, то есть по длине короче в 3 раза (в таком случае делителей может быть и 3,
а может быть 2, один в два раза короче другого, например 60-значное число, с делителями 20-значным, и 40-значным),
то ECM уже работает примерно с такой же скоростью как и SIQS ("в среднем", при большой выборке тестов),
а если минимальный делитель ещё меньше, то ECM становится самым универсальным и лучшим алгоритмом.
Для абсолютного большинства факторизуемых чисел.

Легко задать например 4000-битное число, которое содержит рандомный 200-битный делитель, и
рандомный 3800-битный делитель.
Его только с помощью ECM,и можно будет факторизовать, в то время как на факторизацию методами SIQS и GNFS,
и всеми остальными методами, просто за время существования Вселенной, за много миллиардов лет, не факторизуешь
всеми компьютерами Земли..

-- Вт янв 06, 2026 13:03:05 --

Dmitriy40 в сообщении #1714134 писал(а):

Непонятно зачем часами использовать ECM для больших чисел если разобраться как работает ECM можно и с сильно меньшими.

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

mathpath · 07.01.2026, 11:18

Я сделал рефакторинг питоновской реализации SIQS, которая лежит тут (автор - Stephan Kollmann):
https://github.com/skollmann/PyFactorise/tree/master
Я переписал это на гоу.
На все про все у меня ушло времени где-то с неделю.
Технология рефакторинга у меня была следующая: я брал какую-то функцию из исходного питоновского файла и копипастил ее прямо в чат дипсика и говорил - перепиши ее на гоу.
Дипсик как правило дает результат почти мгновенно.
Затем эта функция на гоу тестируется, при этом может оказаться, что она не рабочая, можно попросить дипсик переписать ее с указанием места, он с радостью признается в ошибке и тут же ее "переписывает".
Короче, где-то процентов на 80 рефакторинг делается дипсиком, а остальное доводится вручную напильником.

Рефакторинг с питона на гоу дал в этом проекте ускорение в скорости факторизации на порядок.
Причем я постоянно говорил дипсику - переписывай по возможности максимально близко к исходному питоновскому тексту, используя в гоу при этом тип данных big.int.
Его можно также заставить делать оптимизацию не только на уровне языка, но и на уровне математики в самом базовом алгоритме, но до этого у меня пока руки не дошли, и там наверняка еще будет прибавка в скорости.
С питона на си я не пробовал переписывать в силу того, что между питоном и си пропасть, но никто конечно не запрещает это делать.
В гоу базовые структуры имеют много общего с питоновскими, поэтому при переносе программы ломать особо ничего не приходится.

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

Skipper · 07.01.2026, 17:26

Skipper в сообщении #1713986 писал(а):

digits D optimal B1 default B2 expected curves
N(B1,B2,D)
-power 1 default poly
20 11e3 1.9e6 74 74 [x^1]
25 5e4 1.3e7 221 214 [x^2]
30 25e4 1.3e8 453 430 [D(3)]
35 1e6 1.0e9 984 904 [D(6)]
40 3e6 5.7e9 2541 2350 [D(6)]
45 11e6 3.5e10 4949 4480 [D(12)]
50 43e6 2.4e11 8266 7553 [D(12)]
55 11e7 7.8e11 20158 17769 [D(30)]
60 26e7 3.2e12 47173 42017 [D(30)]
65 85e7 1.6e13 77666 69408 [D(30)]

Table 1: optimal B1 and expected number of curves to find a
factor of D digits with GMP-ECM.

Подкажите, по каким формулам тут считается "оптимальное" количество кривых? Вот для поиска 65-значных делителей, например, указано, что оптимальное количество 69408 кривых,
для поиска 60-значных делителей: 42017 кривых, для поиска 40-значных делителей: 2350 кривых, для поиска 30-значных делителей: 430 кривых

mathpath · 07.01.2026, 19:11

Цитата:

Подкажите, по каким формулам тут считается "оптимальное" количество кривых? Вот для поиска 65-значных делителей, например, указано, что оптимальное количество 69408 кривых,
для поиска 60-значных делителей: 42017 кривых, для поиска 40-значных делителей: 2350 кривых, для поиска 30-значных делителей: 430 кривых

Оптимально - 100 тысяч
Рабочий диапазон - 50 - 200 тысяч
Еще это сильно зависит от параметра B1
В данном случае оптимальное значение B1 - 85 миллионов
Натуральный логарифм 65-значного числа примерно равен 150
Натуральный логарифм 85 миллионов примерно равен 18
Отношение первого логарифма ко второму примерно равно 8
Восемь в восьмой степени - это примерно 30 миллионов - таково значение B1

Skipper · 07.01.2026, 19:19