Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
|
Еще и еще, 1001 раз: Как разложить общий модуль, зная два ключа RSA ?!! 07.02.03 18:38 Число просмотров: 3219
Автор: Cyclamen Persicum Статус: Незарегистрированный пользователь
|
Уж простите меня,
но чегото у меня не получается такая элементарная весч.
Квадратное уравнение я решать умею,
но добраться до него никак не могу =)))
|
|
<theory>
|
Вопрос математикам 31.01.03 10:19
Автор: NickP Статус: Незарегистрированный пользователь
|
Существует ли алгоритм вычисления больших факториалов по модулю?
Т.е. нужно найти x = a! mod b, где a и b - большие числа.
|
|
Вопрос математикам,а то у меня отдельно пока не постится-( 04.03.03 14:06
Автор: Anastassia Sinkevitch Статус: Незарегистрированный пользователь
|
Я читала:
В уравнении х^2+y^2=z^2 с точностью до перестановки чисел х и у, все решения могут быть получены по формулам
x=±t(u2-v2)
y=±2tuv
z=±t(u2+v2),
где t,u,v - произвольные целые числа. Подробности см. в замечательной книге
А.О. Гельфонд, Решение уравнений в целых числах.
________________________________________________________________________________
Мне стало интересно как можно для числа 7393764^2 определить его пару в уравнении х^2+y^2=z^2 по этим формулам (те что описаны выше).
если к этому числу родные числа (я определяла по другой формуле):
1. 7393764^2 + 7250573^2=1035565^2
2. 7393764^2 + 13712773^2=15579085^2
3. 7393764^2 + 58350427^2=58817005^2
4. 7393764^2 + 43131977^2=431383045^2
5. 7393764^2 + 1847874773^2=1847889565^2
6. 7393764^2 + 6458852573^2=6458856805^2
7. 7393764^2 + 379637125573^2=379637125645^2
8. 7393764^2 + 13666936521923^2=13666936521925^2
9. 7393764^2 + 3416734130477^2=3416734130485^2
|
|
Help! Быстрое умножение по модулю... 13.02.03 19:54
Автор: Persicum Статус: Незарегистрированный пользователь
|
Памажите люди добрые!
Те из вас, кто имеет теоретическую подготовку
и большой опыт работы с большими числами...
Я написал две прекрасные проги (persicum.front.ru)
но они страдают от тормознутости,
из-за того, что я не умею быстро
вычислять x*y mod z ( и x^2 mod z).
где x,y = большие целые, которые лежат в массиве
по кусочкам на 32-bit.
То есть, я их умножаю в столбик и делю в столбик.
Это просто, но требует N^2 операций.
И вдруг меня осенило - умножать
можно, скажем, через FFT, за N log N операций!
Если дополнить x и y слева нулями,
то свертка даст как раз произведение.
В общем - кто просекает проблему -
киньте ссылочек про быстрый алгоритм
(готовые библиотеки лучше не предлагать,
но тоже можно)
|
| |
Нашел таки... 14.02.03 11:56
Автор: Persicum Статус: Незарегистрированный пользователь
|
http://algolist.manual.ru/maths/
Там и теория быстрого умножения, и сырцы.
|
|
Некоторые частные решения 08.02.03 12:07
Автор: Komlin Статус: Незарегистрированный пользователь
Отредактировано 08.02.03 12:14 Количество правок: 2
|
Я не математик, но когда-то решал подобную задачу...:
x! mod n
1)при x>=n == 0
2) при x>=p & x>=q (n=pq) == 0
Поэтому испоьзовать его для разрешения RSA несколько проблематично
----------------
Да чуть не забыл: для простых n c учётом существавания и единственности пар
a * a' ==1 (mod n) a/=a' при a< n-1
(n-1) ! mod n= n-1
(n-2) ! mod n == 1
(n-3)! mod n == (n-3)' где (n-3)' (n-3) == 1 (mod n).
(n-a) mod n == (n-3)' * (n-4)' * ,,, (n-a)'!!
Удачи!
Сорри если где ошибся - писал наскоро.
P.S. Если чем ещё могу помочь - пишите на мыло (komlin & s-mail.com).
|
|
Еще и еще, 1001 раз: Как разложить общий модуль, зная два ключа RSA ?!! 07.02.03 18:38
Автор: Cyclamen Persicum Статус: Незарегистрированный пользователь
|
Уж простите меня,
но чегото у меня не получается такая элементарная весч.
Квадратное уравнение я решать умею,
но добраться до него никак не могу =)))
|
| |
Алгоритм 08.02.03 02:55
Автор: RElf <M> Статус: Member
Отредактировано 08.02.03 08:46 Количество правок: 1
|
> Уж простите меня,
> но чегото у меня не получается такая элементарная весч.
> Квадратное уравнение я решать умею,
> но добраться до него никак не могу =)))
Как я понял, тебе известны ключи (n,e) и (n,d), и нужно найти разложение n=p*q.
Квадратное уравнение возникает только в случае, когда известна величина phi(n)=(p-1)(q-1).
Известные ключи RSA дают только кратное phi(n) число m=e*d-1. Поэтому приходится использовать нечто более изощренное. Например, следующий вероятностный алгоритм:
сначала из m "извлекается" максмальная степень 2-ки, т.е. оно представляется в виде m = 2^k * t, где t - нечетное число. Далее делаем такой цикл:
{
начало цикла:
берем случайное число a из интервала [1,n]
вычисляем b = a^t mod n
если b==1 mod n, то goto начало цикла
вложенный цикл: { пока b^2 mod n не равно 1, полагаем b = b^2 mod n }
находим r = НОД(b-1,n)
если r не равно 1, то это нетривиальный делитель n. конец.
goto начало цикла
}
|
|
http://www.bugtraq.ru/cgi-bin/forum.mcgi?type=sb&b=15&m=64152 31.01.03 11:07
Автор: Korsh <Мельников Михаил> Статус: Elderman
|
> Существует ли алгоритм вычисления больших факториалов по
> модулю?
> Т.е. нужно найти x = a! mod b, где a и b - большие числа.
RSA завалить хочешь
читай ссылку на пост
http://www.bugtraq.ru/cgi-bin/forum.mcgi?type=sb&b=15&m=64152
|
| |
http://www.bugtraq.ru/cgi-bin/forum.mcgi?type=sb&b=15&m=64152 31.01.03 11:53
Автор: NickP Статус: Незарегистрированный пользователь
|
> > Существует ли алгоритм вычисления больших факториалов
> по
> > модулю?
> > Т.е. нужно найти x = a! mod b, где a и b - большие
> числа.
> RSA завалить хочешь
Как ты догадался? ;)
А предыдущее обсуждение я читал, но ничего интересного там не нашел.
|
| | |
Еслиэто уметь, то можно... 04.02.03 14:12
Автор: Persicum Статус: Незарегистрированный пользователь
|
находить простые не вероятностно, а на верняка
поскольку
(N-1)! = -1 mod N, тогда и тока тогда,
когда N - простое (Ферма отдыхает!!!)
|
| | | |
Еслиэто уметь, то можно... 25.03.03 04:03
Автор: andrew Статус: Незарегистрированный пользователь
|
> находить простые не вероятностно, а на верняка
> поскольку
> (N-1)! = -1 mod N, тогда и тока тогда,
> когда N - простое (Ферма отдыхает!!!)
причем давно и успешно, ничего не опасаясь, продолжает курить. при N=>1K задача ВЫЧИСЛИТЕЛЬНО неразрешима. пока.
теоретически - вроде так...
но! язык теории сух, мой друг и если сложность растет экспоненциально с размерностью, то задача NP-полная и к ферма присоединяются (в курении) все остальные, пока не найдется ферма'
8-)
|
| | | |
Еслиэто уметь, то можно... 25.03.03 03:56
Автор: andrew Статус: Незарегистрированный пользователь
|
|
|
| | | |
Еслиэто уметь, то можно... 04.03.03 14:14
Автор: Anastassia Sinkevitch Статус: Незарегистрированный пользователь
|
> находить простые не вероятностно, а на верняка
Есть решение и наверняка. Самое трудное в этом сделать так чтобы "наверняка" не украли и денег за него заплатили.
Наша компания оказывает консалтинговые услуги....в том числе и в этой области.Сейчас решаем вопрос как "наверняка" закрепить законодательно за человеком который сделал мат.модель определения простых чисел влюбом интервале числового ряда. И это не метод банального перебора.
Весь вопрос сейчас завязан на юридических вещах. Как только развяжем этот Гордиев узел, то милости просим.
А если Вы можете помочь развязать его - то вполне можно обговорить и Ваш гонорар.
|
| | | |
мечты, мечты... 05.02.03 07:48
Автор: RElf <M> Статус: Member
Отредактировано 05.02.03 07:49 Количество правок: 1
|
> находить простые не вероятностно, а на верняка
> поскольку
> (N-1)! = -1 mod N, тогда и тока тогда,
> когда N - простое
Это теорема Вильсона. На практике неприменима из-за экспоненциальной сложности вычислений. Вычислять (N-1)! пусть даже по модулю N, для чисел N, например, порядка 2^1024 не представляется возможным.
> (Ферма отдыхает!!!)
Ферма работает. Это Вильсон отдыхает ;-)
|
| | | | |
Сводим n! к арифметической прогрессии... 05.02.03 14:42
Автор: Persicum Статус: Незарегистрированный пользователь
|
> Вычислять (N-1)!
>пусть даже по модулю N, для чисел N, например, порядка
>2^1024 не представляется возможным.
Можно попытаться свести факториал к арифм. прогресии.
Типа
(N-1)! = a ^ [N(N-1)/2) mod N вот примерное док-во теоремы Вильсона.
Короче, кто врубится в алгоритм быстрого факториала -
немедля мыльте сюда!
|
| | | | | |
Сводим n! к арифметической прогрессии... 25.03.03 04:08
Автор: andrew Статус: Незарегистрированный пользователь
|
> > Вычислять (N-1)!
> >пусть даже по модулю N, для чисел N, например, порядка
> >2^1024 не представляется возможным.
>
> Можно попытаться свести факториал к арифм. прогресии.
> Типа
> (N-1)! = a ^ [N(N-1)/2) mod N вот примерное док-во теоремы
> Вильсона.
>
> Короче, кто врубится в алгоритм быстрого факториала -
> немедля мыльте сюда!
можно мне? спасибо!
я врублюсь.
малая китайская теорема об остатках даст существенное приращение, но потребует проверки на каждом шаге и общая эффективность увеличивается не в разы.
да и в разы супротив экспоненты - мизер.
есть забавное индийское решение, но пока его таят от широких масс...
|
|
|
подробно о проекте
Анализ криптографических сетевых...
