?

Log in

No account? Create an account
http://bash.org.ru/quote/399558 Введите любое 11-значное простое… - Sitting on the top of the mushroom.
September 27th, 2008
10:28 pm
[User Picture]

[Link]

Previous Entry Share Next Entry
http://bash.org.ru/quote/399558
Введите любое 11-значное простое число, чтобы продолжить...

UPD:
http://www.bigprimes.net/primality_test.php
Как они ухитряются так быстро управляться с 11-значными простыми - не понимаю.

Current Location: в кресле

(22 comments | Leave a comment)

Comments
 
[User Picture]
From:linoja
Date:September 27th, 2008 06:44 pm (UTC)
(Link)
да, на сегодня оно явно лучшее
[User Picture]
From:helavis
Date:September 27th, 2008 08:25 pm (UTC)
(Link)
Сравнивают с таблицей чисел и вычисляют только для совсем больших?
[User Picture]
From:randir_spb
Date:September 27th, 2008 09:46 pm (UTC)
(Link)
Нет, там все-таки перебор. См. ниже ответ Макса.
[User Picture]
From:cybercat
Date:September 27th, 2008 09:15 pm (UTC)
(Link)
76537565231
[User Picture]
From:cybercat
Date:September 27th, 2008 09:20 pm (UTC)
(Link)
А секрет у нихних несложный ;-)

for(i=5; i<=Stop; i+=di, di=6-di) {
if (N%i == 0) return i;
};
[User Picture]
From:randir_spb
Date:September 27th, 2008 09:48 pm (UTC)
(Link)
А-а, то есть все-таки перебирают до квадратного корня и делят только на первые простые числа и на числа вида 6n+-1, так я понимаю.
[User Picture]
From:randir_spb
Date:September 28th, 2008 05:57 am (UTC)
(Link)
Все-таки там что-то еще есть:
11111111111 is (proven) composite (failed sprp test base 2).
То есть на множители не разложили, но то, что оно составное - доказали.
То есть там еще какие-то тесты работают, коих много и большинство из них для меня, увы, не понятны.

Мало витаминов ел, видимо.
[User Picture]
From:randir_spb
Date:September 28th, 2008 06:01 am (UTC)
(Link)
Хотя SPRP - довольно простой тест. Не все так страшно...
From:aratanwe
Date:September 27th, 2008 09:51 pm (UTC)
(Link)
А одиннадцать единичек не подходит? Понмю раньше это был очень популярный серийник или ключик к хакнутым прогам. (старые старые 90-ые) :)
[User Picture]
From:randir_spb
Date:September 28th, 2008 05:58 am (UTC)
(Link)
Нет, пишут, что оно составное. ЖВ-)))
11111111111 is (proven) composite (failed sprp test base 2).
[User Picture]
From:cybercat
Date:September 28th, 2008 06:19 am (UTC)
(Link)
Зато 11111111113 - простое ;-)
[User Picture]
From:hcube
Date:September 28th, 2008 09:46 am (UTC)
(Link)
У меня честно говоря впечатление, что простота числа определяется алгоритмом логарифмической сложности. Поиск множителей до корня квадратного из числа - это сложность степени 1/2 ;-)

По хорошему, правильным было бы использовать решето эратосфена - т.е. перед проверкой числа на делитель, также проверить делитель на то, простой ли он. И делители делителя тоже ;-)

А в идеале, еще и результат проверки должен кэшироваться. Причем кэш должен использоваться для чисел, сложность прямой проверки которых выше, чем сложность алгоритма выборки числа из ассоциативного массива. Т.е. грубо говоря до 1000 числа проверяются просто тупой проверкой делителя, а выше - при проверке делителя СНАЧАЛА производится его поиск в списке простых чисел, и только потом уже - проверка на простоту на младших делителях.
[User Picture]
From:randir_spb
Date:September 28th, 2008 03:30 pm (UTC)
(Link)
Увы, уже на 11-значных числах решето Эратосфена становится неприемлемо с точки зрения расхода памяти.
А там заявлено до 15 десятичных знаков.
[User Picture]
From:hcube
Date:September 28th, 2008 04:19 pm (UTC)
(Link)
Ну не впрямую же ;-) Тут как - кэшировать надо то, что часто используется и трудно считается. То что считается просто - надо считать.

Кроме того, я бы не сказал, что расход памяти так уж велик. Плотность простых чисел очень быстро падает с ростом значения. 15 десятичных знаков - это 5 триад, 40 бит, тысяча триллионов ;-) Согласно Гауссу, общее число простых чисел приблизительно равно x/ln(x).

Это значит, что для помянутых 10 триллионов надо хранить простые числа для ПРОВЕРКИ МНОЖИТЕЛЕЙ. А также - множителей множителей. Это уж задача попроще, а? ;-) Для 16 знаков множитель уже 8 знаков, а множитель множителя - 4 знака всего лишь. Т.е. надо хранить всего-навсего 1200 чисел и делать по ним поиск. Для этого вполне пойдет бинарное дерево.

После этого, проверка 100 миллионов делителей выглядит так - каждый делитель сначала проверяется на то, что он простой (а для этого в свою очередь у него не должно быть делителя больше чем корень квадратный из него), а затем проверяется, делится ли нацело на него число. Коэффициент прореживания примерно равен 1/ln(x), т.е. на 100 миллионах придется проверить порядка 10 миллионов делителей.

Хмм... а пожалуй что не оправдывается составление таблицы. Ну да, делитель можно проверить на то, делится ли он, относительно быстро. Но похоже, что проще число поделить, чем проверять делитель - деление занимает тактов 5, а проверка делителя - все 500-600, учитывая перебор возможных делителей уже для него. Оно в принципе оправдано - но для очень больших чисел. Нереально больших ;-D

Не, тут что-то другое. С другой стороны, эта простенькая веб-формочка вполне может быть мордой для небольшого суперкомпьютера ;-)
[User Picture]
From:randir_spb
Date:September 28th, 2008 04:38 pm (UTC)
(Link)
Простенькая формочка для обработки использует javascript.
Впрочем, составные числа проверяются немного более умным образом, что позволяет сильно сократить время, как я понимаю.
[User Picture]
From:hcube
Date:September 28th, 2008 04:54 pm (UTC)
(Link)
Ага, посмотрел код... слушай, по-моему, они жульничают ;-) Проверка-то там есть, да... но...

var TrialLimit = 1300; // Should be bigger, like 10000

Точно. Жульничают.

Они не целиком проверяют число, а только на делители меньше 1300. Кроме того, там есть некий мухлеж с самими делителями - следующий делитель подбирается с перепрыгом через 2-4 числа - в то время как реально существуют простые числа, находящиеся рядом.

Хотя конечно вероятность сбоя алгоритма небольшая - порядка 1%. На что и расчет ;-)
[User Picture]
From:randir_spb
Date:September 28th, 2008 06:53 pm (UTC)
(Link)
Посмотри внимательно. Там, если я что-то понимаю, есть еще проверки.
Перепрыг через 2-4 числа как раз честный, так как все простые числа больше 3 могут быть представлены в виде 6k+-1, где k-целое.
Дальше они используют SPRP, про него написано тут. Как это работает, я уже не ловлю.
Дальше, если я что-то правильно понимаю, существуют еще какие-то методы.
[User Picture]
From:hcube
Date:September 28th, 2008 07:36 pm (UTC)
(Link)
Там некое хитрое преобразование идет бинарное. Я честно говоря тоже не понимаю, как оно пашет. Похоже, что а - это степенной показатель, а суть алгоритма заключается в суровом возведении в степень с ограничением. Но ЗАЧЕМ оно надо, я не догоняю, честно говоря. В двоичной-то форме тоже ведь надо проверять, делится число или нет. В общем, у меня впечатление, что честно они проверяют те самые нижние делители, а верхние - того. Проверяют сильно выборочно.

Again all integers n > 1 which fail this test are composite; integers that pass it _might_ be prime.

It has been proven ([Monier80] and [Rabin80]) that the strong probable primality test is wrong no more than 1/4th of the time (3 out of 4 numbers which pass it will be prime).

Тут у нас 7 таких тестов подряд. Это дает вероятность в 1/2^14, если тесты между собой не связаны - это порядка 1/17000. Но НЕ НОЛЬ. Примерно, из 100 триллионов простых чисел в заданном интервале, остается

А - да, там еще есть предварительный тест, который отловит делители вплоть до миллиона - это уменьшит вероятность еще в миллион раз - опять же, если тесты не связаны. Но все равно остается порядка 3000 чисел, которые ПРОЙДУТ этот тест, не будучи простыми.
[User Picture]
From:randir_spb
Date:September 28th, 2008 08:22 pm (UTC)
(Link)
Значит или там есть еще что-то или одно из двух. Потому что рапортует оно именно proven primary.
[User Picture]
From:hcube
Date:September 28th, 2008 04:34 pm (UTC)
(Link)
From:(Anonymous)
Date:November 25th, 2008 04:42 pm (UTC)
(Link)
14! + 1
Простое 11значное число.
Лол?
[User Picture]
From:randir_spb
Date:November 25th, 2008 09:30 pm (UTC)
(Link)
На каком основании оно простое? Не делится ни на одно число меньше 14 - это да. Но...
14! + 1 = 87178291201.

87178291201 is not a prime! It is 23 * 3790360487
Powered by LiveJournal.com