Еще и еще, 1001 раз: Как разложить общий модуль, зная два ключа RSA ?!!07.02.03 18:38 Число просмотров: 3420 Автор: Cyclamen Persicum Статус: Незарегистрированный пользователь
В уравнении х^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 по этим формулам (те что описаны выше).
если к этому числу родные числа (я определяла по другой формуле):
Памажите люди добрые!
Те из вас, кто имеет теоретическую подготовку
и большой опыт работы с большими числами...
Я написал две прекрасные проги (persicum.front.ru)
но они страдают от тормознутости,
из-за того, что я не умею быстро
вычислять x*y mod z ( и x^2 mod z).
где x,y = большие целые, которые лежат в массиве
по кусочкам на 32-bit.
То есть, я их умножаю в столбик и делю в столбик.
Это просто, но требует N^2 операций.
И вдруг меня осенило - умножать
можно, скажем, через FFT, за N log N операций!
Если дополнить x и y слева нулями,
то свертка даст как раз произведение.
В общем - кто просекает проблему -
киньте ссылочек про быстрый алгоритм
(готовые библиотеки лучше не предлагать,
но тоже можно)
Я не математик, но когда-то решал подобную задачу...:
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 Статус: Незарегистрированный пользователь
> Уж простите меня, > но чегото у меня не получается такая элементарная весч. > Квадратное уравнение я решать умею, > но добраться до него никак не могу =)))
Как я понял, тебе известны ключи (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 начало цикла
}
> Существует ли алгоритм вычисления больших факториалов по > модулю? > Т.е. нужно найти x = a! mod b, где a и b - большие числа. RSA завалить хочешь
читай ссылку на пост
> > Существует ли алгоритм вычисления больших факториалов > по > > модулю? > > Т.е. нужно найти x = a! mod b, где a и b - большие > числа. > RSA завалить хочешь
Как ты догадался? ;)
А предыдущее обсуждение я читал, но ничего интересного там не нашел.
Еслиэто уметь, то можно...04.02.03 14:12 Автор: Persicum Статус: Незарегистрированный пользователь
> находить простые не вероятностно, а на верняка > поскольку > (N-1)! = -1 mod N, тогда и тока тогда, > когда N - простое (Ферма отдыхает!!!) причем давно и успешно, ничего не опасаясь, продолжает курить. при N=>1K задача ВЫЧИСЛИТЕЛЬНО неразрешима. пока.
теоретически - вроде так...
но! язык теории сух, мой друг и если сложность растет экспоненциально с размерностью, то задача NP-полная и к ферма присоединяются (в курении) все остальные, пока не найдется ферма'
8-)
Еслиэто уметь, то можно...25.03.03 03:56 Автор: andrew Статус: Незарегистрированный пользователь
Есть решение и наверняка. Самое трудное в этом сделать так чтобы "наверняка" не украли и денег за него заплатили.
Наша компания оказывает консалтинговые услуги....в том числе и в этой области.Сейчас решаем вопрос как "наверняка" закрепить законодательно за человеком который сделал мат.модель определения простых чисел влюбом интервале числового ряда. И это не метод банального перебора.
Весь вопрос сейчас завязан на юридических вещах. Как только развяжем этот Гордиев узел, то милости просим.
А если Вы можете помочь развязать его - то вполне можно обговорить и Ваш гонорар.
мечты, мечты...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-1)! > >пусть даже по модулю N, для чисел N, например, порядка > >2^1024 не представляется возможным. > > Можно попытаться свести факториал к арифм. прогресии. > Типа > (N-1)! = a ^ [N(N-1)/2) mod N вот примерное док-во теоремы > Вильсона. > > Короче, кто врубится в алгоритм быстрого факториала - > немедля мыльте сюда! можно мне? спасибо!
я врублюсь.
малая китайская теорема об остатках даст существенное приращение, но потребует проверки на каждом шаге и общая эффективность увеличивается не в разы.
да и в разы супротив экспоненты - мизер.
есть забавное индийское решение, но пока его таят от широких масс...
подробно о проекте
Анализ криптографических сетевых...
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
