Простые числа

Сообщение №10479 от 23 января 2004 г. 21:00
Тема: Простые числа


5161 Простые числа Часть 1 23 октября 2002

Темы со смежными вопросами
10364 Вопрос по теории чисел
7748 Факторизация чисел
5551: Способ получения простых чисел
2085 Самое большое простое число


Отклики на это сообщение:

Очень нужна информация по лажевым числам мерсенна
вида 2^a +/- 2^b +/- 2^c ... +/- 2^0
Например, 2^384-2^128-2^96+2^32-1 - простое.
Они имеют все достоинства нормальных чисел Мерсенна
1) Простой быстрый детерминированный тест типа Лукаса-Ламера =).
2) Простое взятие модуля-вычета-остатка (магические свойства "девятки")

Внимание, а теперь вопрос:
как в натуре выполнять действия 1 и 2?
1) Заместо LL можно и Рабина раз пять впарить...
2) Как, к примеру, быстро взять модуль 9909 в десятичной системе,
чего-йта никак сообразить не могу.

Ах да, совсем забыл, а чем лажевые числа мерсена лучше обычных?
А тем, что их можно состряпать скока душе угодно для любого 2^a,
а нормальных чисел мерсена - только 40 штук на сегодня. Если кто хочет поставить рекорд в области простых чисел, пусть обращается к ОЧМерсенна!!!
Их полным полно, это вам не обычные числа мерсена.
Главное, что остатки от ОЧМерсенна беруться очень легко! Relf както мне показывал, но я ничего не понял. Еще раз plzzz для 9909 в десятичной системе чисто конкретно покажи.
24 января 2004 г. 13:12:


Да, нет желающих рассказать мне про дырявые числа мерсенна вида 111100000011111111111111111111111000000000000000111111111111111111111000000000000000000000000000000011111111111111111111111111111111111111111000000000000000000000000000000000000000000000111111111111111111111111111111111111111111...
Ну да черт с ними!
Я тут прочитал про числа вида 2^n-c, где c-малое число. Остаток берется вообще с полпинка, вот ими я и займусь наверное...


p=(a^2+b)(a^2-b).
Можно ли удовлетворить этому равенству при:
p=1 (mod4) - простое,
a - нечётное,
b - чёт,
(p,a)=1
30 января 2004 г. 19:17:


> p=(a^2+b)(a^2-b).
> Можно ли удовлетворить этому равенству при:
> p=1 (mod4) - простое,
> a - нечётное,
> b - чёт,
> (p,a)=1

Из простоты p следует, что отдно из множителей в произведении равен +-1. Без потери обности можно считать, что a^2-b=1 (или b=a^2-1) и p=2a^2-1.
Например, полагая a=3, получаем p=17.


> > p=(a^2+b)(a^2-b).
> > Можно ли удовлетворить этому равенству при:
> > p=1 (mod4) - простое,
> > a - нечётное,
> > b - чёт,
> > (p,a)=1

> Из простоты p следует, что отдно из множителей в произведении равен +-1. Без потери обности можно считать, что a^2-b=1 (или b=a^2-1) и p=2a^2-1.
> Например, полагая a=3, получаем p=17.

Прошу прощения за ошибку. Я имел в виду
p=(a^2+b)/(a^2-b)


> > > p=(a^2+b)(a^2-b).
> > > Можно ли удовлетворить этому равенству при:
> > > p=1 (mod4) - простое,
> > > a - нечётное,
> > > b - чёт,
> > > (p,a)=1

> > Из простоты p следует, что отдно из множителей в произведении равен +-1. Без потери обности можно считать, что a^2-b=1 (или b=a^2-1) и p=2a^2-1.
> > Например, полагая a=3, получаем p=17.

> Прошу прощения за ошибку. Я имел в виду
> p=(a^2+b)/(a^2-b)

И что это меняет? Требуем (a^2-b)=1 и далее по тексту.
Работает тот же самый пример: a=3, b=8, p=17.


> > > > p=(a^2+b)(a^2-b).
> > > > Можно ли удовлетворить этому равенству при:
> > > > p=1 (mod4) - простое,
> > > > a - нечётное,
> > > > b - чёт,
> > > > (p,a)=1

> > > Из простоты p следует, что отдно из множителей в произведении равен +-1. Без потери обности можно считать, что a^2-b=1 (или b=a^2-1) и p=2a^2-1.
> > > Например, полагая a=3, получаем p=17.

> > Прошу прощения за ошибку. Я имел в виду
> > p=(a^2+b)/(a^2-b)

> И что это меняет? Требуем (a^2-b)=1 и далее по тексту.
> Работает тот же самый пример: a=3, b=8, p=17.

Ясно. А если явно наложить условие a^2-b != 1.


> > > > > p=(a^2+b)(a^2-b).
> > > > > Можно ли удовлетворить этому равенству при:
> > > > > p=1 (mod4) - простое,
> > > > > a - нечётное,
> > > > > b - чёт,
> > > > > (p,a)=1

> > > > Из простоты p следует, что отдно из множителей в произведении равен +-1. Без потери обности можно считать, что a^2-b=1 (или b=a^2-1) и p=2a^2-1.
> > > > Например, полагая a=3, получаем p=17.

> > > Прошу прощения за ошибку. Я имел в виду
> > > p=(a^2+b)/(a^2-b)

> > И что это меняет? Требуем (a^2-b)=1 и далее по тексту.
> > Работает тот же самый пример: a=3, b=8, p=17.

> Ясно. А если явно наложить условие a^2-b != 1.

Вместо 1, можно взять любое другое нечетное число. Полагаем a^2-b=k, b=a^2-k, a=kt, p=2k*t^2-1. Простых такого вида тоже будет предостаточно.


Всем любителям длинных и очччень длинных чисел!!!
Обновился мой генератор случайных простых чисел
http://persicum.front.ru/purgen_02.zip
С его помощью вы можете находить простые числа практически любого размера. На практике, вы скорее исчерпаете машинное время, чем способность этой программы находить числа до 4 гигабит. Разумеется, такую прогу может написать любой любитель программирования, а уж тем более студент ВМК и т.п. Однако, даже мне иногда приходится учиться и работать, а не только изображать из себя придурка из инета. Первый шаг сделан, и дальнейшая судьба проекта зависит исключительно от вас, мои хорошие. Можно попытаться ускорить эту прогу раз в десять, если:
1) использовать фирменное FFT через SSE2 вместо моего доморощенного. Соответственно, нужна готовая DLL плюс интерфейс на Дельфи, чтобы ее подцепить.
2) искать не просто случайные простые, а специального вида.
Я подумываю о числах Crandall'а вида 2^n+c, где с - обычное малое число на 31бит. Остаток по таким числам берется с полпинка, сразу будет выигрыш в 3-5 раз. К тому же, это вам не числа мерсена. Этих полным полно, только копни. Соответственно, нужно знать, существуют ли для чисел Крондалла какие-нибудь специальные теоремы, признаки простоты и т.д. Хотя общий тест рабина будет здесь особенно эффективен, так как в двоичном представлении числа Крондалла - почти одни нули.
Медитируйте, медитируйте, и вы достигните просветления!!!
А по сему - за работу!


> > > > > > p=(a^2+b)(a^2-b).
> > > > > > Можно ли удовлетворить этому равенству при:
> > > > > > p=1 (mod4) - простое,
> > > > > > a - нечётное,
> > > > > > b - чёт,
> > > > > > (p,a)=1

> > > > > Из простоты p следует, что отдно из множителей в произведении равен +-1. Без потери обности можно считать, что a^2-b=1 (или b=a^2-1) и p=2a^2-1.
> > > > > Например, полагая a=3, получаем p=17.

> > > > Прошу прощения за ошибку. Я имел в виду
> > > > p=(a^2+b)/(a^2-b)

> > > И что это меняет? Требуем (a^2-b)=1 и далее по тексту.
> > > Работает тот же самый пример: a=3, b=8, p=17.

> > Ясно. А если явно наложить условие a^2-b != 1.

> Вместо 1, можно взять любое другое нечетное число. Полагаем a^2-b=k, b=a^2-k, a=kt, p=2k*t^2-1. Простых такого вида тоже будет предостаточно.

А совместимо ли это с p=1 (mod4) ?


> > Вместо 1, можно взять любое другое нечетное число. Полагаем a^2-b=k, b=a^2-k, a=kt, p=2k*t^2-1. Простых такого вида тоже будет предостаточно.

> А совместимо ли это с p=1 (mod4) ?

Да. Если t нечетное, то 2k*t^2-1 = 1 (mod 4).


Уже полюбившийся вам шутер-блокбастер "purgen" обновился до версии 0.3!!! Как вы помните, он предназначен для отстрела чудовищно-огромных простых чисел, которые не желают делиться. А делиться надо, как известно... What's new? В версии 0.3 введена поддержка обобщенных-составных-дырявых чисел МЕРСЕННА. В отличие от 40 своих известных академических собратьев, эти машинно-дружелюбны и выравнены под 32-бит. Проработав всего несколько минут, программа выдала целый зоопарк чисел, причем пару из них - 5000 десятичных знаков, а одно - аж 10000:


2^32768 - 2^8128 - 2^4832 + 2^4640 + 2^4448 - 2^3968 + 1
2^16384 - 2^2752 + 2^1440 + 2^1312 + 2^128 - 1
2^2048 - 2^768 + 2^512 - 2^192 - 2^64 - 2^32 + 1
2^1024 - 2^128 - 2^96 + 2^64 + 2^32 + 1 - очень красивое...


2^16384 - 2^6432 + 2^2272 + 1
2^8192 - 2^1824 - 1
2^8192 - 2^576 + 2^320 + 1
2^4096 - 2^160 + 2^96 + 1
2^2048 - 2^1472 + 2^1152 + 1
2^2048 - 2^448 + 2^192 + 1
2^1536 - 2^864 + 2^64 + 1
2^1024 - 2^512 + 2^128 - 2^64 - 1
2^768 - 2^96 - 1
2^512 - 2^288 + 1
2^512 - 2^32 - 1 (Twins !!!)
2^192 - 2^64 - 1

2^4095 + 78FD6C5Fh
2^1023 + 63CC3D3Dh
2^4096 - 2^2048 - 2^2016 + 2^704 - 2^672 + 2^288 + 1
2^4096 - 2^1024 - 2^192 - 2^96 + 2^32 - 1
2^2048 - 2^1024 - 2^512 - 2^160 + 1
2^2048 - 2^1024 - 2^128 + 2^64 - 1
2^2048 - 2^512 - 2^224 + 2^192 + 2^32 + 1
2^1536 - 2^224 - 2^128 + 2^64 - 1
2^1024 - 2^800 + 2^64 + 2^32 - 1
2^768 - 2^512 - 2^96 + 2^64 + 1
2^512 - 2^256 + 2^192 - 2^128 - 1
2^192 - 2^160 - 2^96 + 2^64 + 2^32 + 1
(2^2048 - 2^1984 + 2^1152 - 2^608 - 2^512 + 2^480 + 2^448 - 2^384 + 2^288 + 2^224 + 2^160 - 2^128 - 2^96 - 2^64 + 1) - вот так!!!


Успехов.


Я написал процедуру умножения длинных чисел через FFT.
Все хорошо, за исключением того, что требуется набивка чисел
незначащими ведущими нулями до длины "проскуриана" - 2^n.
Получается, что число длиной, скажем, 1024 цифры обрабатывается хорошо,
а 1025 - тормозит, как будто бы оно было длиной 2048 цифр.
В тоже время, библиотечная FFTW, которую я вызываю, может работать
с ЛЮБЫМ числом точек. Однако, радоваться рано. Всетаки разумнее
использовать набивку, чтобы гарантировать высокосоставное число, только непонятно какую лучше всего, то ли 3*2^n, то ли 3^m*2^n, может p*2^n, или 3*5*2^n...
24 марта 2004 г. 21:17:



> Я написал процедуру умножения длинных чисел через FFT.
> Все хорошо, за исключением того, что требуется набивка чисел
> незначащими ведущими нулями до длины "проскуриана" - 2^n.
> Получается, что число длиной, скажем, 1024 цифры обрабатывается хорошо,
> а 1025 - тормозит, как будто бы оно было длиной 2048 цифр.
> В тоже время, библиотечная FFTW, которую я вызываю, может работать
> с ЛЮБЫМ числом точек. Однако, радоваться рано. Всетаки разумнее
> использовать набивку, чтобы гарантировать высокосо
ставное число, только непонятно какую лучше всего, то ли 3*2^n, то ли 3^m*2^n, может p*2^n, или 3*5*2^n...
> 24 марта 2004 г. 21:17:

Лет 5 назад мы считали оптимальную величину дополнения нулями сигнала "плохой длины".
В одномерном и двумерном случаях. Ясно, что результат зависит от ассортимента применяемых "базовых" алгоритмов FFT.
Есть публикации.
Если есть интерес, то поищу электронные версии.

Кстати, забавный результат: даже при длине, равной степени двойки вычислительно выгоднее дополнять нулями.
Например, 288-точечный работает теоретически лучше 256-точечного FFT.



> Лет 5 назад мы считали оптимальную величину дополнения нулями сигнала "плохой длины".

Да, задача звучит именно так.

> Если есть интерес, то поищу электронные версии.
Шли на persicum@front.ru или основные выводы пость сюда.

> Например, 288-точечный работает теоретически лучше 256-точечного FFT.
Ну с этим мало кто согласится, это нонсенс. =)))
Из теории FFT известно, что его сложность пропорциональна ~N*Summa[p(i)],где
p(i) - разложение N на множители, т.е. "периметру" многомерного паралльлепипеда в мультипликативном базисе. Для чисел 256 и 288 сумма делителей одинакова - 16.
А для "равных" чисел - конечно куб 2^n имеет минимальный "периметр".

Так что 2^n - вне конкуренции. С другой стороны, не ясно, как оптимально дополнить каждое конкретное число нулями до нужной длины. Так, "полуторное" FFT 3*2^(n-2) будет
быстрее чем 2^n. Так что 1025 наверное лучше дополнить до 3072 чем до 2048.


> > Лет 5 назад мы считали оптимальную величину
дополнения нулями сигнала "плохой длины".

> Да, задача звучит именно так.

> > Если есть интерес, то поищу электронные версии.
> Шли на persicum@front.ru или основные выводы пость сюда.

> > Например, 288-точечный работает теоретически лучше 256-точечного FFT.
> Ну с этим мало кто согласится, это нонсенс. =)))
Это Вы от неосведомленности :(
> Из теории FFT известно, что его сложность пропорциональна ~N*Summa[p(i)],где
> p(i) - разложение N на множители, т.е. "периметру" многомерного паралльлепипеда в мультипликативном базисе. Для чисел 256 и 288 сумма делителей одинакова - 16.
> А для "равных" чисел - конечно куб 2^n имеет минимальный "периметр".

Именно, что "пропорциональна", т.е. там еще коэффициент живет.

> Так что 2^n - вне конкуренции. С другой стороны, не ясно, как оптимально дополнить каждое конкретное число нулями до нужной длины. Так, "полуторное" FFT 3*2^(n-2) будет
> быстрее чем 2^n. Так что 1025 наверное лучше дополнить до 3072 чем до 2048.

Вообще-то я по синтезу быстрых алгоритмов дискретных преобразований защищался, их сложности...
В трех кандидатских по этой тематике руководителем был...
Думаю, что по этой тематике у меня и моих учеников под сотню публикаций наберется...
Так что Ваше предложение
> Шли на persicum@front.ru или основные выводы пость сюда.
затруднительно реализовать чисто технически: какие из этих десятков работ Вас интересуют в максимальной степени?
Они взаимосвязаны...


Существует ли связь между простыми числами и целочисленными квадратами? Да, поскольку только квадрат с простым числом узлов на его стороне обладает таким свойством, что любая прямая, проходящая через его вершину и любой узел (за исключением других вершин) лежащий на одной из двух противоположных сторон, не пересекает ни одного другого узла рещетки внутри квадрата.
Такое вот замечание, но я хочтел бы узнать у Вас, -- насколько глубоко исследовано это наблюдение и где в литературе можно об этом почитать. По-моему, такие целочисленные квадраты являются наглядной иллюстрацией простых чисел. А если целочисленную решетку факторизовать, то на торе можно получить получить неплохую иллюстрацию делимости. Стоит ли работать над этой темой, или тут все давно описано?
26 марта 2004 г. 03:35:


> Это Вы от неосведомленности :(
> ... там еще коэффициент живет.

Берем Бохвалов-Жидков, "Численные методы", стр. 171, читаем:
"... общее число операций не превосходит CN[p(1)+...+p(r)], здесь С - постоянная, не зависящая от N." =)))
Кстати говоря, интересно было замерить на практике время исполнения real-to-halfcomplex fft в исполнении признанного мирового лидера - проекта fftw.org . Мои замеры показали, что при числе точек 288 время исполнения процедуры на 40% выше, чем для 256 точек. Причем, самой функции исполнения fft предшествует тщательное ПЛАНИРОВАНИЕ с перебором различных вариантов и выбором наискорейшего (разумеется, время планирования я не рассматривал).


> какие из этих десятков работ Вас интересуют в максимальной степени?
Да не нужно мне ничего высылать... Cyclamen Persicum - не профессор и не доцент, а простой любитель околокомпьютерных тем и использует только простейшие понятные методы. Нужны практические рекомендации по удлинению векторов нулями для достижения оптимальной производительности.
Например:
1) Выбираем минимальное N, такое, чтобы 2^N было >= length, замеряем время исполнения
2) Выбираем минимальное N, такое, чтобы 3*2^N было >= length, замеряем время исполнения
3) Выбираем быстрейший из первых двух.

P.S. Недавно мной было открыто составное число Мерсена-Первушина-Меция-Персикума на 64кбит - простое:
2^65536 - 2^23200 + 2^16480 + 1 !!!!!!!!!!
И хотя проверка самого числа занимает где-то полторы минуты,
подбор нужных коэффициентов был очень,очень нелегким делом...


> > Это Вы от неосведомленности :(
> > ... там еще коэффициент живет.

> Берем Бохвалов-Жидков, "Численные методы", стр. 171, читаем:
> "... общее число операций не превосходит CN[p(1)+...+p(r)], здесь С - постоянная, не зависящая от N." =)))
> Кстати говоря, интересно было замерить на практике время исполнения real-to-halfcomplex fft в исполнении признанного мирового лидера - проекта fftw.org . Мои замеры показали, что при числе точек 288 время исполнения процедуры на 40% выше, чем для 256 точек. Причем, самой функции исполнения fft предшествует тщательное ПЛАНИРОВАНИЕ с перебором различных вариантов и выбором наискорейшего (разумеется, время планирования я не рассматривал).

Проект fftw.org
использует достаточно стандартный (примитивный) набор базовых алгоритмов с тщательной программистской проработкой.
В двумерном случае - хуже.
Впрочем, программы там - лучшие из "попсы".

288 = 2^5*3^2

FFT длины, равной степени тройки, работают быстрее, если комплексные константы (корни) и входные данные представлять
не в "стандартной" комплексной форме
a + bi =z,
а в форме
x*w+y*w^2 =z,
где w - корень третьей степени из единицы.

Тогда упрощается умножение на фазовые множители.
(идея: Дюбуа, Венетсапуполос, 1978 и др. более поздние работы)

И для 288 просто. Расщепляем по Гуду-Томасу на 32 и 9.
Все очень шустренько.

Кстати, по желанию заказчика мы искали длину преобразованияв диапазоне 150-280 с минимальным числом операций FFT на отсчет.
Оказалось 216. Реализовано аппаратно. Проверено. Летает.


Hello, ALL !
Приветствую Вас, господа МАТЕМАТИКИ !

Возникла такая вот задача.

Имеется 2 числовых ряда: ( в {} ,будут примеры )

a. Фибоначчи - { 1 2 3 5 8 13 ... } = R1
b. типа Фибоначчи - { 1 3 4 7 11 18 ... } = R2

на _заданном_ отрезке N { N ~ 8-ми байтовое целое, т.е. ~ 2^64 }

Дано множество, вычисляемое по формуле:

C = A * R % N , где

С - вычисленный член множества
А - заданная константа, простое натуральное число
N - отрезок поиска, ( N > R !!! , мощность множества)
R - _любое_ число из R1 или R2
% - операция "остаток от деления" в "C" ,
или mod(N) в математической записи

НАЙТИ: R =?= A * R % N
т. е. имеются ли пересечения рядов R и множества
A * R % N, и найти это(и) пересечение(я) (по возможности).
При решении задачи "в лоб" перебором, при N = 2^32 (4 байта)
P3-833 в чистом DOS "дохнет" :-(
Буду весьма признателен за помощь (желательно алгоритм).

Удачи !
26 марта 2004 г. 11:43:


> Имеется 2 числовых ряда: ( в {} ,будут примеры )

> a. Фибоначчи - { 1 2 3 5 8 13 ... } = R1
> b. типа Фибоначчи - { 1 3 4 7 11 18 ... } = R2

> на _заданном_ отрезке N { N ~ 8-ми байтовое целое, т.е. ~ 2^64 }

> Дано множество, вычисляемое по формуле:

> C = A * R % N , где

> С - вычисленный член множества
> А - заданная константа, простое натуральное число
> N - отрезок поиска, ( N > R !!! , мощность множества)
> R - _любое_ число из R1 или R2
> % - операция "остаток от деления" в "C" ,
> или mod(N) в математической записи

> НАЙТИ: R =?= A * R % N
> т. е. имеются ли пересечения рядов R и множества
> A * R % N, и найти это(и) пересечение(я) (по возможности).

Решение существенно зависит от N. Что известно про это число? Например, является ли оно простым и т.п.?


Все о чем Вы говорите сводится к простому школьному факту.
В более общей формулировке это будет выглядеть так:
В прямоугольнике с взаимно простыми сторонами диагонать не проходит ни через одну внутреннюю узловую точку.
Все дело именно во взаимной простоте!
Насколько я вижу ничего более содержательного отсюда получить нельзя...


> > Имеется 2 числовых ряда: ( в {} ,будут примеры )

> > a. Фибоначчи - { 1 2 3 5 8 13 ... } = R1
> > b. типа Фибоначчи - { 1 3 4 7 11 18 ... } = R2

> > на _заданном_ отрезке N { N ~ 8-ми байтовое целое, т.е. ~ 2^64 }

> > Дано множество, вычисляемое по формуле:

> > C = A * R % N , где

> > С - вычисленный член множества
> > А - заданная константа, простое натуральное число
> > N - отрезок поиска, ( N > R !!! , мощность множества)

Извиняюсь, мощностью фактически будет R !!!
... т к кол-во R << N. ( << - значительно меньшее )

> > R - _любое_ число из R1 или R2
> > % - операция "остаток от деления" в "C" ,
> > или mod(N) в математической записи

> > НАЙТИ: R =?= A * R % N
> > т. е. имеются ли пересечения рядов R и множества
> > A * R % N, и найти это(и) пересечение(я) (по возможности).

> Решение существенно зависит от N. Что известно про это число? Например, является ли оно простым и т.п.?

Да, N простое натуральное число.


Слыш, Михалыч, хочу поделиться с тобой кое-какими соображениями. Насколько я понимаю, быстродействие алгоритма определяется двумя факторами:
1) Теоретическая оценка сложности. Понятно, что при прочих равных алгоритм со сложностью O(n^2) будет работать медленнее,
чем O(n log n). Однако и здесь возможны нюансы: асимптотическое быстродействие не всегда выше фактического, к примеру, быстрая сортировка может уступать сортировке пузырьком при малых входных массивах.
2) Легкость практической реализации с учетом аппаратных особенностей современных ЭВМ. Так, теоретически, числа Мерсенна идеально подходят для модульных операций, но на практике используют составные числа Мерсена, например, 2^544 - 2^32 + 1 вместо 2^521-1. Парадокс в том, что взятие остатка с использованием первого числа производится значительно быстрее и легче вследствие его выравненности под машинное слово.
У меня большие сомнения чтобы тройка "прижилась" на современной двоичной машине. Короче говоря, при наличии DLL можем забенчить твои изыскания, будь ты хоть трижды академик и герой соц.труда, и сравнить с FFTW. Тогда и будем делать выводы. Кстати, FFTW "не боится" троек, fft-3072 раза в полтора быстрее чем fft-4096 работает.

Теперь насчет задачи о наращивании векторов. Я разузнал, как она решается на Great Internet Mersenne Prime Search. Массивы доращиваются до p*2^n, где p=2,3,5,7. Получается гладенькая такая последовательность: 4,5,6,7,8, т.е. в худшем случае нужно увеличить вектор всего на 25%, а не в два раза. Такой вариант меня вполне устроит. Как то раз я уже имел удовольствие спросить насчет Взвешенного DFT, но кроме упоминания каких-то мифических статей ничего не услышал... Так получилось и в этот раз, а ларчик просто открывался. Кстати, среди денежных призов GIMPS, учрежденных за открытие новых чисел, есть и большой приз за существенное повышение производительности программы. А вычисления GIMPS длятся многие недели и месяцы! И если
2*3^n работает заметно быстрее чем 3*2^n, you have a chance... =))).


> > > Имеется 2 числовых ряда: ( в {} ,будут примеры )

> > > a. Фибоначчи - { 1 2 3 5 8 13 ... } = R1
> > > b. типа Фибоначчи - { 1 3 4 7 11 18 ... } = R2

> > > на _заданном_ отрезке N { N ~ 8-ми байтовое целое, т.е. ~ 2^64 }

> > > Дано множество, вычисляемое по формуле:

> > > C = A * R % N , где

> > > С - вычисленный член множества
> > > А - заданная константа, простое натуральное число
> > > N - отрезок поиска, ( N > R !!! , мощность множества)

> Извиняюсь, мощностью фактически будет R !!!
> ... т к кол-во R << N. ( << - значительно меньшее )

Сами же пишете

> > > R - _любое_ число из R1 или R2

Получается, что мощность - это лобое число. Нонсенс. Как это понимать?

Далее, зачем нужно условие R<Скажем, если бы R=N/2 - подошло в качестве решения или нет? Или R=N/100? Или R=sqrt(N)?

> > > % - операция "остаток от деления" в "C" ,
> > > или mod(N) в математической записи

> > > НАЙТИ: R =?= A * R % N

Судя сопровождающему по тексту, R в левой и правой частях обозначают разные элементы ряда. Так? Тогда лучше было бы обозначить их разными буквами.

Если же интересует наличие такого R, что
R = (A*R)%N
то для этого достаточно решить это сравнение относительно R:
R = (A-1)^(-1) (mod N)
и проверить является ли это R элементом ряда...

> > > т. е. имеются ли пересечения рядов R и множества
> > > A * R % N, и найти это(и) пересечение(я) (по возможности).

> > Решение существенно зависит от N. Что известно про это число? Например, является ли оно простым и т.п.?

> Да, N простое натуральное число.

Что именно интересует:
1) сам факт пересечения;
2) какой-то его элемент;
3) все элементы из пересечения
???

Пока лишь замечу, что то, что вы обозначили C и называете элементами множества, является по сути так же последовательностью типа Фибоначчи по модулю N. Дело в том, что если x1 + x2 = x3, то
((A*x1)%N + (A*x2)%N)%N = (A*x3)%N


Сообщение Андрей Викторович 29 марта 2004 г. 20:02
Тема: Задача про простое число.

Есть простое число 1601. Его начали делить последовательно делить на все числа 2,3,4... . До какого числа нужно делить это число, чтобы с увереностью сказать, что оно простое. Зарание Спасибо за помощь.

--------------------------------------------------------------------------------
Re: Задача про простое число. СанитарЖеня 29 марта 20:08 нов
В ответ на: Задача про простое число. от Андрей Викторович , 29 марта 2004 г.:
> Есть простое число 1601. Его начали делить последовательно делить на все числа 2,3,4... . До какого числа нужно делить это число, чтобы с увереностью сказать, что оно простое. Зарание Спасибо за помощь.
До корень квадратный из N.

--------------------------------------------------------------------------------
Re: Задача про простое число. Борик 30 марта 00:53 нов
В ответ на Re: Задача про простое число. от СанитарЖеня , 29 марта 2004 г.:
> > Есть простое число 1601. Его начали делить последовательно делить на все числа 2,3,4... . До какого числа нужно делить это число, чтобы с увереностью сказать, что оно простое. Зарание Спасибо за помощь.
> До корень квадратный из N.

Более того, следует проверять делимость лишь на простые числа (меньшие сорока):
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 и 37...
И все!



Еще одна задачка.
Пусть есть число, скажем, 10^10+9^9+8^8+...+2^2+1^1.
Сколько первых простых, а именно, 2,3,5,7... нужно взять,
чтобы проверив условие малой теоремы Ферма a^(p-1)=1 (mod p)
(в другом варианте - проведя тест Рабина), можно было С УВЕРЕННОСТЬЮ сказать,
простое оно или составное???


> > > > Имеется 2 числовых ряда: ( в {} ,будут примеры )
> > > > a. Фибоначчи - { 1 2 3 5 8 13 ... } = R1
> > > > b. типа Фибоначчи - { 1 3 4 7 11 18 ... } = R2
> > > > на _заданном_ отрезке N { N ~ 8-ми байтовое целое, т.е. ~ 2^64 }
> > > > Дано множество, вычисляемое по формуле:
> > > > C = A * R % N , где
> > > > С - вычисленный член множества
> > > > А - заданная константа, простое натуральное число
> > > > N - отрезок поиска, ( N > R !!! , мощность множества)

> > Извиняюсь, мощностью фактически будет R !!!
> > ... т к кол-во R << N. ( << - значительно меньшее )
> Сами же пишете

Я Сам запутался, малость ;-)

> > > > R - _любое_ число из R1 или R2
> Получается, что мощность - это лобое число. Нонсенс. Как это понимать?

Мощность множ-ва это _количество_ его элементов (дискр. матем.)

> Далее, зачем нужно условие R<

N это 8-ми байтовое целое, т.е. ~ 2^64
_Количество_ членов ряда Фибоначи на промежутке 1...N значительно
меньше числа N. (~= 5 000 )

> Скажем, если бы R=N/2 - подошло в качестве решения или нет? Или R=N/100? Или R=sqrt(N)?
???
> > > > % - операция "остаток от деления" в "C" ,
> > > > или mod(N) в математической записи
> > > > НАЙТИ: R =?= A * R % N

> Судя сопровождающему по тексту, R в левой и правой частях обозначают разные элементы ряда. Так? Тогда лучше было бы обозначить их разными буквами.

Да, именно так !
А одна буква, т к это одно и то-же множ-во, из элементов ( R1 & R2 ).

> Если же интересует наличие такого R, что
> R = (A*R)%N
> то для этого достаточно решить это сравнение относительно R:
> R = (A-1)^(-1) (mod N)
> и проверить является ли это R элементом ряда...

Да !
Сейчас решается так: (схематически)
===============
Цикл по всем R
С = (A*R)%N
Цикл по всем R
Если (С == R)
{
PRINT "Ok !"
BREAK;
}
кон цикла
кон цикла
==============
Вот эта проверка (внутренний цикл) и забирает львиную долю
процесорного времени, это фактически перебор :-( всех R по R
Вот если-бы _напрямую_ (по формуле) указать что скажем
при таком-то А, пятый элемент ряда Фибоначи умноженный на А по модулю N,
совпадает скажем например, с 27-м элементом ряда Фибоначи (из R1 или R2).
Нужно именно такое решение, если оно существует вообще :-(

> > > > т. е. имеются ли пересечения рядов R и множества
> > > > A * R % N, и найти это(и) пересечение(я) (по возможности).

Да !!!

> > > Решение существенно зависит от N. Что известно про это число? Например,
> > >является ли оно простым и т.п.?
> > Да, N простое натуральное число.

> Что именно интересует:
> 1) сам факт пересечения;
> 2) какой-то его элемент;

п1 + п2 ;-)

> 3) все элементы из пересечения
> ???

Если п1 + п2 будут решены, п3 не имеет смысла,
т.к. ищется только наличие такого вхождения в множ-во R.
См. выше алгоритм.

> Пока лишь замечу, что то, что вы обозначили C и называете элементами множества, >является по сути так же последовательностью типа Фибоначчи по модулю N. Дело в

... да, но умноженной на константу A.
... а константа A имеет тот-же порядок что и N ( ~ 2^64, но обязательно A < N )

>том, что если x1 + x2 = x3, то ((A*x1)%N + (A*x2)%N)%N = (A*x3)%N

Точно !!! Как я сам этого не увидел :-(
Тогда получается что нужно искать число Фибоначи из ряда Фибоначи
умноженного на константу A. Такое решение (формула) _тоже_ устраивает.
Даже без учёта mod(N).


> Пусть есть число, скажем, 10^10+9^9+8^8+...+2^2+1^1.
> Сколько первых простых, а именно, 2,3,5,7... нужно взять,

Почему именно простых? Здесь простота особой роли не играет.

> чтобы проверив условие малой теоремы Ферма a^(p-1)=1 (mod p)
> (в другом варианте - проведя тест Рабина), можно было С УВЕРЕННОСТЬЮ сказать,
> простое оно или составное???

Для теста Милера-Рабина в предположении справедливости расширенной гипотезы Римана достаточно проверить все a из отрезка [2,70*ln(p)^2], чтобы с уверенностью утверждать простоту p.
См. http://www.cryptography.ru/db/msg.html?mid=1161235&uri=node32.html


Здравствуйте, Relf!
Вы писали :
>> Для теста Милера-Рабина в предположении справедливости расширенной гипотезы Римана достаточно проверить все a из отрезка [2,70*ln(p)^2], чтобы с уверенностью утверждать простоту p.
> См. http://www.cryptography.ru/db/msg.html?mid=1161235&uri=node32.html

Там в конце приписка -
Алгоритм Миллера принципиально отличается от алгоритма 5, так как полученное с его помощью утверждение о том, что число - составное, опирается на недоказанную расширенную гипотезу Римана и потому может быть неверным. В то время как вероятностный алгоритм 5 дает совершенно правильный ответ для составных чисел. Несмотря на отсутствие оценок сложности, на практике он работает вполне удовлетворительно -
конец цитаты.

Как это понимать ?

Андрей Сапожников.


> >> Для теста Милера-Рабина в предположении справедливости расширенной гипотезы Римана достаточно проверить все a из отрезка [2,70*ln(p)^2], чтобы с уверенностью утверждать простоту p.
> > См. http://www.cryptography.ru/db/msg.html?mid=1161235&uri=node32.html

> Там в конце приписка -
> Алгоритм Миллера принципиально отличается от алгоритма 5, так как полученное с его помощью утверждение о том, что число - составное, опирается на недоказанную расширенную гипотезу Римана и потому может быть неверным. В то время как вероятностный алгоритм 5 дает совершенно правильный ответ для составных чисел. Несмотря на отсутствие оценок сложности, на практике он работает вполне удовлетворительно -
> конец цитаты.

> Как это понимать ?

Похоже, что в этой приписке описка. Должно быть ``...так как полученное с его помощью утверждение о том, что число - ПРОСТОЕ, опирается...''.

Алгоритм Миллера и алгоритм Миллера-Рабина (который обозначен там номером 5) проверяют одни и те же соотношения. Отличие состоит в том, что Миллер перебирает все a из отрезка [2,70*ln(p)^2], а Миллер-Рабин выбирает некоторое количество значений a случайным образом. Первый алгоритм опирается в доказательстве простоты на расширенную гипотезу Римана, второй - на оценку числа хороших/плохих значений a и дает оценку сверху для вероятности ошибки.

Ошибка и там, и там может быть только такого типа: составное число названо простым. Для алгоритма Миллера такая ошибка может возникнуть только если вдруг расширенная гипотеза Римана окажется неверна, а для алгоритма Миллера-Рабина вероятность ошибки заведомо может быть сделана сколь угодно малой.


Да...
Алгоритм хоть и полиномальный, но все равно ужасно трудоемкий!
Для числа 1024 бит получается, что нужно взять, грубо говоря, 70000000 свидетелей.
И потом, алгоритм дает только, что число имеет вид p^n. А как убедиться,
что n=1, не делением же до корня квадратного...


> Да...
> Алгоритм хоть и полиномальный, но все равно ужасно трудоемкий!
> Для числа 1024 бит получается, что нужно взять, грубо говоря, 70000000 свидетелей.

Поэтому простоту так не доказывают ;)

> И потом, алгоритм дает только, что число имеет вид p^n. А как убедиться,
> что n=1, не делением же до корня квадратного...

Достаточно извлечь все корни N^(1/k), где k=2..[log(N)], и убедится что среди них нет целых. Это делается, например, путем извлечения целочисленного корня r=[N^(1/k)] (методом Ньютона) и последующей проверкой на равенство N=?=r^k.


> Подскажите, где можно посмотреть таблицу простых чисел больше 128 двоичных разрядов?

Mathematica:
Do[If[PrimeQ[2^128 + i], Print[2^128 + i]], {i, 1, 1000}]

340282366920938463463374607431768211507
340282366920938463463374607431768211537
340282366920938463463374607431768211621
340282366920938463463374607431768211729
340282366920938463463374607431768211841
340282366920938463463374607431768211877
340282366920938463463374607431768211919
340282366920938463463374607431768212029
340282366920938463463374607431768212081
340282366920938463463374607431768212213
340282366920938463463374607431768212273
340282366920938463463374607431768212303

Не стоит благодырностей :)


> Поэтому простоту так не доказывают ;)

А ее вообще не доказывают. За исключением некоторых простых специального
вида, Мерсена, Ферма, обобщенных именных и т.п.
Так, для чисел Ферма достаточно взять только один свидетель - 3.
(Я конечно знаю и то, что это все-равно не поможет, т.к. их всего только 5 первых штук существует =). Мерсена тоже железно проверяются за время,
эквивалентное одному раунду Рабина-Миллера.
Уважаемый Relf - какой общий алгоритм вы посоветуете, что-бы
не требовалась факторизация ни в каком виде (типа разложение N-1 и т.п.)?
Кстати, Вы разобрались с новоявленным и уже ставшим легендарным
полиномиальным Индийским алгоритмом проверки на простоту?
Какова его сложность если мерить в раундах теста Рабина-Миллера?
Наверняка без PowerMod там не обошлось...


Подскажите, где можно посмотреть таблицу простых чисел (более 128 двоичных разрядов)? Заранее благодарен.
31 марта 2004 г. 17:23:


> > Поэтому простоту так не доказывают ;)

> А ее вообще не доказывают.

Часто - да, не доказывают, но не "вообще". Для простоты давно разработано понятие сертификата, который позволяет легко воспроизвести (проверить) строгое доказательство.
При необходимости сертификат находят и сопровождают им простое число.

> За исключением некоторых простых специального
> вида, Мерсена, Ферма, обобщенных именных и т.п.
> Так, для чисел Ферма достаточно взять только один свидетель - 3.
> (Я конечно знаю и то, что это все-равно не поможет, т.к. их всего только 5 первых штук существует =). Мерсена тоже железно проверяются за время,
> эквивалентное одному раунду Рабина-Миллера.

Хороший обзор дан тут: http://www.utm.edu/research/primes/prove/index.html

> Уважаемый Relf - какой общий алгоритм вы посоветуете, что-бы
> не требовалась факторизация ни в каком виде (типа разложение N-1 и т.п.)?
> Кстати, Вы разобрались с новоявленным и уже ставшим легендарным
> полиномиальным Индийским алгоритмом проверки на простоту?

Угу. Хороший алгоритм.

> Какова его сложность если мерить в раундах теста Рабина-Миллера?

Сложность Миллера-Рабина оценивается величиной типа O(ln(p)^3). Индийский алгоритм доказанно не сложнее O(ln(p)^12), и не сложнее O(ln(p)^6), если справедлива некоторая правдоподобная гипотеза.

> Наверняка без PowerMod там не обошлось...

Без этого никуда ;)


> > > > > Имеется 2 числовых ряда: ( в {} ,будут примеры )
> > > > > a. Фибоначчи - { 1 2 3 5 8 13 ... } = R1
> > > > > b. типа Фибоначчи - { 1 3 4 7 11 18 ... } = R2
> > > > > на _заданном_ отрезке N { N ~ 8-ми байтовое целое, т.е. ~ 2^64 }
> > > > > Дано множество, вычисляемое по формуле:
> > > > > C = A * R % N , где
> > > > > С - вычисленный член множества
> > > > > А - заданная константа, простое натуральное число
> > > > > N - отрезок поиска, ( N > R !!! , мощность множества)

[...]

> Тогда получается что нужно искать число Фибоначи из ряда Фибоначи
> умноженного на константу A. Такое решение (формула) _тоже_ устраивает.
> Даже без учёта mod(N).

Без mod N все просто.
Обозначим везде далее h=sqrt(5) и g=(1+h)/2 - золотое сечение.

Переформулируем задачу так: найти два члена последовательности Фибоначчи u(n) и u(m) такие, что u(m)=A*u(n).

1. По известному свойству НОД(u(i),u(j))=u(НОД(i,j)) для всех i,j.
В частности, для i=n, j=m имеем НОД(u(n),u(m))=u(НОД(n,m)), а с другой стороны НОД(u(n),u(m))=НОД(u(n),A*u(n))=u(n).
Откуда заключаем, что НОД(n,m)=n или другими словами m делится на n.

2. Покажем, что число p=m/n обязано быть простым. Если это не так, и m=a*b*n, где a,b>1, то по тому же свойству получаем, что u(m) делится на u(b*n), которое в свою очередь делится на u(n). Таким образом,
A = u(m)/u(n) = (u(m)/u(b*n))*(u(b*n)/u(n)),
причем отношения в скобках являются целыми и строго большими единицы. Но это противоречит простоте числа A.

3. Рассмотрим случай p=2. Известно, что u(2*n)=u(n)*v(n), где последовательность v(n) задается соотношениями:
v(0)=2, v(1)=1
v(k+1)=v(k)+v(k-1)
Кроме того справедлива формула v(k)=round(g^k) для k>=2. (*)

Наша задача сводится к проверке является ли A элементом последовательности v(k). В виду формулы (*) легко узнать возможный номер такого элемента: round(log(A)/log(g)).
Далее достаточно вычислить элемент с таким номером и сравнить его с A.


4. Если p - нечетное простое, то можно доказать, что A = 5^((p-1)/2) (mod p). Правая часть этого сравнения равна 1 или -1 в зависимости от того является 5 квадратичным вычетом mod p или нет.
Отсюда следует, что p является делителем либо A+1, либо A-1. Находим все простые делители чисел A+1 и A-1 и перебираем их в качестве p.
Воспользуемся формулой u(k)=round(g^k/h) (следствие формулы Бине). Имеем
A = u(p*n)/u(n) = round(g^(p*n)/h)/round(g^n/h)
Откуда следует, что
g^((p-1)*n)+h*g^((p-2)*n) >= A >= g^((p-1)*n)-h*g^((p-2)*n)
что в свою очередь дает оценку на n и все сводится к небольшому перебору.


> > > Поэтому простоту так не доказывают ;)

> > А ее вообще не доказывают.

> Часто - да, не доказывают, но не "вообще". Для простоты давно разработано понятие сертификата, который позволяет легко воспроизвести (проверить) строгое доказательство.
> При необходимости сертификат находят и сопровождают им простое число.

> > За исключением некоторых простых специального
> > вида, Мерсена, Ферма, обобщенных именных и т.п.
> > Так, для чисел Ферма достаточно взять только один свидетель - 3.
> > (Я конечно знаю и то, что это все-равно не поможет, т.к. их всего только 5 первых штук существует =). Мерсена тоже железно проверяются за время,
> > эквивалентное одному раунду Рабина-Миллера.

> Хороший обзор дан тут: http://www.utm.edu/research/primes/prove/index.html

> > Уважаемый Relf - какой общий алгоритм вы посоветуете, что-бы
> > не требовалась факторизация ни в каком виде (типа разложение N-1 и т.п.)?
> > Кстати, Вы разобрались с новоявленным и уже ставшим легендарным
> > полиномиальным Индийским алгоритмом проверки на простоту?

> Угу. Хороший алгоритм.

> > Какова его сложность если мерить в раундах теста Рабина-Миллера?

> Сложность Миллера-Рабина оценивается величиной типа O(ln(p)^3). Индийский алгоритм доказанно не сложнее O(ln(p)^12), и не сложнее O(ln(p)^6), если справедлива некоторая правдоподобная гипотеза.

> > Наверняка без PowerMod там не обошлось...

> Без этого никуда ;)

> Извините, что вмешиваюсь, но, кажется Бернштейн (D.J. Bernstein) понизил показатель в экспоненте с 6 до 4-х. [D. J. Bernstein, "Proving primality in essentially quartic random time," (2003) См. http://cr.yp.to/papers.html]


>> Пусть есть число, скажем, 10^10+9^9+8^8+...+2^2+1^1.
>> Сколько первых простых, а именно, 2,3,5,7... нужно взять,
> Почему именно простых? Здесь простота особой роли не играет.

Всетаки, брать малые простые - это была неплохая идея:
If n < 1,373,653 is a both 2 and 3-SPRP, then n is prime.
If n < 25,326,001 is a 2, 3 and 5-SPRP, then n is prime.
If n < 25,000,000,000 is a 2, 3, 5 and 7-SPRP, then either n = 3,215,031,751 or n is prime. (This is actually true for n < 118,670,087,467.)
If n < 2,152,302,898,747 is a 2, 3, 5, 7 and 11-SPRP, then n is prime.
If n < 3,474,749,660,383 is a 2, 3, 5, 7, 11 and 13-SPRP, then n is prime.
If n < 341,550,071,728,321 is a 2, 3, 5, 7, 11, 13 and 17-SPRP, then n is prime.

> Извините, что вмешиваюсь, но, кажется Бернштейн (D.J. Bernstein) понизил показатель в экспоненте с 6 до 4-х. [D. J. Bernstein, "Proving primality in essentially quartic random time," (2003) См. http://cr.yp.to/papers.html]

Знаем-знаем... =))) Из того же источника:
Berrizbeitia [Berrizbeitia2003] found a way to save time in AKS-type primality proofs for some primes n, reducing the exponent from 6+o(1) to 4+o(1). Cheng [Cheng2003] extended Berrizbeitia's idea to more primes n, and Bernstein [Bernstein2003] extended it to all primes n. The algorithm for finding these proofs relies on some randomness, unlike the original AKS algorithm.


> Подскажите, где можно посмотреть таблицу простых чисел (более 128 двоичных разрядов)? Заранее благодарен.
> 31 марта 2004 г. 17:23:

теория чиесел


Физика в анимациях - Купить диск - Тесты по физике - Графики on-line

Реклама:
Rambler's Top100