На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
Страницы: (3) [1] 2 3  все  ( Перейти к последнему сообщению )  
> Разложение на простые множители..
    Кто-нить пытался как-то оптимизировать сабж? Максимум, что у меня получилось, - это где-то за 70 секунд (на 120-м пне) определить, что самое большое 32-битное простое - действительно простое (4294836197, по-моему). Т.е. при разложении получилось 1 и само число.

    Есть идеи? :) Просто интересно..
    Сообщение отредактировано: Kernel_Panic -
      А ты не думал - почему именно сабж является источником почти-необратимых функций, которые сейчас используются для наиболее популярных алгоритмов шифрования? Именно из-за больших затрат ресурсов для решения сабжа.
        Вот пример на TMT.... Работает быстро....
        ExpandedWrap disabled
          {$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, то ещё проще....
        ExpandedWrap disabled
          {$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.
          Я тут прогнал немного, извиняюсь ;D
          Вот верный вариант программы, раскладывающий число на простые множители....

          ExpandedWrap disabled
            {$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.
            По-моему, выше перебор описан. Попробуй найти документацию по ассиметричной криптографии там описан алгоритм разложения на простые множители. К примеру схема ElGamal. А вторую забыл ???
              Цитата zer, 23.04.02, 11:38:45
              По-моему, выше перебор описан. Попробуй найти документацию по ассиметричной криптографии там описан алгоритм разложения на простые множители. К примеру схема ElGamal. А вторую забыл ???


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

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


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

                  Добавлено
                  Нашёл:
                  http://en.wikipedia.org/wiki/General_Number_Field_Sieve
                    Подскажите какую-нибудь "стандартную" Си-библиотеку для проверки на простоту (+разложение на простые) для чисел от 2 до 1032, пожалуйста! :thanks:
                      Славян, "стандартной" по твоему запросу нет. Думаю тебе следует скрестить вот этот код разложения (на Си без плюсов перевести несложно, равно как и добавить проверок):
                      ExpandedWrap disabled
                        #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;
                        }

                      ExpandedWrap disabled
                        Value (10111787): 1 7 7 17 61 199

                      ... и какую-нить либу для работы с большими целыми, типа этой. Для чистого Си без плюсов не искал.
                        ExpandedWrap disabled
                          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 несколько напрягают по скорости алгоритма... Хм-м... :scratch:
                            (Div++) это (Div = Div + 1)
                            (Div+=2) это (Div = Div + 2)
                            Сложение не сильно увеличит сложность. Тем более, что проверка на (Div > 2) это тоже еще одна операция суммирования
                            Если проверять на делимость с четными числами - это бесполезно после проверки div = 2. А так перебор сокращен вдвое.
                            Сообщение отредактировано: macomics -
                              Да я тут слегонца глубже задумался и понял, что физически идёт проверка на делимость со всеми нечётными. Ну так это же Г-метод, "детсадовский"! :wall: :wall: :wall:
                              Надо, конечно, не всемирно-кластерный, с проверкой до 10300, но всё же хоть какой-то "университетский". :blush:
                                Может он и детсадовский (хотя деление и дроби это школа, 1-2 класс), но число 2147483647 с моими дополнениями проверяется меньше секунды и вывод
                                ExpandedWrap disabled
                                  Value (2147483647): 1 2147483647

                                Максимально проверяемый делитель 46341
                                Сообщение отредактировано: macomics -
                                1 пользователей читают эту тему (1 гостей и 0 скрытых пользователей)
                                0 пользователей:
                                Страницы: (3) [1] 2 3  все


                                Рейтинг@Mail.ru
                                [ Script execution time: 0,0408 ]   [ 14 queries used ]   [ Generated: 24.06.22, 23:17 GMT ]