Всем добрый день. Реализую вероятностный метод проверки чисел на простоту (Миллера-Рабина). В общем и целом не возникает особых проблем, ибо тема распиана во многих монографиях и мануалах, например, --> Здесь <--. Вот только везде, где мне удавалось нагуглить что-то стоящее внимания, не описывается момент, как n-1 раскладывают на два множителя так, чтоб один был результатом возведения двойки в некую степень s, а другой - как можно меньшим нечётным числом. Студенческие реализации полны фольклора, но тупой перебор здесь не годится. Поясню более подробно. Допустим, имеем достаточно большое число, которое нужно проверить на простоту. Если рассматривать функцию степени двойки, то она асимптотически растёт, т.е. у нас есть два дискретных значения (т.к. для целых чисел) этой функции, к примеру, 64 (2^6) и 128 (2^7). Нужно проверить на простоту число 127. Ближайшее целое (ну, а какое ещё), принадлежащее отображению этой степенной функции, это 64. Т.е. если тупо в цикле, отнимая от 127 единицу на каждой итерации, проверять числа делением на 2 (типа, делим 127 на два, если разделилось нацело, полученный результат делим опять на два, если нет - переходим к следующему, и так, пока не найдём число, являющееся степенью двойки), то это будет очень неэффективно. Ведь если ближайшее меньшее число степени двойки положим равным n, а ближайшее большее тогда будет 2*n, то нужно в худшем случае проверить n-1 вариантов. Да и сами числа могут быть составными, но по-разному составными. Т.е. двойка может входить в разложение такого числа не единожды (далеко не единожды). Битовые операции (сдвиги и тесты старшего бита) тоже нельзя использовать, поскольку с вещественными числами их нельзя применять по причине упакованности последних. И как же быть?

-----
Stuck to the plan, always think that we would stand up, never ran.

| Сообщение посчитали полезным:

Блин, вот я дурик. Можно ж просто делить это число на 2, пока делится. А когда дойдём до момента, при котором деление нацело невозможно, то эту неделящуюся часть примем за d, а количество удачных делений - за s.

-----
Stuck to the plan, always think that we would stand up, never ran.

| Сообщение посчитали полезным:

ARCHANGEL может я чет не понял, но признак делимости число на 2 это его окончание хххх10 в бинарном виде, а недилимость это хххххх1, кагбы все ничетные числа заканчиваюца на 1 в бинарном видел. я когдато курил тему про простые числа.. и самый быстрый контроль при бруте это если число в десятчиной заканчиваеца на 1 3 7 9 , типа все простые числа имеют такое окончание

-----
Наша работа во тьме, Мы делаем, что умеем. Мы отдаем, что имеем, Наша работа во тьме....

| Сообщение посчитали полезным:

VodoleY пишет:
но признак делимости число на 2 это его окончание хххх10 в бинарном виде

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

и самый быстрый контроль при бруте это если число в десятчиной заканчиваеца на 1 3 7 9

Но это же ещё не вся проверка. 33 ведь не простое число.

З.Ы. Хотя от упакованных чисел, видимо, придётся отказаться.

-----
Stuck to the plan, always think that we would stand up, never ran.

| Сообщение посчитали полезным:

ARCHANGEL я собственно о чем пытался сказать.. что есть варианты, когда проверка числа на псевдо простое(с достаточной глубиной), может занять больше времени чем просчет итерации брута с этим числом. НО минимальный тест который пролетает мнгновенно это признак 1 3 7 9

-----
Наша работа во тьме, Мы делаем, что умеем. Мы отдаем, что имеем, Наша работа во тьме....

| Сообщение посчитали полезным: ajax

ARCHANGEL пишет:
А когда мы имеем дело с вещественными числами - откуда это вдруг взялись вещественные числа в алгоритме Миллера-Рабина?

| Сообщение посчитали полезным:

Promix_17 ты 4дня думал чтоб процитировать сообщение?

-----
Наша работа во тьме, Мы делаем, что умеем. Мы отдаем, что имеем, Наша работа во тьме....

| Сообщение посчитали полезным:

Promix_17
В самом алгоритме - ниоткуда, т.к. алгоритм применим на кольце вычетов, которое образовано элементами целых чисел. Но тут есть одно но. По логике 8-байтовый double должен вмещать бОльшие целые значения, нежели 4-байтовый DWORD.

-----
Stuck to the plan, always think that we would stand up, never ran.

| Сообщение посчитали полезным:

Лучше б __int64 заюзал, он целый и вопросов не создаст. Ну или его же unsigned. И тоже 8 байтов. И никаких проблем с корявым представлением, типа что упакованный. Накой там дабл, непонятно.

| Сообщение посчитали полезным: ARCHANGEL

Не совсем понятна логика использования double для целых, ведь страдает точность и если даже можно будет представить целое, превосходящее DWORD, зачем? Можно и __int64 использовать.

-----
Следуй за белым кроликом

| Сообщение посчитали полезным:

VodoleY пишет:
Promix_17 ты 4дня думал чтоб процитировать сообщение? - я только зашёл

ARCHANGEL пишет:
8-байтовый double должен вмещать бОльшие целые значения, нежели 4-байтовый DWORD

8-байт = 64 бита - как-то слабо...

Т.е. если это что-то для RSA или т.п., то надо будет самому работу с большими числами пилить.

| Сообщение посчитали полезным: DimitarSerg

Promix_17 все реализации алгоритмов, работающих с большими числами, используют дополнительные библиотеки для работы с большими числами. Для делфи это FGInt(стабильная, но скудная) DFFLibV13 (малеха подглючивает, отписал афтору обещал исправить) для си это BigDigits-2.3.0(сам юзать не пробывал). Есть еще реализованные базовые функи на асме (сложение умножение деление и т.д)

-----
Наша работа во тьме, Мы делаем, что умеем. Мы отдаем, что имеем, Наша работа во тьме....

| Сообщение посчитали полезным: ARCHANGEL

VodoleY
Для С/С++ реализаций чуть меньше чем докуя, длинка даже в boost входит.

Add:
Может пригодится GMP.

| Сообщение посчитали полезным:

F_a_u_s_t я не утверждал, что на си их мало. я делфист, BigDigits попался постоку поскольку... но чЁто мы флудить начали... (boost интересная штука, почитал спс, чет раньше не встречалось)

-----
Наша работа во тьме, Мы делаем, что умеем. Мы отдаем, что имеем, Наша работа во тьме....

| Сообщение посчитали полезным: