Утверждение №2 - если известен минимально возможный остаток от деления числа N на любое M меньшее N и соответсвующие кратные K , то получение минимально возможного остатка от деления N на M-1 занимает четыре операции сложения максимум.
Попробую обосновать данные утверждения:
Возьмём выражение N=M*K+R
1) Проведём элементарное преобразование
N = M*K+R = (M-1)*K + (R+K)
2) В случае, если R+K>=M-1 существует остаток R1 меньший R такой, что
N = (M-1)*K + (M-1)*L + R1 то есть
N = (M-1)*(K+L) + R1
в случае, если получен R1 такой, что R1+(K+L)>=M-1 то R1 минимальный
остаток от деления N на M-1. Частное в данном случае будет равно K+L
3) Получение числа L может быть получено инкрементально путём увеличения
на каждом шаге K на единицу и определения R1 вычитая из него M-1
это возможно из тождества N = (M-1)*(K+1) + (R1 - (M-1))
4) Утверждение полученное эмпирически.
Если R минимальный остаток от деления числа N на M и K, то если R+K>=M-1
существует один остаток R1 и он будет единственным минимальным остатком такой что
N = (M-1)*(K+L) + R1 где L натуральное число. В случае же, если R+K<M-1 то новый минимальный остаток будет равен R+K для тождества N = (M-1)*K + (R+K) 5)
5) Частный случай, когда R1=0 - случай когда R делится нацело на M-1. частное в данном случае находится автоматически.
6) Сложность алгоритма. Количество шагов за которые может быть найдено решение будет существенно меньше чем N*((N/2)-SQRT(N)) (далее будет показано насколько меньше).
7) По вышеизложенным выкладкам построим элементарный алгоритм:
procedure TForm1.Button1Click(Sender: TObject);
var
Source : TNumber;
Index : TNumber;
Shift : TNumber;
Candidat : TNumber;
begin
Source:=strtoint(Edit1.text); // Source Number
Index:=2;
Candidat:=Trunc(Source/Index);
Shift:=Source-Candidat*Index;
if (Shift=0) then begin
Memo1.Lines.Add(inttostr(Candidat)+';'+inttostr(Index)); // Result
end;
while (Candidat>SQRT(Source)) do begin
if (Candidat>Shift) then begin
dec(Candidat);
Shift:=Shift+Index;
end
else begin
inc(Index);
Shift:=Abs(Candidat-Shift);
if (Shift=0) then& nbsp;begin
Memo1.Lines.Add(inttostr(Candidat)+';'+inttostr(Index)); // Result
end; // if
end; // if
end; // while
end; // procedure
* Алгоритм только иллюстрирует процесс
8) И посчитаем (в лоб) количество операций которое понадобится для получения всех делителей.
54;106;1061999999997;1999999987;499968374223540623
55;105;1105
56;115;1149
57;105;1194
58;108;1240
59;108;1287
60;116;1335
61;112;1384
1671;3333;1327814
1672;3342;1329424
1673;3337;1331035
1674;3346;1332647
1675;3342;1334260
1676;3345;1335874
1677;3347;1337489
4161;8315;8388552
4162;8316;8392617
4163;8317;8396682
4164;8324;8400749
4165;8325;8404817
4166;8324;8408885
4167;8326;8412955
4168;8330;8417026
4169;8329;8421097
4170;8338;8425170
10923;21839;58514367
10924;21841;58525134
10925;21845;58535902
10926;21848;58546670
10927;21846;58557440
10928;21851;58568211
10929;21849;58578983
26957;53909;358913966
26958;53914;358940677
26959;53912;358967389
26960;53924;358994103
26961;53923;359020817
26962;53926;359047532
26963;53921;359074248
77982;155966;3018819488
77983;155960;3018897051
77984;155968;3018974616
77985;155969;3019052182
77986;155968;3019129748
77987;155971;3019207316
77988;155982;3019284884
77989;155973;3019362454
77990;155982;3019440025
77991;155977;3019517596
77992;155982;3019595169
77993;155981;3019672742
77994;155994;3019750317
77995;155987;3019827893
77996;155998;3019905469
77997;155989;3019983047
1150521;2301035;660615209951
1150522;2301036;660616358864
1150523;2301037;660617507777
1150524;2301068;660618656692
1150525;2301042;660619805608
1150526;2301058;660620954524
1150527;2301047;660622103442
1150528;2301053;660623252360
99999997;199999985;4998999700045004
Первая колонка - исходное число. Вторая - количество операций для полной факторизации. Третья величина (N/2)*SQRT(N). Опытным путём было получено, что для полной факторизации числа нужно 2*N операций.
Итоги:
1) Был построен алгоритм получающий на каждом шаге минимально возможный остаток
2) В случае, когда минимально возможный остаток равен нулю мы имеем случай деления нацело. То есть алгоритм производит факторизацию исходного числа - получение делителей числа.
3) Численно было получено число операций, необходимых для полной факторизации числа. Для исходного числа N число операций сложения для факторизации числа будет 2*N
Википедия утверждает, что для больших N полиномиальная сложность хороша при факторизации. В приведённом решении, сложность не просто полиномиальна - она линейна. Для случаев RSA когда исходное число - произведение двух простых чисел Задача сразу упрощается, потому что на каждом шаге мы получаем сразу два делителя M и L. Что особенно ценно в данном алгоритме - в центральной части алгоритма используется только операция сложения(она де сравнение и вычитание). Нет деления и умножения. Алгоритм детерминирован. Время работы может быть рассчитано заранее.
Комментариев нет:
Отправить комментарий