Комментарии 20
Спасибо за интересную статью! Получил истинное удовольствие, сходил на сайт GIMPS и установил Prime95:) Возник тут сразу вопрос. А есть какое-нибудь более-менее активное применение этим числам? В криптографии, например.
+2
Ниже вы видите памяти этого компьютера, содержащий 256 слов по 37 бит каждое.
Спасибо за интересную статью но, это блок с элт и вряд-ли блок памяти. Скорее всего вывода или диагностики.
+1
20-е простое число Мерсенна было обнаружено Александром Гурвицем в ноябре 1961 года в результате проведения 50-минутного теста Люка-Лемера на IBM 7090. Ниже мы воспроизводим эти результаты (на это потребовалось около 151 секунд машинного времени на современном одноядерном ноутбуке)
50минут vs 151 секунда — т.е. современный одноядерный ноутбук всего в 20 раз эффективнее компьютера 55 летней давности? Либо тут опечатка, либо с эффективностью что-то не то. Быстрый гуглинг показывает эффективность 7090 в 100KFlops, современный ноутбук по хорошему должен бы единицы гигафлопс выдавать
+1
Я бы предположил, что Гурвиц писал сильно оптимизированный код под конкретную платформу, а тут вычисления в Mathematica (интерпретатор?) с открытым скайпом и другими оверхедами.
0
Либо тут опечатка, либо с эффективностью что-то не то.
Я посмотрел статью, на которую в тексте приводили ссылку.
Theorem.
If S(1) = 4 and S(n+1) = S(n)^2-2 then Mp is prime if and only if S(p-i) = 0 (mod Mp).
The test takes about 50 minutes of machine time for p = 4423
Я так понимаю, 50 минут уходило на то, чтобы для одного фиксированного p, взять Mp=2^p-1 и потом вычислить по его модулю S(p-1).
Что именно делают и меряют в wolfram alpha — мне не понятно.
Я попробовал простое решение "в лоб" на Scala — оно перебирает все простые числа до p=5000 за 30 секунд.
максимально простой код
val start = System.currentTimeMillis()
var count = 0
for (p <- 2 to 5000 if BigInt(p).isProbablePrime(20)) {
val mp = BigInt(2).pow(p) - 1
if (mp.isProbablePrime(20)) {
count += 1
println(s"$count numbers found, time = ${System.currentTimeMillis() - start}ms")
println(s"2^$p - 1 = $mp")
}
}
Ещё попробовал алгоритм Люка-Лермера, для p = 4423 проверяет за 0.2 секунды. Получается, в 15000 раз быстрее, чем за 50 минут)
Перебор для всех простых p от 2 до 5000, как ни странно, у меня работает за те же 30 секунд.
тест Люка-Лермера на википедии
код с алгоритмом
def lucasLehmer(p: Int): Boolean = {
var S = BigInt(4)
val mp = BigInt(2).pow(p) - 1
for (k <- 1 until (p - 1)) {
S = (S * S - 2) mod mp
}
S == 0
}
val start = System.currentTimeMillis()
lucasLehmer(4423)
println(s"time = ${System.currentTimeMillis() - start}ms")
0
В Wolfram Language тест Люка-Лемера (на моем компьютере 7-летней давности) для p = 4423 выполняется за:
![](https://habrastorage.org/r/w1560/files/5c5/f8f/ae2/5c5f8fae2f864681886304e1581aafa1.png)
Дело в том, что функция Джона lucasLehmerPrep работает так: если за время, равное
(количество цифр в записи числа)*0.05 секунд
встроенная навороченная функция PrimeQ не дает ответа, применяется тест Люка-Лемера. Именно поэтому применение её к диапазону от 1 до 1000-го простого числа занимает 150 секунд (у Джона).
Также учтите, что p_1000 = 7919, так что вы должны были проводить тестирование не для простых чисел меньших 5000, а до 8000. Время существенно изменится.
Я проделал теже вычисления у себя на компьютере, получилось 1926 секунд (для lucasLehmerPrep) и 54 секунды для чисто теста Люка-Лемера (так как, получается, мой компьютер медленнее компьютера Джона примерно в 12.84, то вычисление теста Люка-Лемера для p = 4423 заняло бы у него примерно 0.0049 с (т. е. в 183673 раза быстрее), что заметно быстрее, чем у вас):
![](https://habrastorage.org/r/w1560/files/b02/39c/520/b0239c520d5a4d4385742305596d4966.png)
![](https://habrastorage.org/files/5c5/f8f/ae2/5c5f8fae2f864681886304e1581aafa1.png)
Дело в том, что функция Джона lucasLehmerPrep работает так: если за время, равное
(количество цифр в записи числа)*0.05 секунд
встроенная навороченная функция PrimeQ не дает ответа, применяется тест Люка-Лемера. Именно поэтому применение её к диапазону от 1 до 1000-го простого числа занимает 150 секунд (у Джона).
Также учтите, что p_1000 = 7919, так что вы должны были проводить тестирование не для простых чисел меньших 5000, а до 8000. Время существенно изменится.
Я проделал теже вычисления у себя на компьютере, получилось 1926 секунд (для lucasLehmerPrep) и 54 секунды для чисто теста Люка-Лемера (так как, получается, мой компьютер медленнее компьютера Джона примерно в 12.84, то вычисление теста Люка-Лемера для p = 4423 заняло бы у него примерно 0.0049 с (т. е. в 183673 раза быстрее), что заметно быстрее, чем у вас):
![](https://habrastorage.org/files/b02/39c/520/b0239c520d5a4d4385742305596d4966.png)
0
*промахнулся*
0
я десять тысяч раз извиняюсь, возможно это все так и должно быть запутанно, но (сугубо мое лично имхо, уберите помидоры) числа мерсена легко заходят через двоичное представление. для 2^n-1 это просто число из n двоичных единиц. И делиться на что бы то ни было оно может только если n не простое (это очевидно если представить двоичное умножение) — причем разложение числа 2^n -1 для составного n тривиально — это 2^x-1, где x — поочередно множители n и соотв. результат деления 2^n-1 на 2^x-1
Ну и с пониманием этого факта все остальные свойства этих чисел тоже становятся либо тривиальны либо более понятны.
Подробнее думаю не стоит — тусовка програмерская, должны понять.
Ну и с пониманием этого факта все остальные свойства этих чисел тоже становятся либо тривиальны либо более понятны.
Подробнее думаю не стоит — тусовка програмерская, должны понять.
0
Ваши рассуждения уже в первом абзаце не верны.
Речь идет как раз о простых числах Мерсенна, у которых n — простое число и которые в свою очередь являются простыми числами.
![](https://habrastorage.org/r/w1560/files/57f/796/c97/57f796c97cd841b8a1b9cdc7b37a1777.png)
Речь идет как раз о простых числах Мерсенна, у которых n — простое число и которые в свою очередь являются простыми числами.
![](https://habrastorage.org/files/57f/796/c97/57f796c97cd841b8a1b9cdc7b37a1777.png)
0
если вы мне — то нет. Я говорю о признаках делимости чисел 2^n-1 — прочитайте внимательно. если n — не простое — то разложение очевидно и такое число не может быть простым. Для простых n там идет проверка по сложению. В общем не суть. Умножьте на бумаге два числа в двоичной системе — поймете о чем я. Например 3 на 5 .
0
Простой контрпример: показатель степени простой — 11, число 2^11-1 = 2047 имеет делители 23 и 89:
![](https://habrastorage.org/r/w1560/files/d91/e91/a4f/d91e91a4f9d049d98113ea703386ce29.png)
![](https://habrastorage.org/files/d91/e91/a4f/d91e91a4f9d049d98113ea703386ce29.png)
0
> если n — не простое — то разложение очевидно
Уважаемый, вы все таки не перечитали о чем я пишу. Если Вам это не нужно — зачем тратить свое время на бессмысленные посты?
Уважаемый, вы все таки не перечитали о чем я пишу. Если Вам это не нужно — зачем тратить свое время на бессмысленные посты?
-1
Ок, перешли на хамоватый язык, я с вами тоже цацкаться не собираюсь.
Гражданин, вы бы свои мысли оформили для начала в каком-то законченном виде. Написали один комментарий некорректный, я вам на это указал, тут же его отредактировали. Написали еще пару туманных комментариев ни о чем.
А если вы не поняли смысла поста и суть простых чисел Мерсенна — перечитайте пост и сопутствующую литературу.
Если считаете, что есть более тривиальный метод поиска простых чисел Мерсенна, опубликуйте — все сообщество математиков и криптологов вам спасибо скажет. Граждан, умеющих доказывать теоремы уровня Ферма на салфетке простым сложением уже достаточно видел.
Гражданин, вы бы свои мысли оформили для начала в каком-то законченном виде. Написали один комментарий некорректный, я вам на это указал, тут же его отредактировали. Написали еще пару туманных комментариев ни о чем.
А если вы не поняли смысла поста и суть простых чисел Мерсенна — перечитайте пост и сопутствующую литературу.
Если считаете, что есть более тривиальный метод поиска простых чисел Мерсенна, опубликуйте — все сообщество математиков и криптологов вам спасибо скажет. Граждан, умеющих доказывать теоремы уровня Ферма на салфетке простым сложением уже достаточно видел.
0
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Простые числа Мерсенна и тест Люка-Лемера