Разложение на простые множители..

[Kernel Panic]

Кто-нить пытался как-то оптимизировать сабж? Максимум, что у меня получилось, - это где-то за 70 секунд (на 120-м пне) определить, что самое большое 32-битное простое - действительно простое (4294836197, по-моему). Т.е. при разложении получилось 1 и само число.

Есть идеи? Просто интересно..

Сообщение отредактировано: Kernel_Panic - 16.04.02, 19:39

[Фауст]

А ты не думал - почему именно сабж является источником почти-необратимых функций, которые сейчас используются для наиболее популярных алгоритмов шифрования? Именно из-за больших затрат ресурсов для решения сабжа.

[Jin X]

Вот пример на TMT.... Работает быстро....

{$S-,B-,R-,Q-}<br>Var<br>   N, i, j: DWord;<br>   Prime: Boolean;<br><br>Begin<br>   N := $FFFFFFFF;<br>   For i := 2 to Trunc(Sqrt(N)) do<br>   Begin<br>      Prime := True;<br>      For j := 2 to Trunc(Sqrt(i)) do<br>         If (i mod j) = 0 then<br>         Begin<br>            Prime := False;<br>            Break<br>         End;<br>      If Prime and ((N mod i) = 0) then WriteLn(i)<br>   End<br>End.

А если заменить DWord на Longint и поставить N := $7FFFFFFF, то можно будет и в BP компилить..... Кстати, простое - это $7FFFFFFF (2147483647), а не $FFFFFFFF.

А если тебе нужно найти все числа, кратные N, то ещё проще....

{$S-,B-,R-,Q-}<br>Var<br>   N, i: DWord;<br><br>Begin<br>   N := $FFFFFFFF;<br>   For i := 2 to Trunc(Sqrt(N)) do<br>      If (N mod i) = 0 then WriteLn(i)<br>End.

[Jin X]

Я тут прогнал немного, извиняюсь ;D
Вот верный вариант программы, раскладывающий число на простые множители....

{$S-,B-,R-,Q-}<br>Var<br>   N, i, j: DWord;<br>   Prime: Boolean;<br><br>Begin<br>   N := $FFFFFFFF;<br>   Repeat<br>      For i := 2 to Trunc(Sqrt(N)) do<br>      Begin<br>         Prime := True;<br>         For j := 2 to Trunc(Sqrt(i)) do<br>            If (i mod j) = 0 then<br>            Begin<br>               Prime := False;<br>               Break<br>            End;<br>         If Prime and ((N mod i) = 0) then<br>         Begin<br>            WriteLn(i);<br>            N := N div i;<br>            Break<br>         End<br>      End<br>   Until not Prime;<br>   WriteLn(N)<br>End.

[zer]

По-моему, выше перебор описан. Попробуй найти документацию по ассиметричной криптографии там описан алгоритм разложения на простые множители. К примеру схема ElGamal. А вторую забыл ???

[Фауст]

Цитата zer, 23.04.02, 11:38:45

По-моему, выше перебор описан. Попробуй найти документацию по ассиметричной криптографии там описан алгоритм разложения на простые множители. К примеру схема ElGamal. А вторую забыл ???

Неверный ответ  - шифр Эль-Гамаля основан на дискретном логарифмировании, на факторизации основан RSA.
Уточнено из источника: http://algolist.manual.ru/defence/well_known/index.php

[esperanto]

:-[
да на данный момент есть разные решения но все они в общем случае принадлежат классу НП то есть экспоненцмальные

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


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

[Imperator]

Лучший алгоритм - общее решето числового поля. Как раз сейчас ищу)

Добавлено 28.02.06, 18:55
Нашёл:
http://en.wikipedia.org/wiki/General_Number_Field_Sieve

[Славян]

Подскажите какую-нибудь "стандартную" Си-библиотеку для проверки на простоту (+разложение на простые) для чисел от 2 до 10³², пожалуйста!

[Majestio]

Славян, "стандартной" по твоему запросу нет. Думаю тебе следует скрестить вот этот код разложения (на Си без плюсов перевести несложно, равно как и добавить проверок):

#include <iostream>
#include <vector>
 
void PrimeFactorization(int Value, std::vector<int> &Res) {
  int Div = 2;
  Res.push_back(1);
  while (Value > 1) {
    while (Value % Div == 0) {
        Res.push_back(Div);
        Value /= Div;
    }    
    if (Div == 2) Div++;
    else Div += 2;
  }
}
 
int main() {
  int Value = 10111787;
  std::vector<int> Res;
  PrimeFactorization(Value, Res);
  std::cout << "Value (" << Value << "): ";
  for(const auto &i: Res) std::cout << i << " ";
  return 0;
}

Value (10111787): 1 7 7 17 61 199

... и какую-нить либу для работы с большими целыми, типа этой. Для чистого Си без плюсов не искал.

[macomics]

void PrimeFactorization(int Value, std::vector<int> &Res) {
  int Div = 2, Div2 = 4;
  Res.push_back(1);
  while (Value > 1) {
    while (Value > Div2 && Value % Div == 0) {
        Res.push_back(Div);
        Value /= Div;
    }
    if (Value <= Div2) {
        Res.push_back(Value);
        Value = 1;
    }
    if (Div++ > 2) Div++;
    Div2 = Div * Div;
  }
}

Так будет чуть быстрее

[Славян]

Спасибо, поэкспериментирую, но что-то строки Div++ и Div+=2 несколько напрягают по скорости алгоритма... Хм-м...

[macomics]

(Div++) это (Div = Div + 1)
(Div+=2) это (Div = Div + 2)
Сложение не сильно увеличит сложность. Тем более, что проверка на (Div > 2) это тоже еще одна операция суммирования
Если проверять на делимость с четными числами - это бесполезно после проверки div = 2. А так перебор сокращен вдвое.

Сообщение отредактировано: macomics - 18.06.22, 09:23

[Славян]

Да я тут слегонца глубже задумался и понял, что физически идёт проверка на делимость со всеми нечётными. Ну так это же Г-метод, "детсадовский"!
Надо, конечно, не всемирно-кластерный, с проверкой до 10³⁰⁰, но всё же хоть какой-то "университетский".

[macomics]

Может он и детсадовский (хотя деление и дроби это школа, 1-2 класс), но число 2147483647 с моими дополнениями проверяется меньше секунды и вывод

Value (2147483647): 1 2147483647

Максимально проверяемый делитель 46341

Сообщение отредактировано: macomics - 18.06.22, 10:12