Какой самый быстрый алгоритм факторизации?
Я написал программу, которая пытается найти Дружных Паров. Для этого необходимо найти суммы правильных делителей чисел.
Вот мой ток sumOfDivisors() метод:
int sumOfDivisors(int n)
{
int sum = 1;
int bound = (int) sqrt(n);
for(int i = 2; i <= 1 + bound; i++)
{
if (n % i == 0)
sum = sum + i + n / i;
}
return sum;
}
Поэтому мне нужно много факторизовать, и это становится настоящим узким местом в моем приложении. Я набрал огромное число в MAPLE, и оно безумно быстро его разложило.
Что является одним из самых быстрых алгоритмов факторизации?
11 ответов
Вытащил прямо из моего ответа на этот другой вопрос.
Метод будет работать, но будет медленным. "Насколько велики твои числа?" определяет метод для использования:
- Менее 2^16 или около того: таблица поиска.
- Менее 2^70 или около того: модификация Ричарда Брента алгоритма ро Полларда.
- Менее 10^50: факторизация эллиптической кривой Ленстры
- Менее 10 ^ 100: квадратичное сито
- Более 10 ^ 100: сито поля общего номера
Алгоритм Шора: http://en.wikipedia.org/wiki/Shor%27s_algorithm
Конечно, вам нужен квантовый компьютер, хотя:D
Вопрос в заголовке (и в последней строке), похоже, имеет мало общего с фактическим содержанием вопроса. Если вы пытаетесь найти дружественные пары или вычисляете сумму делителей для многих чисел, то раздельное разложение каждого числа (даже с самым быстрым из возможных алгоритмов) - абсолютно неэффективный способ сделать это.
Функция суммы делителей, σ(n) = (sum of divisors of n), является мультипликативной функцией: для относительно простых m и n имеем σ(mn) = σ(m)σ(n), так
σ (p1k1… prkr) = [(p1k1+1-1) / (p1-1)]… [(prkr+1-1) / (pr-1)].
Таким образом, вы бы использовали любое простое сито (например, расширенную версию сита Эратосфена), чтобы найти простые числа до nи, в процессе, разложение всех чисел до n. (Например, когда вы делаете сито, сохраняйте наименьший простой множитель каждого n. Затем вы можете позже разложить любое число n путем итерации.) Это будет быстрее (в целом), чем использование любого отдельного алгоритма факторизации несколько раз.
Кстати: несколько известных списков дружных пар уже существуют (см., Например, здесь и ссылки на MathWorld) - так вы пытаетесь продлить запись или делаете это просто для удовольствия?
Я бы предложил начать с того же алгоритма, что и в Maple, Quadratic Sieve.
- Выберите нечетное число n для разложения,
- Выберите натуральное число k,
- Поиск по всем p <= k, так что k^2 не является конгруэнтным (n mod p) для получения факторной базы B = p1, p2,..., pt,
- Начиная с r > floor (n), ищите не менее t+1 значений, так что y^2 = r^2 - n имеют только факторы B,
- Для каждого только что вычисленного y1, y2,..., y (t+1) вы генерируете вектор v(yi) = (e1, e2, ..., et), где ei вычисляется путем уменьшения по модулю 2 показателя степени pi в ии,
- Используйте метод исключения Гаусса, чтобы найти несколько векторов, которые сложены вместе и дают нулевой вектор.
- Установите x как произведение ri, связанного с yi, найденным на предыдущем шаге, и установите y как p1^a * p2^b * p3^c * .. * pt^z, где показатели степени - половина показателей, найденных в факторизации уг
- Вычислите d = mcd(xy, n), если 1
то d является нетривиальным множителем n, в противном случае начните с шага 2, выбирая большее k.
Проблема этих алгоритмов состоит в том, что они действительно подразумевают много теории в численном исчислении.
Это статья о целочисленной факторизации в Maple.
"Исходя из некоторых очень простых инструкций -" ускорить целочисленную факторизацию в Maple "- мы реализовали алгоритм факторинга Quadratic Sieve в комбинации Maple и C..."
Более 2015 C++ версия 227 реализация таблицы поиска для 1 ГБ памяти:
#include <iostream.h> // cerr, cout, and NULL
#include <string.h> // memcpy()
#define uint unsigned __int32
uint *factors;
const uint MAX_F=134217728; // 2^27
void buildFactors(){
factors=new (nothrow) uint [(MAX_F+1)*2]; // 4 * 2 * 2^27 = 2^30 = 1GB
if(factors==NULL)return; // not able to allocate enough free memory
int i;
for(i=0;i<(MAX_F+1)*2;i++)factors[i]=0;
//Sieve of Eratosthenese
factors[1*2]=1;
factors[1*2+1]=1;
for(i=2;i*i<=MAX_F;i++){
for(;factors[i*2] && i*i<=MAX_F;i++);
factors[i*2]=1;
factors[i*2+1]=i;
for(int j=2;i*j<=MAX_F;j++){
factors[i*j*2]=i;
factors[i*j*2+1]=j;
}
}
for(;i<=MAX_F;i++){
for(;i<=MAX_F && factors[i*2];i++);
if(i>MAX_F)return;
factors[i*2]=1;
factors[i*2+1]=i;
}
}
uint * factor(uint x, int &factorCount){
if(x > MAX_F){factorCount=-1;return NULL;}
uint tmp[70], at=x; int i=0;
while(factors[at*2]>1){
tmp[i++]=factors[at*2];
cout<<"at:"<<at<<" tmp:"<<tmp[i-1]<<endl;
at=factors[at*2+1];
}
if(i==0){
cout<<"at:"<<x<<" tmp:1"<<endl;
tmp[i++]=1;
tmp[i++]=x;
}else{
cout<<"at:"<<at<<" tmp:1"<<endl;
tmp[i++]=at;
}
factorCount=i;
uint *ret=new (nothrow) uint [factorCount];
if(ret!=NULL)
memcpy(ret, tmp, sizeof(uint)*factorCount);
return ret;
}
void main(){
cout<<"Loading factors lookup table"<<endl;
buildFactors(); if(factors==NULL){cerr<<"Need 1GB block of free memory"<<endl;return;}
int size;
uint x=30030;
cout<<"\nFactoring: "<<x<<endl;
uint *f=factor(x,size);
if(size<0){cerr<<x<<" is too big to factor. Choose a number between 1 and "<<MAX_F<<endl;return;}
else if(f==NULL){cerr<<"ran out of memory trying to factor "<<x<<endl;return;}
cout<<"\nThe factors of: "<<x<<" {"<<f[0];
for(int i=1;i<size;i++)
cout<<", "<<f[i];
cout<<"}"<<endl;
delete [] f;
x=30637;
cout<<"\nFactoring: "<<x<<endl;
f=factor(x,size);
cout<<"\nThe factors of: "<<x<<" {"<<f[0];
for(int i=1;i<size;i++)
cout<<", "<<f[i];
cout<<"}"<<endl;
delete [] f;
delete [] factors;
}
Обновление: или пожертвовав некоторой простотой ради чуть большего расстояния чуть позже 228
#include <iostream.h> // cerr, cout, and NULL
#include <string.h> // memcpy(), memset()
//#define dbg(A) A
#ifndef dbg
#define dbg(A)
#endif
#define uint unsigned __int32
#define uint8 unsigned __int8
#define uint16 unsigned __int16
uint * factors;
uint8 *factors08;
uint16 *factors16;
uint *factors32;
const uint LIMIT_16 = 514; // First 16-bit factor, 514 = 2*257
const uint LIMIT_32 = 131074;// First 32-bit factor, 131074 = 2*65537
const uint MAX_FACTOR = 268501119;
//const uint64 LIMIT_64 = 8,589,934,594; // First 64-bit factor, 2^33+1
const uint TABLE_SIZE = 268435456; // 2^28 => 4 * 2^28 = 2^30 = 1GB 32-bit table
const uint o08=1, o16=257 ,o32=65665; //o64=4294934465
// TableSize = 2^37 => 8 * 2^37 = 2^40 1TB 64-bit table
// => MaxFactor = 141,733,953,600
/* Layout of factors[] array
* Indicies(32-bit) i Value Size AFactorOf(i)
* ---------------- ------ ---------- ----------------
* factors[0..128] [1..513] 8-bit factors08[i-o08]
* factors[129..65408] [514..131073] 16-bit factors16[i-o16]
* factors[65409..268435455] [131074..268501119] 32-bit factors32[i-o32]
*
* Note: stopping at i*i causes AFactorOf(i) to not always be LargestFactor(i)
*/
void buildFactors(){
dbg(cout<<"Allocating RAM"<<endl;)
factors=new (nothrow) uint [TABLE_SIZE]; // 4 * 2^28 = 2^30 = 1GB
if(factors==NULL)return; // not able to allocate enough free memory
uint i,j;
factors08 = (uint8 *)factors;
factors16 = (uint16 *)factors;
factors32 = factors;
dbg(cout<<"Zeroing RAM"<<endl;)
memset(factors,0,sizeof(uint)*TABLE_SIZE);
//for(i=0;i<TABLE_SIZE;i++)factors[i]=0;
//Sieve of Eratosthenese
//8-bit values
dbg(cout<<"Setting: 8-Bit Values"<<endl;)
factors08[1-o08]=1;
for(i=2;i*i<LIMIT_16;i++){
for(;factors08[i-o08] && i*i<LIMIT_16;i++);
dbg(cout<<"Filtering: "<<i<<endl;)
factors08[i-o08]=1;
for(j=2;i*j<LIMIT_16;j++)factors08[i*j-o08]=i;
for(;i*j<LIMIT_32;j++)factors16[i*j-o16]=i;
for(;i*j<=MAX_FACTOR;j++)factors32[i*j-o32]=i;
}
for(;i<LIMIT_16;i++){
for(;i<LIMIT_16 && factors08[i-o08];i++);
dbg(cout<<"Filtering: "<<i<<endl;)
if(i<LIMIT_16){
factors08[i-o08]=1;
j=LIMIT_16/i+(LIMIT_16%i>0);
for(;i*j<LIMIT_32;j++)factors16[i*j-o16]=i;
for(;i*j<=MAX_FACTOR;j++)factors32[i*j-o32]=i;
}
}i--;
dbg(cout<<"Setting: 16-Bit Values"<<endl;)
//16-bit values
for(;i*i<LIMIT_32;i++){
for(;factors16[i-o16] && i*i<LIMIT_32;i++);
factors16[i-o16]=1;
for(j=2;i*j<LIMIT_32;j++)factors16[i*j-o16]=i;
for(;i*j<=MAX_FACTOR;j++)factors32[i*j-o32]=i;
}
for(;i<LIMIT_32;i++){
for(;i<LIMIT_32 && factors16[i-o16];i++);
if(i<LIMIT_32){
factors16[i-o16]=1;
j=LIMIT_32/i+(LIMIT_32%i>0);
for(;i*j<=MAX_FACTOR;j++)factors32[i*j-o32]=i;
}
}i--;
dbg(cout<<"Setting: 32-Bit Values"<<endl;)
//32-bit values
for(;i*i<=MAX_FACTOR;i++){
for(;factors32[i-o32] && i*i<=MAX_FACTOR;i++);
factors32[i-o32]=1;
for(j=2;i*j<=MAX_FACTOR;j++)factors32[i*j-o32]=i;
}
for(;i<=MAX_FACTOR;i++){
for(;i<=MAX_FACTOR && factors32[i-o32];i++);
if(i>MAX_FACTOR)return;
factors32[i-o32]=1;
}
}
uint * factor(uint x, int &factorCount){
if(x > MAX_FACTOR){factorCount=-1;return NULL;}
uint tmp[70], at=x; int i=0;
while(at>=LIMIT_32 && factors32[at-o32]>1){
tmp[i++]=factors32[at-o32];
dbg(cout<<"at32:"<<at<<" tmp:"<<tmp[i-1]<<endl;)
at/=tmp[i-1];
}
if(at<LIMIT_32){
while(at>=LIMIT_16 && factors16[at-o16]>1){
tmp[i++]=factors16[at-o16];
dbg(cout<<"at16:"<<at<<" tmp:"<<tmp[i-1]<<endl;)
at/=tmp[i-1];
}
if(at<LIMIT_16){
while(factors08[at-o08]>1){
tmp[i++]=factors08[at-o08];
dbg(cout<<"at08:"<<at<<" tmp:"<<tmp[i-1]<<endl;)
at/=tmp[i-1];
}
}
}
if(i==0){
dbg(cout<<"at:"<<x<<" tmp:1"<<endl;)
tmp[i++]=1;
tmp[i++]=x;
}else{
dbg(cout<<"at:"<<at<<" tmp:1"<<endl;)
tmp[i++]=at;
}
factorCount=i;
uint *ret=new (nothrow) uint [factorCount];
if(ret!=NULL)
memcpy(ret, tmp, sizeof(uint)*factorCount);
return ret;
}
uint AFactorOf(uint x){
if(x > MAX_FACTOR)return -1;
if(x < LIMIT_16) return factors08[x-o08];
if(x < LIMIT_32) return factors16[x-o16];
return factors32[x-o32];
}
void main(){
cout<<"Loading factors lookup table"<<endl;
buildFactors(); if(factors==NULL){cerr<<"Need 1GB block of free memory"<<endl;return;}
int size;
uint x=13855127;//25255230;//30030;
cout<<"\nFactoring: "<<x<<endl;
uint *f=factor(x,size);
if(size<0){cerr<<x<<" is too big to factor. Choose a number between 1 and "<<MAX_FACTOR<<endl;return;}
else if(f==NULL){cerr<<"ran out of memory trying to factor "<<x<<endl;return;}
cout<<"\nThe factors of: "<<x<<" {"<<f[0];
for(int i=1;i<size;i++)
cout<<", "<<f[i];
cout<<"}"<<endl;
delete [] f;
x=30637;
cout<<"\nFactoring: "<<x<<endl;
f=factor(x,size);
cout<<"\nThe factors of: "<<x<<" {"<<f[0];
for(int i=1;i<size;i++)
cout<<", "<<f[i];
cout<<"}"<<endl;
delete [] f;
delete [] factors;
}
Зависит от того, насколько велики ваши цифры. Если вы ищете дружественные пары, вы делаете много факторизаций, поэтому ключом может быть не в том, чтобы как можно быстрее вычислять фактор, а в том, чтобы распределить как можно больше работы между различными вызовами. Чтобы ускорить пробное деление, вы можете посмотреть на запоминание и / или предварительное вычисление простых чисел до квадратного корня из наибольшего числа, которое вас волнует. Проще получить первичную факторизацию, а затем вычислить сумму всех факторов из этого, чем выполнить цикл до sqrt (n) для каждого числа.
Если вы ищете действительно большие дружные пары, скажем, больше, чем 2^64, то на небольшом количестве машин вы не сможете сделать это, разложив каждое число независимо от того, насколько быстра ваша разложение. Сокращения, которые вы используете для поиска кандидатов, могут помочь вам их учесть.
Это важная открытая математическая проблема с 2020 года.
Другие ответили с практической точки зрения, и существует высокая вероятность того, что для размеров проблем, встречающихся на практике, эти алгоритмы близки к оптимальным.
Однако я также хотел бы подчеркнуть, что более общая математическая проблема (в асимптотической сложности вычислений, т.е. когда количество бит стремится к бесконечности) полностью не решена.
Никто никогда не мог доказать, каково минимальное оптимальное время для максимально быстрого алгоритма.
Это показано на странице Википедии: https://en.wikipedia.org/wiki/Integer_factorization. Алгоритм также фигурирует на странице Wiki "Список нерешенных проблем в информатике": https://en.wikipedia.org/wiki/List_of_unsolved_problems_in_computer_science
Все, что мы знаем, это то, что лучшее, что у нас есть в настоящее время, - это сито общих чисел. А до 2018 года у нас не было даже неэвристического доказательства его сложности.
По состоянию на 2020 год мы даже не доказали, является ли проблема NP-полной или нет (хотя, очевидно, это NP, поскольку все, что вам нужно сделать, чтобы проверить решение, - это умножить числа)! Хотя многие ожидают, что он будет NP-полным. Мы не можем быть настолько плохими в поиске алгоритмов, не так ли?
Конечно, существует алгоритм HMA профессора Хэла Махутана (февраль 2021 г.), который находится на пороге исследования факторизации.
Решение для двух больших простых чисел для открытого ключа выглядит следующим образом ...
Любой AxB = открытый ключ можно нарисовать на положительных осях X и Y, которые образуют непрерывную кривую, где все нецелые факторы решают для открытого ключа. Конечно, это бесполезно, это просто наблюдение на данный момент.
Понимание Хэла таково: если мы настаиваем на том, что нас интересуют только точки, в которых A является целым числом, особенно точки, которые B представляет, когда A является целым.
Предыдущие попытки с этим подходом потерпели неудачу, когда математики боролись с очевидной случайностью остатка B или, по крайней мере, с отсутствием предсказуемости.
Хэл говорит, что предсказуемость универсальна для любого открытого ключа при одинаковом соотношении a / b. В основном, когда для анализа представляется серия различных открытых ключей, все они могут обрабатываться одинаково, при условии, что они используют одну и ту же точку во время обработки, где a / b постоянны, т. Е. Они имеют одну и ту же касательную.
Взгляните на этот набросок, который я нарисовал, чтобы попытаться объяснить, что здесь происходит у профессора Махутана.
Итак, вот гений Хэла. Hal использует мощные суперкомпьютеры для создания серии хэш-таблиц (на диаграмме Q, R, S и T). На трех кривых A x B = Key слева вы можете видеть, что все они имеют общие касательные T и S (единственные выделенные там), но диаграмма показывает, что при любом открытом ключе в области кривой, где касательная такая же, то вы можете совместно использовать хэш-таблицы, которые управляют этим регионом.
Просто техническое примечание, очевидно, что в кривой AxB= Key все постоянно меняется по мере изменения значений AxB, поэтому теоретически общий касательный, который отображается в хеш-таблицу, устареет, но интересная вещь это то, что с действительно большими ключами (по иронии судьбы, это облегчает их взлом, потому что они разделяют более длинные прогоны, где полезна хеш-таблица). Так что это отличная новость, поскольку ожидается, что размеры ключей будут намного больше по мере ускорения прогресса в факторизации и вычислениях. На самом деле происходит то, что предсказуемость хеш-таблицы буквально «выходит из фокуса», когда касательные, к которым они применяются, начинают расходиться. К счастью, это не проблема, потому что вы переходите к следующей хэш-таблице, которая соответствующим образом сопоставлена с новым Tangent.
Чтобы прояснить, все когда-либо сгенерированные открытые ключи всегда будут использовать один и тот же набор хэш-таблиц, так что это своего рода одноразовое вложение, которое можно хранить в сети, буквально миллионы терабайт поисковых данных, поскольку все ключи подчиняются одному и тому же тангенциальные отношения.
Итак, что делают хэш-таблицы для ускорения поиска простых чисел. Хэш-таблицы индексируются с остатком, когда открытый ключ делится на B. По сути, Хэл говорит, что для всех ключей можно найти любое соотношение A x B. Единственное различие между разными кривыми, имеющими одну и ту же касательную, состоит в том, что для них требуется другое смещение, определяемое «контрольной кривой». «Контрольная кривая» - это любая произвольная кривая, для которой вы создаете соответствующие коэффициенты. Скажем, для «Контрольной кривой» ключ равен 15, а отображаемая касательная - когда B = 5, поэтому A равно 3, а остаток равен нулю. В другом отображении с той же Касательной, скажем, теперь Ключ равен 16. Нам нужно найти ту же Касательную, которая лежит в точке 5,33 для B и 3,2 для A. Таким образом, остаток для A равен 0,2,поэтому открытый ключ 16 может использовать ту же таблицу поиска, что и 15, при условии, что он соответствующим образом смещен на .2.
Так что в хэш-таблицах? Индексируется по смещению, и значение всегда возвращает расстояние вдоль кривой AxB, для которого вы не найдете другого целого числа B. Хэл говорит, что можно безопасно прыгать вперед и не проверять, являются ли эти числа факторами. И это в основном все. Хэл пробивает дыры в кривой, которые никогда не нужно проверять, и это только ускоряет всю игру.
Спасибо, профессор Махутан!
Очень интересный вопрос, спасибо!
Потратил целый день на программирование кода C++ с нуля, который реализует очень быстрый и поиск
Известно, что метод очень и очень быстрый. Этот метод ECM, если он хорошо оптимизирован, позволяет легко за одну секунду найти множители даже 100-битного числа (состоящего из двух 50-битных простых чисел). Он медленнее только Quadratic Sieve и GNFS.
Как вы сказали, вы ищете 25-значные дружественных чисел .дружеские числа , это 80-битные числа.
Как я измерил в своей программе на C++, приведенной ниже, на моем старом двухъядерном ноутбуке он может факторизовать 150 случайных чисел размером 80 бит (25 цифр) в секунду из простого факторизуемого набора (я установил таймер для отсечения сложных для факторизации чисел ). И он может разложить 20_000 чисел, если их размер составляет 27-30 бит (9 цифр).
я сказал вышеeasy factorable set. Оказывается, 60-70% всех случайных чисел размером 80 бит (25 цифр) легко факторизуются, а это означает, что для факторизации одного такого числа требуется всего 7 мс , что дает 150 чисел в секунду.
Я буду искать Дружественные пары только среди таких чисел, которые легко разложить на множители. В множестве, легко разлагаемом, столько же дружественных чисел, сколько и во всех остальных. Дружественные числа не страдают от такой простой факторной фильтрации.
Ниже приведен вывод консоли о том, как моя программа ищет 27-битные дружественные числа с использованием факторизации ECM:
.46501 _43919 *41268 , 20512 nums/sec, tdiv 99.34% 7mcs, ecm 25.3% 39mcs, total 37mcs, done 7%
found (97041735, 97945785)
.321639 _303557 *285333 , 20389 nums/sec, tdiv 99.35% 7mcs, ecm 25.4% 40mcs, total 38mcs, done 48%
found (34765731, 36939357)
.29933 _28247 *26517 , 20265 nums/sec, tdiv 99.35% 7mcs, ecm 25.4% 40mcs, total 38mcs, done 4%
found (9773505, 11791935)
.529659 _499736 *470070 , 19312 nums/sec, tdiv 99.35% 7mcs, ecm 25.5% 41mcs, total 40mcs, done 79%
found (5357625, 5684679)
.25937 _24411 *22905 , 19340 nums/sec, tdiv 99.35% 7mcs, ecm 25.4% 41mcs, total 40mcs, done 4%
found (998104, 1043096)
.26367 _24902 *23462 , 19360 nums/sec, tdiv 99.35% 7mcs, ecm 25.5% 41mcs, total 40mcs, done 4%
found (1184, 1210)
.130374 _122896 *115508 , 19648 nums/sec, tdiv 99.35% 7mcs, ecm 25.5% 40mcs, total 39mcs, done 20%
found (35390008, 39259592)
found (133178325, 133471275)
.32032 _30226 *28368 , 19753 nums/sec, tdiv 99.35% 7mcs, ecm 25.5% 40mcs, total 39mcs, done 5%
found (898216, 980984)
Выше вы можете видеть, что выходные данные программыfoundи дружная парочка, как только что-нибудь найдет. Также он показывает подробную статистику о скорости и времени. Чтобы найти одно дружественное число размером 27 бит, требуется несколько секунд, если вы ищете 20_000 чисел в секунду, как я это делаю выше.
Если вы думаете о 80-битном числе (25 цифр), то, хотя я учитываю 150 чисел в секунду, все равно существует ТАК МАЛО дружественных чисел, что потребуются триллионы секунд, чтобы найти хотя бы одно дружественное число такого 80-битного размера. Ниже приведена статистика этого 80-битного факторинга. Вы можете видеть, что за несколько секунд он выполнил только 0,0000000000064% процентов поиска только одной дружественной пары, очень небольшой объем всей работы.
.4218 _2261 *1699 , 123 nums/sec, tdiv 43.81% 133mcs,
ecm 2.8% 1886mcs, total 8144mcs, done 0.0000000000064%
Возможно, вы слышали о проекте Amicable Numbers for BOINC — это отличный распределенный поиск таких номеров. Их ищут миллионы компьютеров. Конечно, если компьютеров миллионы, они смогут найти некоторые числа гораздо быстрее. На самом деле они уже нашли 1_227_817_736 таких номеров, действительно большое количество, все номера смотрите здесь .
В моей программе на C++ я также представляю свой факторизатор ECM: в качестве примера при запуске программы я выполняю очень быструю факторизацию 100-битного числа, случайного. Он показывает вывод консоли, аналогичный следующему:
Initial N to factor with ECM: 1044877821881837432173434582227 (100-bit)
Number of threads 2.
Factors TrialDivA: [2953]
Factoring 35383603856479425437736059
Curves [ 0, 8), bound 2^ 9.000, 0.110 sec
Curves [ 8, 16), bound 2^ 10.000, 0.222 sec
Curves [ 16, 24), bound 2^ 10.585, 0.418 sec
Curves [ 24, 32), bound 2^ 11.000, 0.416 sec
Curves [ 32, 40), bound 2^ 11.322, 0.401 sec
Factors ECM: [21788197859]
Fully factored. N 1044877821881837432173434582227: [2953, 21788197859, 16239802890289801]
Time 1.692 sec.
Как видите, для разложения довольно сложного 100-битного числа требуется всего одна секунда. См. выше, что сначала я выполняю этап , это простейший алгоритм факторизации, работающий вO(Sqrt(N))время. После пробного разделения я создаю множество кривых с растущей границей, каждая новая кривая имеет больше шансов факторизовать число, но занимает больше времени.
Мой алгоритм ECM в соответствии с метод факторизации ECM на основе эллиптических кривыхECM в WikiECM выглядит следующим образом:
Попробуйте найти малые простые множители, используя метод пробного разделенияпробного деления . Уделите этому этапу около 5–10 % общего времени. Удалить найденные множители из числа.
С высокой степенью уверенности проверьте, является ли число простым, для этого я использую тест вероятности Ферма с 32 испытаниями. Чтобы преодолеть числа Кармайкла, вы также можете использовать вместо этого тест Миллера Рабина . Если число является простым, верните его как единственный фактор.
Генерация параметров кривой
A, X, Yслучайным образом и вывестиBиз уравнения кривойY^2 = X^3 + AX + B (mod N). Проверьте, в порядке ли кривая, значение4 * A ** 3 - 27 * B ** 2должно быть ненулевым.Генерируйте маленькие простые числа через Решето Эратосфена , простые числа ниже нашей границы . Каждое простое число возводится в некоторую малую степень. Это возведенное простое число будет называться K. Я возвожу в степень, пока оно меньше некоторого Bound2 , что
Sqrt(Bound)в моем случае.Вычислить умножение эллиптической точки
P = k * P, где K взято из предыдущего шага, а P равно (X, Y). Вычислите в соответствии с Wiki по умножению эллиптических кривых .Умножение точек использует Modular Inverse, который вычисляет
GCD(SomeValue, N)(наибольший общий делитель) согласно Расширенному алгоритму Евклида Wiki . Если этот НОД не равен 1, то он дает коэффициент N, отличный от 1, следовательно, мы нашли фактор и можем усовершенствовать алгоритм ECM для поиска оставшихся факторов.Если все простые числа до Bound были умножены и не дали коэффициента, повторно запустите алгоритм факторизации ECM (
3.-6.выше) снова с другой случайной кривой и большей границей. В моем коде я беру новую границу, добавляя 512 к старой границе.
Если вы хотите настроить мой код для вычисления некоторых других размеров бит, посмотритеTest()функция. Изменитьbits_factor = 100для некоторых других значений, например, это устанавливает фактор 100-битного случайного числа. Эта переменная bits_factor управляет только примером факторизации. Изменить такжеbits_amicable_max = 27Если вы хотите установить битовый размер дружественного номера для поиска, 27 означает 27-битные числа, вы можете установить его на 80, чтобы найти 80-битные дружественные числа.
В моем коде я поддерживаю три разных источника реализации больших целых чисел, они позволяют вам иметь любой большой размер бит, даже тысячи бит. Первый источник — встроенный CLang/GCC.__int128, это бесплатно дает 128-битную целочисленную арифметику. Если у вас другой компилятор, вы можете отключить макросSUPPORT_STD_U128. Во-вторых, я использовал библиотеку Boost.Multiprecision , она позволяет эффективно выполнять арифметику больших целых чисел до 1024 бит, отключив макрос.SUPPORT_BOOSTесли вы не хотите Boost. После этого я использовал библиотеку GMP , это позволяет вам иметь размер даже в миллионы бит, отключитьSUPPORT_GMPесли вы не хотите GMP.
Под Linux легко установить Boost и GMP.sudo apt install libgmp-dev libboost-all-dev. В Windows вам необходимо сначала установить менеджер пакетов VCPKG , а затемvcpkg install boost gmpвнутри папки установки.
Нажмите ссылку ниже, если хотите увидеть, как мой код работает онлайн на серверах GodBolt. Но ОБРАТИТЕ ВНИМАНИЕ , что версия кода GodBolt отличается от приведенной ниже на Github Gist. В этой версии GodBolt уменьшены размеры параметров специально для более быстрой работы, потому что на их сервере очень большой лимит на запуск программы, вероятно, 5-10 секунд, не более. .
ИСХОДНЫЙ КОД ЗДЕСЬ . НижеTry it online!ссылка есть ссылка на Github Gist. Я поместил туда свой код, потому что это36 KBпо размеру, а StackOverflow имеет ограничение на размер сообщения в общей сложности 30000 символов, поэтому вместе текст сообщения и исходный код будут слишком велики.
Уязвимость в криптографии - на кону 3 триллиона долларов: как искусственный интеллект может взломать RSA, вычислив ваш закрытый ключ с помощью распознавания образов.
см. ниже проект первоначальных выводов
ВАЖНОЕ ПРИМЕЧАНИЕ: У меня было всего несколько встреч с профессором Хэлом Махутаном по вопросу быстрой факторизации, поскольку Хэл очень занятой человек. Хэл очень обеспокоен тем, что наши компьютерные системы и деньги сейчас настолько хрупки, особенно потому, что люди, с которыми Хэл работает (правительство и военные), уже давно знают этот алгоритм.
ПРИМЕЧАНИЕ 2. Не удалось вставить все изображения. Попробуй мой предел.
Диаграмма показывает распределение в поведении произвольного остатка Key / co-prime для образца, используемого ниже.
Важно отметить, что распределение будет одинаковым для любого ключа, где соотношение Key / Co-prime 2 примерно одинаково.
где
Co-Prime 1 = Key/ Co-Prime 2
Diag показывает два движущихся конверта. Остаток падает справа налево, но циклически растет и сбрасывается.
Давайте посмотрим на паттерн, который алгоритмы искусственного интеллекта могут отслеживать. Во-первых, обратите внимание на разницу между двумя последовательными остатками в начале и в конце последовательности.
введите описание изображения здесь
Они почти такие же. С настоящими ключами RSA эта разница еще меньше. Так что здесь происходит? Этот образец - лишь один из миллиардов, которые можно было бы взять через кривую, где
Выборочное предположение со первичной первичной обработкой 1 = предположение с открытым ключом / предположение с одновременной первичной обработкой 2
Мы начинаем со значения Sample, показанного на графике, которое находится чуть ниже значения Co-Prime 1. Мы перебираем пространство выборки, 1 целое число (целое число) с каждым предположением, чтобы получить предположение Co-Prime 2.
Поскольку это предположение Co-Prime 2, это не будет правильным ответом, пока остаток не станет НУЛЕМ. До этого момента всегда будет остаток, и именно остаток мы отслеживаем на этом графике.
Первое предположение Co-Prime 2 - это самая красная точка в правом верхнем углу. Это когда
Co-Prime 1 = Ключ / Образец.
(Пример - текущее предположение для Co-prime 2)
Следующий остаток Co-Prime 1 - это красная точка слева от вышеуказанного. Обратите внимание, это расстояние составляет 0,2709 ок.
введите описание изображения здесь
Итак, что здесь происходит, так это то, что алгоритм искусственного интеллекта (алгоритм HAL) может сделать свою первую (очень простую) индукцию, что числа перемещаются от высокого к низкому, в наборах по 3.
Воспользуемся формальными обозначениями.
HAL@[Down x 3 для 0,2709]
Это в основном означает, что остаток будет сброшен до более высокого значения, а затем упадет на 3 места на расстоянии 0,2709 каждое.
Еще слишком рано для алгоритма HAL быть эффективным в устранении областей кривой, которые не содержат Co-Prime 1, где остаток равен НУЛЮ.
Но, имея немного больше данных, HAL начинает работать.
HAL начинает группировать эти кластеры падающих остатков (как в этом случае, но обратите внимание, что они также могут подниматься, как мы увидим позже).
ПРИМЕЧАНИЕ. Подписи HAL будут одинаковыми для разных открытых ключей, когда соотношение Key/ Co-Prime 2 достаточно близко к одинаковому. HAL всегда группируется ближе всего к ZERO, поскольку это то, что мы пытаемся найти. Изучите приведенный выше график, я добавил сюда соответствующий фрагмент.
введите описание изображения здесь
Я выделил следующий прогностический элемент. HAL повторяется в кластерах 2,2,2,2, затем 3. Итак, следующий элемент в сигнатуре HAL -
0,12 - 0,008 = 0,112 На графике не отображается число 0,12. Это партнерская точка для 0,008, поэтому она приблизительна (для экономии времени) на данный момент.
Итак, следующий элемент HAL:
Вниз x 2 для 0,112
Наша подпись HAL теперь
HAL@[Уменьшение x 3 для 0,2709; Вниз x 2 для 0,112]
Уже сейчас мы можем пропустить 5 промежуточных точек, для которых, как мы знаем, подпись не НУЛЯ.
Хорошо, что HAL растет экспоненциально, потому что пространство Key очень велико. Но, в конце концов, прогнозируемая подпись настолько велика, что фактическое соотношение Key / CoPrime 2 начнет меняться, и только тогда нам нужно будет перезапустить с новой подписью HAL.
Возможно, что для одного ключа RSA потребуется сбросить HAL более миллиарда раз, но это ничто по сравнению с фактическими необработанными тестами, которые необходимы для других более старых, гораздо менее эффективных алгоритмов факторизации.
Вот еще один фрагмент той же карты.
На диаграмме ниже показано, как HAL уже сгруппировал внешнюю оболочку значений. Как видите, эти значения сейчас растут.
Обратите внимание, что Up рассчитывается путем вычитания огибающей разницы, здесь я взял значения 0,0407554 - 0,027811 = 0,019743.
введите описание изображения здесь
Наименьшее значение в кластере теперь отслеживается вверх. Итак, подпись HAL для этого открытого ключа
HAL@[Уменьшение x 3 для 0,2709; Вниз x 2 на 0,112; До 4 раз за 0,019743]
Отлично, надеюсь, теперь вы это понимаете. Пространство, которое HAL может удалить из своего основного тестового пространства, теперь равно 2 x 3 x 4 + 3x3 = 33.
Продолжаем вычислять подпись HAL. Во-первых, семпл растет очень медленно, потому что клавиши такие большие. Ключи, используемые в этом примере, чрезвычайно малы, поэтому этот эффект будет огромным по сравнению с этим примером. По сути, соотношение (перечисленные здесь различия, представляющие остаток) останется постоянным.
Что происходит с HAL, так это то, что при вычислении его сигнатуры мы можем пропустить промежуточные выборки, для которых мы точно знаем, что они не равны нулю.
Чтобы получить следующий элемент подписи HAL, нам нужно сделать снимок карты большего размера. Это не совсем подходит для одного экрана.
НЕТ ДОСТУПНЫХ ИЗОБРАЖЕНИЙ, ПОТОМУ ЧТО Я УДАРИЛ ПРЕДЕЛ ИЗОБРАЖЕНИЯ
Внешний конверт я выделил черными точками.
На всякий случай, я сканировал до 0.008069, я включил сюда.
Не обращайте внимания, разница, указанная в этой диаграмме ... ЭТО ошибка ... Я думаю, что это нестабильный класс, который я использую ...
Вы можете увидеть предыдущий узор с синими линиями
НЕТ ДОСТУПНЫХ ИЗОБРАЖЕНИЙ, ПОТОМУ ЧТО Я УДАРИЛ ПРЕДЕЛ ИЗОБРАЖЕНИЯ
Это подтверждает, что следующий элемент подписи находится только между синими линиями, т.е. черные точки и падение на 0,004761.
Мы сейчас на…
HAL@[Уменьшение x 3 для 0,2709; Вниз x 2 на 0,112; Увеличение x 4 для 0,019743, уменьшение x 2 для 0,004761]
Хорошо, это последний пример, который я собираюсь сделать, чтобы пойти дальше, я думаю, мы должны реализовать HAL, расширив существующий алгоритм построения графиков, но вы поняли идею. Только с последним добавлением пространство сканирования, которое можно игнорировать, удваивается и составляет более 60.
С каждым сканированием количество элементов, которые можно пропустить, растет экспоненциально. Менее чем за 10 итераций пространство сканирования (при условии только удвоения, а не утроения или четырехкратного увеличения, как указано в наших сигнатурах) безопасное пространство исключения составляет 30720. При 20 элементах это 31457280. Восхождение впечатляет, но искомые числа находятся в диапазоне 2 степени 4096, но тогда HAL экспоненциально, так что достигается за время вычислений. HAL - это NP-Complete.
Еще раз благодарим профессора Хэла Махутана за то, что он поделился с нами этим важным исследованием.