Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
| | | | | | | | | |
Только вот факториал надо вычислять по модулю N 29.12.04 12:58 Число просмотров: 5829
Автор: amirul <Serge> Статус: The Elderman
Отредактировано 29.12.04 13:17 Количество правок: 1
|
По китайской теореме об остатках, единственный набор остатков (модулей), которые вместе будут иметь период N будет набор простых делителей числа N. То есть для того, чтобы УПРОСТИТЬ факторизацию нужно сначала факторизовать число.
А алгоритмы перевода в систему остаточных классов (так называется система счисления, где числа представляются остатками от деления на заданные простые основания) и обратно в позиционную есть. Точно так же можно сделать алгоритм вычисления факториала по модулю Rho, который является произведением этих простых оснований (желательно небольших). Но вот чтобы перевести факториал по модулю Rho в факториал по модулю N (в самом трудном случае если N взаимо простое с Rho) нужно знать факториал по модулю Rho*N. Круг замкнулся.
|
|
<theory>
|
Быстрый алгоритм факторизации, возможна ли реализация? 20.12.04 12:00
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
Отредактировано 20.12.04 12:03 Количество правок: 1
|
Дано число N.
Пусть S будет квадратным корнем из N.
Тогда, если N является произведением двух простых, наименьшее находится вычислением НОД( N, S! ), поскольку второй множитель будет больше S и в факториал не попадет.
Если более двух простых, то надо проверить на простоту и повторить вычисления для частного и результата НОД.
Понятно, что проблема только в том, как быстро вычислить факториал. Может есть подобный алгоритм как и для возведения в степень по модулю?
Мало того, факториал от большого числа очень большой получится. Может есть методы вычисления факториала, точнее не факториала, а произведения только простых, меньших заданного? А так же факториала по модулю.
|
|
Новая мысл/ветка, нефакториальная. 13.04.05 10:47
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
Отредактировано 13.04.05 10:49 Количество правок: 1
|
Где-то видел про хитрую факторизацию, вроде как, методом N-1. Идея была в том, что N-1 легко раскладыывается на простые сомножители. Помнится приблизительно такая фраза от туда "... хотя бы потому, что оно четное, получаем сразу двойку, само число сразу резко уменьшается, поскольку при разложении 'снизу' 2, 3, 5, 7, ... велика вероятность присутствия в N-1 этих сомножителей...". Потом как-то по этим сомножителям искались сомножители самого числа N. Как - не помню. Ссылку что-то никак не найду. На том сайте был еще пример на скрипте - можно было забить любое большое число или сгенерить его там же. Потом почти мгновенно выдавались сомножители. На последний, особенно если он большой, писалось, что возможно простое.
Кто-нибудь про это читал, и где? Как народ относится к этому методу (если я чего не напутал)?
|
| |
Идея (p-1)-метода в том, что если N=p*q и все делители числа... 14.04.05 12:18
Автор: RElf <M> Статус: Member
Отредактировано 14.04.05 12:21 Количество правок: 1
|
> Где-то видел про хитрую факторизацию, вроде как, методом
> N-1. Идея была в том, что N-1 легко раскладыывается на
> простые сомножители.
Идея (p-1)-метода в том, что если N=p*q и все делители числа p-1 маленькие, то p-1 само является делителем m! для небольшого m. Поэтому число 2^(m!)-1 обязано делится на p. Откуда p можно найти как НОД(2^(m!)-1 mod N, N).
Сначала вычисляют число 2^(m!) mod N. Это делается примерно так:
a=2;
for i=1 to m do
a = a^i mod N;
end do;
m выбирается из расчета чем больше - тем лучше, но так чтобы вычисления занимали разумное время.
Потом просто вычисляют НОД(a-1,N). Если он равен:
* 1 - значит, m взято слишком маленьким;
* p - вуаля, найдет нетривиальный делитель N;
* N - значит, m взято слишком большим (но это не так страшно - надо уменьшить m и повторить).
|
| | |
Интересно, а почему именно 2 в стемени m!, а не 3 или что-нибудь еще? 14.04.05 19:35
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
Отредактировано 14.04.05 19:46 Количество правок: 1
|
> Идея (p-1)-метода в том, что если N=p*q и все делители
> числа p-1 маленькие, то p-1 само является делителем m! для
> небольшого m. Поэтому число 2^(m!)-1 обязано делится на p.
> Откуда p можно найти как НОД(2^(m!)-1 mod N, N).
Интересно, а почему именно 2 в стемени m!, а не 3 или что-нибудь еще?
> Сначала вычисляют число 2^(m!) mod N. Это делается примерно
> так:
> a=2;
> for i=1 to m do
> a = a^i mod N;
> end do;
> m выбирается из расчета чем больше - тем лучше, но так
> чтобы вычисления занимали разумное время.
А на каждом шаге цикла почему бы НОД не вычислить и остановиться, как только НОД не будет равен 1?
> Потом просто вычисляют НОД(a-1,N). Если он равен:
> * 1 - значит, m взято слишком маленьким;
> * p - вуаля, найдет нетривиальный делитель N;
> * N - значит, m взято слишком большим (но это не так
> страшно - надо уменьшить m и повторить).
Нужели можно взять такое m, что НОД будет равен N. И что будет, если сомножители p-1 и q-1 примерно равны?
И, собственно, не так уж и часто встречается ситуация, когда наибольший делитель p-1 будет достаточно мал (чтобы p-1 был делителем m!), чтобы за разумное время прокрутить вышеуказанный цикл :(.
А поиск перебором для небольших значений можно ли ускорить, если из перебора исключить заведомо составные числа? Понятно, что каждый раз проверять число на простоту - только огромная потеря времени, но с другой стороны циклично вычислять простые числа практически не реально - медленно. Поэтому можно ли исключить из перебора в цикле числа, заведомо кратные 2, 3, 5, 7 и т. д. до разумных значений? Ведь совсем несложно выкинуть четные, даже кратные 2 или 3. Причем "масочка", которая маскирует из натурального ряда числа, заведомо кратные небольшому количеству маленьких простых будет периодическая и ее можно применять циклично.
|
| | | |
Можно и 3, можно и любое другое число. Но это ничем особо от... 15.04.05 06:36
Автор: RElf <M> Статус: Member
Отредактировано 15.04.05 06:37 Количество правок: 1
|
> Интересно, а почему именно 2 в стемени m!, а не 3 или что-нибудь еще?
Можно и 3, можно и любое другое число. Но это ничем особо от 2 отличатся не будет.
> > Сначала вычисляют число 2^(m!) mod N. Это делается
> примерно
> > так:
> > a=2;
> > for i=1 to m do
> > a = a^i mod N;
> > end do;
> > m выбирается из расчета чем больше - тем лучше, но так
> > чтобы вычисления занимали разумное время.
>
> А на каждом шаге цикла почему бы НОД не вычислить и
> остановиться, как только НОД не будет равен 1?
Вычисление НОД - дорогая операция. Лучше ее вычислять только один раз в конце, во избежание нежелательных тормозов.
> > Потом просто вычисляют НОД(a-1,N). Если он равен:
> > * 1 - значит, m взято слишком маленьким;
> > * p - вуаля, найдет нетривиальный делитель N;
> > * N - значит, m взято слишком большим (но это не так
> > страшно - надо уменьшить m и повторить).
>
> Нужели можно взять такое m, что НОД будет равен N.
Ну, например, m=N гарантированно даст в качестве результата N. Другое дело, что для больших N, прогон такого цикла будет практически неосуществим.
> И что будет, если сомножители p-1 и q-1 примерно равны?
Нужно выбрать такое m, чтобы p-1 (но не q-1, или же наоборот) было делителем m!.
> И, собственно, не так уж и часто встречается ситуация,
> когда наибольший делитель p-1 будет достаточно мал (чтобы
> p-1 был делителем m!), чтобы за разумное время прокрутить
> вышеуказанный цикл :(.
Теперь еще не чаще. ;)
Имея в виду этот метод, при генерации от p-1 и q-1 часто требуют наличия больших простых делителей.
> А поиск перебором для небольших значений можно ли ускорить,
> если из перебора исключить заведомо составные числа?
Можно ускорить (но не особо), есть соответствующие модификации. Но основная идея та же.
|
|
А) Идея хоршоая, но не нова. см. cryptography.ru 22.03.05 10:31
Автор: Searcher Статус: Незарегистрированный пользователь
|
> Дано число N.
> Пусть S будет квадратным корнем из N.
> Тогда, если N является произведением двух простых,
> наименьшее находится вычислением НОД( N, S! ), поскольку
> второй множитель будет больше S и в факториал не попадет.
> Понятно, что проблема только в том, как быстро вычислить
> факториал. Может есть подобный алгоритм как и для
> возведения в степень по модулю?
А) Идея хоршоая, но не нова. см. cryptography.ru
Б) Есть формула ПРИБЛИЖЕННОГО вычисления факториала. называется формула Стерлинга (стрилинга). См. Д. Кнут "Исскуство программирования". Формула в одну строчку, без рядов и рекурсий.
Есть одна проблема - приближенное. Боюсь приближенность (читай неточность) вычисленного факториала будет намного выше, чем само число N.
Если интересно пиши.
|
| |
Пишу, вот. Придумать формулу для приближенного вычисления... 22.03.05 12:22
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
|
> А) Идея хоршоая, но не нова. см. cryptography.ru
> Б) Есть формула ПРИБЛИЖЕННОГО вычисления факториала.
> называется формула Стерлинга (стрилинга). См. Д. Кнут
> "Исскуство программирования". Формула в одну строчку, без
> рядов и рекурсий.
> Есть одна проблема - приближенное. Боюсь приближенность
> (читай неточность) вычисленного факториала будет намного
> выше, чем само число N.
> Если интересно пиши.
Пишу, вот. Придумать формулу для приближенного вычисления факториала не проблема. Причем чем проще формула, тем меньше точность.
Мало того, она не будет применима для вычисления факториала килобитного числа - размерность результата астрономическая.
Так что Стерлинг здесь не применим.
Поиск по сайту ничего приличного не дал. Облазить все форумы, ЧАВО, научные статьи, обзоры, заметки, рефераты времени не хватит.
Поиск по поисковикам на тему быстрого вычисления факториала по модулю ничего не дал.
Вспомнил я про вычисления суммы арифметической прогрессии. Там используется свертка пополам для получения ряда одинаковых значений. Сумма вычисляется легко значение умножается на длину свернутого ряда.
Хотел то же самое для факториала придумать. Связь просматривается: там сумма, здесь произведение; там произведение, здесь возведение в степень; по модулю перемножать и возводить в степень не проблема.
Попробовал - свернул кусок натурального ряда по принципу первый умножаем на последний, второй на предпоследний. Хотел как у арифметической прогрессии получить что-то постоянное, тогда просто бы в степень возвел и все. Увы - только вторая или третья "производная" обнулилась. Свернул еще пополам уже свернутый ряд - следующая "производная" обнулилась.
Под "производной" я имею в виду приращение значения. Приращение аргумента здесь равно единицы. О пределах пока речи не ведем.
Одно пока понял: десяток раз свернем - сам ряд в тысячу раз сократится, два десятка - в милион. Для вычисления факториала достаточно получить первых N значений и вычислить N-1 приращений, N-2 приращений приращений, ... и так до нулевых приращений. Тогда для получения очередного значения сначала вычисляет N-1 производную прибавляя к ее предыдущему значению Nую производную, потом новую N-2, прибавив к ее старому значению новую N-1, ... и так N раз до получения нового значения свернутого ряда. Итого N сложений. Разумеется полученный член ряда умножаем на произведение всех предыдущих, а храним только остаток от деления.
Короче мне думается, что быстрое вычисление факториала по модулю реально и находится где-то в этом направлении.
|
| | |
А можешь придумать сложную, но точность выше? (отступление... 24.03.05 16:45
Автор: Searcher Статус: Незарегистрированный пользователь
Отредактировано 24.03.05 20:50 Количество правок: 1
|
> Пишу, вот. Придумать формулу для приближенного вычисления
> факториала не проблема. Причем чем проще формула, тем
> меньше точность.
А можешь придумать сложную, но точность выше? (отступление от темы)
> Вспомнил я про вычисления суммы арифметической прогрессии.
> Там используется свертка пополам для получения ряда
> одинаковых значений. Сумма вычисляется легко значение
> умножается на длину свернутого ряда.
Здесь невозможно получить одинаковые значения. 8(
> Для вычисления
> факториала достаточно получить первых N значений и
> вычислить N-1 приращений, N-2 приращений приращений, ... и
> так до нулевых приращений. Тогда для получения очередного
> значения сначала вычисляет N-1 производную прибавляя к ее
> предыдущему значению Nую производную, потом новую N-2,
> прибавив к ее старому значению новую N-1, ... и так N раз
> до получения нового значения свернутого ряда. Итого N
> сложений. Разумеется полученный член ряда умножаем на
> произведение всех предыдущих, а храним только остаток от
> деления.
Даже, если это будут только сложения, у тебя их слишком много получется.
> Короче мне думается, что быстрое вычисление факториала по
> модулю реально и находится где-то в этом направлении.
Это я понял. :) Осталось всего ничего.
Я попробовал начать сворачивать от середины. Если я правильно посчитал, то произведение четырех членов ряда можно получить за 2 умножения и 2 сложения.
Пусть нужно вычислить (x-a(x-(a-1))... (x-1x*(x+1)...(x+(a-1))x+a)
(x-a)*(x+a)=x*x-a*a,
аналогично
(x-(a-1)(x+(a-1))=x*x-(a-1)a-1),
получается "половинный" ряд
x*(x*x-1*1)*...(x*x-a*a) т.е "a" членов, вместо "2*а+1"
пусть b- число, ~ a/2, t - число от 1 до a/2
берем пару (x*x-(b-t(b-t))*(x*x-(b+t)b+t)) = (далее значком ^ обозначаем возведение в степень)
=x^4-x^2*((b-t)^2)-x^2*((b+t)^2)+((b+t)^2)*((b-t)^2)=
=x^4-x^2(b^2-2*b*t+t^2+b^2+2*b*t+t^2)+(b^2-t^2)^2=
=x^4-x^2(2*b^2+2*t^2)+b^4-2*b^2*t^2+t^4=
=x^4-x^2*2*b^2+b^4-x^2*2*t^2-2*b^2*t^2+t^4=
=x^4-x^2*2*b^2+b^4 + t^2*(t^2-2*x^2-2*b^2)=
const1 + t^2* (t^2 - const2)
итого две предварительных константы и
1 умножение t^2,
2 умножение t^2*(...)
и два сложения.
Вместо исходных трех (x-(b+t)(x+(b+t))*(x-(b-t))x+(b-t))
Ежели, конечно, я нигде не ошибся.
|
| | | |
Было бы возможно, факториал любого числа равнялся бы... 24.03.05 19:57
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
Отредактировано 24.03.05 20:01 Количество правок: 1
|
> Здесь невозможно получить одинаковые значения. 8(
Было бы возможно, факториал любого числа равнялся бы возведению целого числа в целую степень 8(.
> Это я понял. :) Осталось всего ничего.
Кто знает...
> Я попробовал начать сворачивать от середины. Если я
> правильно посчитал, то произведение четырех членов ряда
> можно получить за 2 умножения и 2 сложения.
> Пусть нужно вычислить (x-a(x-(a-1))...
> (x-1x*(x+1)...(x+(a-1))x+a)
> (x-a)*(x+a)=x*x-a*a,
> аналогично
> (x-(a-1)(x+(a-1))=x*x-(a-1)a-1),
>
> получается "половинный" ряд
> x*(x*x-1*1)*...(x*x-a*a) т.е "a" членов, вместо "2*а+1"
> пусть b- число, ~ a/2, t - число от 1 до a/2
> берем пару (x*x-(b-t(b-t))*(x*x-(b+t)b+t)) = (далее
> значком ^ обозначаем возведение в степень)
> =x^4-x^2*((b-t)^2)-x^2*((b+t)^2)+((b+t)^2)*((b-t)^2)=
> =x^4-x^2(b^2-2*b*t+t^2+b^2+2*b*t+t^2)+(b^2-t^2)^2=
> =x^4-x^2(2*b^2+2*t^2)+b^4-2*b^2*t^2+t^4=
> =x^4-x^2*2*b^2+b^4-x^2*2*t^2-2*b^2*t^2+t^4=
> =x^4-x^2*2*b^2+b^4 + t^2*(t^2-2*x^2-2*b^2)=
> const1 + t^2* (t^2 - const2)
> итого две предварительных константы и
> 1 умножение t^2,
> 2 умножение t^2*(...)
> и два сложения.
> Вместо исходных трех
> (x-(b+t)(x+(b+t))*(x-(b-t))x-(b-t))
> Ежели, конечно, я нигде не ошибся.
Суть то не в том, что можно чуть быстрее сворачивать. Все равно весь ряд сворачивать не надо. Для десятикратного сворачивания достаточно получить десяток значений. Пусть для этого потребуется даже десять тысяч перемножений и пять тысяч вычитаний для вычисления приращений. Главное потом для вычисления очередного значения свернутого ряда достаточно будет десяток сложений и членов ряда будет меньше в тысячу раз.
Однако этот метод хоть и может быть более быстрым, но не годится для нахождения факториала по модулю для килобитных чисел. Максисум для 64 битных, поскольку для сокращения ряда в миллион раз потребуется хранить в оперативке два-три десятка восьмимегабайтных чисел. Количество перемножений хоть и сократится в милион раз, все равно останется 18 трилионов. Нужно что-то упрощать.
Над приближенным вычислением подумаю, им тоже можно воспользоваться.
|
| | | | |
Извини, не правильно понял. 27.03.05 23:48
Автор: Searcher Статус: Незарегистрированный пользователь
|
> Суть то не в том, что можно чуть быстрее сворачивать. Все
> равно весь ряд сворачивать не надо.
Извини, не правильно понял.
Я думал про арифметическую прогрессию, где основное свойство ряда а
а(x-1)-a(x)=a(x)-a(x+1)=dx.
откуда а(x-1)+a(x+1)=2а(х) и а(x-y)+a(x+y)=2а(х).
поэтому я и рассматривал проивзедение (x+y)(x-y)=x*x-y-y.
Я просто хотел попробовать "свернуть" часть ряда, чтобы быстрее его вычислить. Надеялся, что если свернуть 8 членов можно будет выиграть еще операций. В теории,
если бы удалось для них получить многочлен вида x^8+k1*x^4+k2*x^2+k3. То был бы дополнительный выигрыш. И если бы тенденция сохранилась, то 2^m членов свернулось бы к полиному m-ой степени. :)
Не получается. :( :)
>Для десятикратного
> сворачивания достаточно получить десяток значений. Пусть
> для этого потребуется даже десять тысяч перемножений и пять
> тысяч вычитаний для вычисления приращений. Главное потом
> для вычисления очередного значения свернутого ряда
> достаточно будет десяток сложений и членов ряда будет
> меньше в тысячу раз.
> Однако этот метод хоть и может быть более быстрым, но не
> годится для нахождения факториала по модулю для килобитных
> чисел. Максисум для 64 битных, поскольку для сокращения
> ряда в миллион раз потребуется хранить в оперативке два-три
> десятка восьмимегабайтных чисел. Количество перемножений
> хоть и сократится в милион раз, все равно останется 18
> трилионов. Нужно что-то упрощать.
??? не понял, это про сворачивание, или про то, что я предложил?
> Над приближенным вычислением подумаю, им тоже можно
> воспользоваться.
Один из вариантов - если иметь приближенное значение, то можно пытаться искать тот самый НОД в некотором диапазоне от числа. Главное, чтобы приближение было в разумных пределах, а не районе корня (N).:)
Кстати, ты ничего не слышал о
"Дэниэл Бернстайн (Daniel Bernstein) опубликовал статью, где описал новый метод вычисления факториалов больших чисел"
http://www.pcsamara.ru/news.phtml?n=3&day=13&m=4&y=2002&mode=prev
И о формуле Стирлинга
http://ru.wikipedia.org/wiki/Формула_Стирлинга#.D0.A4.D0.BE.D1.80.D0.BC.D1.83.D0.BB.D0.B0_.D0.A1.D1.82.D0.B8.D1.80.D0.BB.D0.B8.D0.BD.D0.B3.D0.B0
ее "неприменимость" определяется,как мне кажется ,кроме неточности,
вычислением степени т.е. (n/e)^n, однако, если учесть, что нам нужно
значение факториала по модулю, то
можно было бы рассчитать (n/e)^n mod n. Как поделить (n/e)^n на n - ясно - это
(n/e)^(n-log по основанию n/e от n). Неясно, как остаток получить. :)
|
| | | | | |
Бред сивого переводчика 30.03.05 08:34
Автор: RElf <M> Статус: Member
Отредактировано 30.03.05 08:39 Количество правок: 2
|
> Кстати, ты ничего не слышал о
> "Дэниэл Бернстайн (Daniel Bernstein) опубликовал статью,
> где описал новый метод вычисления факториалов больших
> чисел"
> http://www.pcsamara.ru/news.phtml?n=3&day=13&m=4&am
> p;y=2002&mode=prev
Бред сивого переводчика. Вот первоисточник на английском:
http://www.geek.com/news/geeknews/2002mar/gee20020329010951.htm
О факториалах там вообще речь не идет. А слово factor употребляется в единственном смысле "факторизовать".
|
| | | | | | |
Большое спасибо за информацию. 30.03.05 09:53
Автор: Searcher Статус: Незарегистрированный пользователь
|
|
|
| | | | | |
Я уже потом, по дороге домой, понял, что ты неправильно... 28.03.05 11:22
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
|
> Извини, не правильно понял.
Я уже потом, по дороге домой, понял, что ты неправильно понял.
> Я думал про арифметическую прогрессию, где основное
> свойство ряда а
> а(x-1)-a(x)=a(x)-a(x+1)=dx.
> откуда а(x-1)+a(x+1)=2а(х) и а(x-y)+a(x+y)=2а(х).
> поэтому я и рассматривал проивзедение (x+y)(x-y)=x*x-y-y.
> Я просто хотел попробовать "свернуть" часть ряда, чтобы
> быстрее его вычислить. Надеялся, что если свернуть 8 членов
> можно будет выиграть еще операций. В теории,
> если бы удалось для них получить многочлен вида
> x^8+k1*x^4+k2*x^2+k3. То был бы дополнительный выигрыш. И
> если бы тенденция сохранилась, то 2^m членов свернулось бы
> к полиному m-ой степени. :)
> Не получается. :( :)
> ??? не понял, это про сворачивание, или про то, что я
> предложил?
Я там тоже ошибся, в програмке, которая проверяля предположение. При очередном "сворачивании" "обнуляется" каждая вторая "производная".
Короче все равно "не катит".
Была мысль поработать над быстрым вычислением "простого" факториала, то есть произведения вех простых чисел не более заданного. Но похоже там все еще сложнее.
> > Над приближенным вычислением подумаю, им тоже можно
> > воспользоваться.
> Один из вариантов - если иметь приближенное значение, то
> можно пытаться искать тот самый НОД в некотором диапазоне
> от числа. Главное, чтобы приближение было в разумных
> пределах, а не районе корня (N).:)
Это понятно, но проблема будет в самом поиске в этом диапазоне. Вычислять сам факториал бессмыслено, поскольку его разрядность космическая. Остается вопрос как перебрать НОДы от чисел диапазона, зная НОД от приближенного значения.
Ну и опять же вопрос точности - количества переборов.
> Кстати, ты ничего не слышал о
> "Дэниэл Бернстайн (Daniel Bernstein) опубликовал статью,
> где описал новый метод вычисления факториалов больших
> чисел"
> http://www.pcsamara.ru/news.phtml?n=3&day=13&m=4&am
> p;y=2002&mode=prev
>
> И о формуле Стирлинга
> http://ru.wikipedia.org/wiki/Формула_Стирлинга#.D0.A4.D0.BE
> .D1.80.D0.BC.D1.83.D0.BB.D0.B0_.D0.A1.D1.82.D0.B8.D1.80.D0.
> BB.D0.B8.D0.BD.D0.B3.D0.B0
Надо почитать. Но эсли б это было так все просто, то кто-нибудь давно этим воспользовался.
> ее "неприменимость" определяется,как мне кажется ,кроме
> неточности,
> вычислением степени т.е. (n/e)^n, однако, если учесть, что
> нам нужно
> значение факториала по модулю, то
> можно было бы рассчитать (n/e)^n mod n. Как поделить
> (n/e)^n на n - ясно - это
> (n/e)^(n-log по основанию n/e от n). Неясно, как остаток
> получить. :)
Это как раз просто, нужно просто на каждом этапе возведения в степень вычислять остаток:
http://primenumber.narod.ru/
http://www.gamedev.ru/forum/?action=showtopic&group=0&topic=1939
http://ssl.stu.neva.ru/psw/crypto/timing.html
unsigned long st( unsigned long x, unsigned long y, unsigned long n ){
unsigned __int64 s, t, u;
s = 1;
t = x;
u = y;
while( u ){
if( u & 1 )
s = ( s * t ) % n;
u >>= 1;
t = ( t * t ) % n;
}
return( s );
}
long powmod( long a, long k, long n ){
long b = 1;
while( k ){
if( k % 2 == 0 ){
k /= 2;
a *= a; // [ a = (a*a)%n; ]
}
else{
k--;
b *= a; // [ b = (b*a)%n; ]
}
}
return b;
}
---
|
| | | | | | |
Про то, что не стоит "возиться" с простыми, и лучше работать... 28.03.05 22:26
Автор: Searcher Статус: Незарегистрированный пользователь
Отредактировано 28.03.05 22:59 Количество правок: 2
|
> Я там тоже ошибся, в програмке, которая проверяля
> предположение. При очередном "сворачивании" "обнуляется"
> каждая вторая "производная".
> Короче все равно "не катит".
> Была мысль поработать над быстрым вычислением "простого"
> факториала, то есть произведения вех простых чисел не более
> заданного. Но похоже там все еще сложнее.
К тому, что не стоит "возиться" с простыми, и лучше работать просто с целыми, я пришел из простого рассуждения:
количество простых чисел, меньших N, с точностью до порядка, равно N/ln (N).
Что означает, что для чисел порядка 10^70 простым будет "каждое" трехсотое(тысячное, сто тысячное, не очень важно).
В то же время, чтобы найти это простое необходимо (при проверке в лоб) проверить каждое из них на
взаимную простоту со всеми найдеными, а это примерно 10^67 (10^65) . :) За это время можно произвести довольно большое количество операций со всеми этими числами, среди которых одно простое.
> Надо почитать. Но эсли б это было так все просто, то
> кто-нибудь давно этим воспользовался.
Абсолютно с тобой согласен, но может там есть некоторые интересные идеи.
> > (n/e)^(n-log по основанию n/e от n). Неясно, как
> > остаток получить. :)
>
> Это как раз просто, нужно просто на каждом этапе возведения
> в степень вычислять остаток:
??? Может я ошибся (Или мало понял) :). но шел разговор о
(n/e)^(n-log по основанию n/e от n). Где степень (n-log по основанию n/e от n), т.е. порядка n.
Если на каждом этапе вычислять остаток, то количество этапов будет порядка n. А это не реализуемо в "приличное "время.
Кстати, можно еще рассмотреть только произведение чисел от корень(N) до корень(N)/2. (С вероятностью 50% на успех, или выше, если предположить, что исходные множители должны быть одинакового размера.)
P.S. в связи с тем, что я не могу создать сообщение, пишу здесь. :)
Как найти решение сравнения a*x*x+b*x+c=0 mod p, где p простое.
|
| | | | | | | |
Черт его знает, может в этом случае удасться избавиться от е... 29.03.05 10:36
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
|
> К тому, что не стоит "возиться" с простыми, и лучше
> работать просто с целыми, я пришел из простого рассуждения:
> количество простых чисел, меньших N, с точностью до
> порядка, равно N/ln (N).
Черт его знает, может в этом случае удасться избавиться от е и ln().
> Что означает, что для чисел порядка 10^70 простым будет
> "каждое" трехсотое(тысячное, сто тысячное, не очень важно).
> В то же время, чтобы найти это простое необходимо (при
> проверке в лоб) проверить каждое из них на
> взаимную простоту со всеми найдеными, а это примерно 10^67
> (10^65) . :) За это время можно произвести довольно большое
> количество операций со всеми этими числами, среди которых
> одно простое.
Не надо проверок. Во первых простые генеряться решетом Эратосфена без делений и проверок. Во вторых апроксимационная формула может оказаться очень простой и очень точной, как на первый взгляд не покажется.
> > > (n/e)^(n-log по основанию n/e от n). Неясно, как
> > > остаток получить. :)
> >
> > Это как раз просто, нужно просто на каждом этапе
> возведения
> > в степень вычислять остаток:
> ??? Может я ошибся (Или мало понял) :). но шел разговор о
> (n/e)^(n-log по основанию n/e от n). Где степень (n-log по
> основанию n/e от n), т.е. порядка n.
> Если на каждом этапе вычислять остаток, то количество
> этапов будет порядка n. А это не реализуемо в "приличное
> "время.
А не надо ничего ни на что делить. Остаток автоматом получается. Посмотрим на исходную функцию (n/e)^n % n. Вычисляем только (n/e), а дальше элементарнейшим алгоритмом возведения в степень по модулю, который во всех реализациях RSA используется.
> Кстати, можно еще рассмотреть только произведение чисел от
> корень(N) до корень(N)/2. (С вероятностью 50% на успех, или
> выше, если предположить, что исходные множители должны быть
> одинакового размера.)
Хорошо, но если алгоритм 100% взлома на всем интервале будет работать для килобитных чисел несколько минут, то и с половинкой интервала не стОит замарачиваться.
> P.S. в связи с тем, что я не могу создать сообщение, пишу
> здесь. :)
> Как найти решение сравнения a*x*x+b*x+c=0 mod p, где p
> простое.
Сначала полезно придумать критерий для коэффициентов, при котором решений нет. Например все они четные.
А вообще то сомневаюсь, что кроме как перебором можно решить.
|
| | | | | | | | |
Даже по решету эратосфена придется "пройтись" простыми до... 29.03.05 11:50
Автор: Searcher Статус: Незарегистрированный пользователь
Отредактировано 29.03.05 12:03 Количество правок: 1
|
> Не надо проверок. Во первых простые генеряться решетом
> Эратосфена без делений и проверок.
Даже по решету эратосфена придется "пройтись" простыми до корня из N. т.е. если N~10^70,
то пройтись придется простыми до 10^35. (Если я правильно знаю решето)
> Во вторых
> апроксимационная формула может оказаться очень простой и
> очень точной, как на первый взгляд не покажется.
? Осталось ее найти.
> А не надо ничего ни на что делить. Остаток автоматом
> получается. Посмотрим на исходную функцию (n/e)^n % n.
> Вычисляем только (n/e), а дальше элементарнейшим алгоритмом
> возведения в степень по модулю, который во всех реализациях
> RSA используется.
Тогда что остается неприменимого в формуле Стирлинга? Только точность.
Интересно, как получить остальные члены в полиноме для увеличения точности.
И еще, какая понадобится точность для N=10^k, k знаков, или больше чем 10^k? :)
> Хорошо, но если алгоритм 100% взлома на всем интервале
> будет работать для килобитных чисел несколько минут, то и с
> половинкой интервала не стОит замарачиваться.
Это если будет, а если нет? И еще, если рассматривать только половинку (верхнюю) интервала,
то относительное изменение чисел (отношение максимального члена к минимальному) будет максимум в 2 раза, что может снизить неточность, по сравнению
с нижней половиной, где относительное изменение чисел будет 10^35 (Если N 10^70).
> Сначала полезно придумать критерий для коэффициентов, при
> котором решений нет. Например все они четные.
> А вообще то сомневаюсь, что кроме как перебором можно
> решить.
Жаль. Хочется быстрее чем перебором. :)
|
| | | | | | | | | |
А это смотря для каких задач. Если надо одно большое... 29.03.05 16:24
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
|
> Даже по решету эратосфена придется "пройтись" простыми до
> корня из N. т.е. если N~10^70,
> то пройтись придется простыми до 10^35. (Если я правильно
> знаю решето)
А это смотря для каких задач. Если надо одно большое простое, то нужно их поискать в окресности перебором. Если надо много/все на интервале, то решетом. В любом случае это будет быстрее, чем пытаться делить каждое на простые и проверять остаток. Причем разница колосальна.
> Тогда что остается неприменимого в формуле Стирлинга?
> Только точность.
Естественно! 4 знака очень мало, когда речь идет о сотне.
> Интересно, как получить остальные члены в полиноме для
> увеличения точности.
Вариант - эмпирически. Подбираем коэффициенты, оценивая сренеквадратичное отклонение. Другой метод будет более сложен.
> И еще, какая понадобится точность для N=10^k, k знаков, или
> больше чем 10^k? :)
n-k. Хотим +/-10 - надо -(к-1), хотим +/-100 - надо -(к-2).
> Это если будет, а если нет? И еще, если рассматривать
> только половинку (верхнюю) интервала,
> то относительное изменение чисел (отношение максимального
> члена к минимальному) будет максимум в 2 раза, что может
> снизить неточность, по сравнению
> с нижней половиной, где относительное изменение чисел будет
> 10^35 (Если N 10^70).
Экстенсивные методы бессмысленно рассматривать, это все равно что на ассемблере вылизывать код, чтоб добиться десятикратного ускорения. С одной стороны это не плохо. С другой стороны если речь идет о времени вычислений 10^600 лет, то от того что время сократится до 10^599 лет легче не станет.
|
| | | | | | | | | | |
И возвращаясь к "простому" факториалу 29.03.05 20:02
Автор: Searcher Статус: Незарегистрированный пользователь
|
> А это смотря для каких задач. Если надо одно большое
> простое, то нужно их поискать в окресности перебором. Если
> надо много/все на интервале, то решетом. В любом случае это
> будет быстрее, чем пытаться делить каждое на простые и
> проверять остаток. Причем разница колосальна.
И возвращаясь к "простому" факториалу, надо будет найти все простые на интервале, и
для больших чисел по решету надо будет пройтись всеми простыми, которые меньше чем корень из
кандидатов. При этом даже если будет отсеяно 9999999 из 1000000, то по этому последнему необходимо будет пройтись всеми простыми, количество которых существенно больше, чем 1000000 на десятки порядков.
Но тем, не менее, если считаешь, что "простой факториал" даст выигрыш, может так оно и есть.
> > Интересно, как получить остальные члены в полиноме для
> > увеличения точности.
>
> Вариант - эмпирически. Подбираем коэффициенты, оценивая
> сренеквадратичное отклонение. Другой метод будет более
> сложен.
>
> > И еще, какая понадобится точность для N=10^k, k
> знаков, или
> > больше чем 10^k? :)
>
> n-k. Хотим +/-10 - надо -(к-1), хотим +/-100 - надо -(к-2).
То есть, приводя для случая rsa-1024~10^308 нам надо получить
308 знаков и 308 членов полинома? Полиномиальная сложность?
> Экстенсивные методы бессмысленно рассматривать, это все
> равно что на ассемблере вылизывать код, чтоб добиться
> десятикратного ускорения. С одной стороны это не плохо. С
> другой стороны если речь идет о времени вычислений 10^600
> лет, то от того что время сократится до 10^599 лет легче не
> станет.
Да, ты прав. Просто это было ограничение, которое могло бы упростить вычисления.
Да, вылизывать код на АСМе, чтобы выиграть один порядок из 100 - пустая трата времени.
Тем не менее, если рассматривать два ряда
1*2*3*....*100 и
101*102*103*...*200, то 1*100 отличается от 50*51 в 25 раз, в то время как
101*200 отличается от 150*151 в 1.1, что означает, что значение первого ряда от 50^50 будет отличаться
на пару десятков порядков, в то время как значение второго от 150^50 всего на 2.
|
| | | | | | | | | | | |
Это я к тому, что может быть простая формула для вычисления... 30.03.05 00:10
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
|
> И возвращаясь к "простому" факториалу, надо будет найти все
> простые на интервале, и
> для больших чисел по решету надо будет пройтись всеми
> простыми, которые меньше чем корень из
> кандидатов. При этом даже если будет отсеяно 9999999 из
> 1000000, то по этому последнему необходимо будет пройтись
> всеми простыми, количество которых существенно больше, чем
> 1000000 на десятки порядков.
> Но тем, не менее, если считаешь, что "простой факториал"
> даст выигрыш, может так оно и есть.
Это я к тому, что может быть простая формула для вычисления простого факториала, которую пока не нашли и для обычного. НАПРИМЕР, взяли простое число, возвели его в степень, где показатель - его "порядковый номер", потом его "порядковый номер" возвели в степень того что получилось в первый раз. Или что-нибудь в этом духе. И не надо ничего вычислять и генерить сами числа, перемножать их.
> > > И еще, какая понадобится точность для N=10^k, k
> > знаков, или
> > > больше чем 10^k? :)
> >
> > n-k. Хотим +/-10 - надо -(к-1), хотим +/-100 - надо
> -(к-2).
> То есть, приводя для случая rsa-1024~10^308 нам надо
> получить
> 308 знаков и 308 членов полинома? Полиномиальная сложность?
Это я к формуле Стерлинга. Там погрешность -4, или 0.0001, насколько я помню. Если мы не хотим перебирать более 10 чисел в окресности приближенного факториала, то нам нужно, чтоб к-1 десятичных знаков были точными из к знаков всего.
> Да, ты прав. Просто это было ограничение, которое могло бы
> упростить вычисления.
> Да, вылизывать код на АСМе, чтобы выиграть один порядок из
> 100 - пустая трата времени.
> Тем не менее, если рассматривать два ряда
> 1*2*3*....*100 и
> 101*102*103*...*200, то 1*100 отличается от 50*51 в 25 раз,
> в то время как
> 101*200 отличается от 150*151 в 1.1, что означает, что
> значение первого ряда от 50^50 будет отличаться
> на пару десятков порядков, в то время как значение второго
> от 150^50 всего на 2.
А к чему это?
|
| | | | | | | | | | | | |
Может быть. Осталось ее найти. 30.03.05 09:47
Автор: Searcher Статус: Незарегистрированный пользователь
|
> Это я к тому, что может быть простая формула для вычисления
> простого факториала, которую пока не нашли и для обычного.
> НАПРИМЕР, взяли простое число, возвели его в степень, где
> показатель - его "порядковый номер", потом его "порядковый
> номер" возвели в степень того что получилось в первый раз.
> Или что-нибудь в этом духе. И не надо ничего вычислять и
> генерить сами числа, перемножать их.
Может быть. Осталось ее найти.
>
>
> Это я к формуле Стерлинга. Там погрешность -4, или 0.0001,
> насколько я помню. Если мы не хотим перебирать более 10
> чисел в окресности приближенного факториала, то нам нужно,
> чтоб к-1 десятичных знаков были точными из к знаков всего.
Я понял. В этой формуле первые два члена "отвечают" за быстрое вычисление,
а последний, то что я неправильно назвал полиномом, (1+12/n+1/(288n^2)...),
"отвечает" за точность. Так если 4 члена обеспечивают точность в -4, то 308 членов могут обеспечить точность 308 знаков? Тогда для искомого вычисления факториала неизвестными остаются только эти члены.
> > Тем не менее, если рассматривать два ряда
> > 1*2*3*....*100 и
> > 101*102*103*...*200 ....
>
> А к чему это?
К тому, что если вычислять факториал, то это эквивалент ряда 1*2*3*...*100. И его приближенное значение
как 50^50 будет очень не точным (разница в пару десятков порядков).
А если вычислять "частичный факториал" т.е. произведение, начинаемое не с 1, а с 101, и для "корректности сравнения", тоже из 100 членов, 101*102*...*200, то его приближенное значение в 150^50 будет существенно точнее.
Возвращаясь к исх. задаче и приближенной формуле: Есть число N, надо найти k!, где k~корень(N), с учетом того, что один из множителей принадлежит диапазону от 1 до k. Так вот если значение k! приближенно расчитывать, как
(k/2)^(k/2), то оно от реального будет отличаться на пару порядков.
А если считать произведение от (k/4) до (k/2), то его значение приближенное значение как (k*3/4)^(k/4) будет существенно точнее. И цена за такое существенное увеличение будет "всего" вдвое уменьшение шансов.
|
|
|
подробно о проекте
Анализ криптографических сетевых...
