Поговорим о факторизации

есть любопытный момент если N-1 имеет достаточно малые делители, то можно подобрать A^phi(d) mod N=1, где d|N-1

 

maxdiver

Да, это один из вариантов, хотя конечно f(x) вовсе не обязана быть вида x^2+C. Можно также брать С случайно.

Это вывод на основании каких-то опытов или просто твое предположение? Теоретически такое действительно может произойти (потому и метод честно называется "из семейства Monte-Carlo"), но на практике наблюдается крайне редко даже для одной начальной функции (не говоря уже о нескольких последовательно выбранных). Беда в том, что вычислить точную вероятность неудачи невозможно, в лучшем случае примерно оценить.

Если хочешь более детально разобраться с алгоритмами, могу посоветовать две книги по теме:
Cohen H.A. A Course in Computational Algebraic Number Theory
Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone Handbook of Applied Cryptography

Там расписано очень многое, в случае чего спрашивай - будем думать вместе

p-1 это другой метод того же автора, имеет примерно ту же скорость и сложность, но рассчитан на числа с так называемыми "B-smooth" делителями для примерно известного, не очень большого B. Реализация не сложнее. чем для rho.

А чем тебе вероятностные не нравятся? Если взять число побольше, то с помощью "четких" (видимо детерминированных?) тестов ты будешь проверять его до второго пришествия. В вероятностных тестах можно задать нужную границу уверенности, кроме того можно использовать комплексные тесты вроде того же BPSW. Если тебе удастся найти составное число, которое он определит как простое, то ты будешь первым, кому это удалось (со всеми вытекающими, славой и даже, если не ошибаюсь, небольшой премией )

 

http://algolist.manual.ru/maths/count_fast/phi_n.php

ВОТ ЕТО МОЩНО ЗАДВИНУЛИ(!!!..!!)-''Всего лишь..." - я им нумберы на 1024 бит пошлю у меня не получаеться 'ВСЕГО ЛИШЬ...' - А я так хочу фи посчитать у етих нумберов))

 

Stiver
я вообще то про алгоритм который обсуждали в этой теме.
просто выше была только ссылка на ныне покойные страницы с www.cse.iitk.ac.in и упоминался некий "алгоритм"
я просто уточнил какой именно алгоритм тут обсуждался и где найти ту инфу, на которую указывали сдохшие ссылки

 

зачем он тебе нужен вероятностные тесты вполне надёжны и более быстры??

 

он мне не нужен. просто наткнувшись на эту тему я начал искать про какой это такой "куда более крутой детерминистический тест. Тест очень быстр." идет речь, и как это я до сих пор не в курсе.
Потратив N времени и найдя инфу решил предостеречь других, чтоб народ знал, что под "супер пупер" алго подразумевался AKS

 

насколько я знаю он опубликован в 2002 году и на практике особо его не юзают - вероятность форева!!)

 

---------

 

UbIvItS

Господи ты моя воля.. Тебе не надоело бред писать??

Удивительно, да? Особенно если учесть, что L(1,p) = 1 (где L - символ Лежандра)

1^2 = 1 mod 3
2^2 = 1 mod 3

Действительно легко доказать..

 

а тебе не надоело отвечать на пустые сообщения) - свою ошибку я уже обнаружил и стёр, так о чем ты речь ведешь??????))) - я ищу и на этом пути всегда много ошибок - не ошибаеться тот, кто ничего не делает)

 

Stiver

Ну вот я и добрался до quadratic sieve
А вот что значит "не очень большие числа"? Для 10^16 за секунду точно отработает?

 

Mpqs вроде делает 80 бит за три минуты 100 бит за 6 часов, если правильно помню.

 

maxdiver

Зависит от реализации, обычно кладут границу между QS и NFS в районе 80-100 десятичных разрядов.

Работать с абсолютной скоростью немного некорректно, так как она зависит от реализации и машины. У меня RSATool (с MPQS only) раскладывает 128 бит за 1-2 секунды.

 

Stiver
С реализацией, конечно, пока проблемы. Собственно, я пока пытаюсь реализовать Диксона, а не квадратичное решето
Но учитывая, что "RSATool (с MPQS only) раскладывает 128 бит за 1-2 секунды", у меня запас есть

 

Stiver

что у тебя за тачка - супер комп домой перебазировал - насколько помню разработчики mpqs на сайте у себя писали, что на последних атлонах 80 бит за 3 мин.

 

"80 бит за три минуты"
и
"128 бит за 1-2 секунды"
Что-то несостыковывается

 

maxdiver
вот и я о том же - что за чудо проц???????........????
http://en.wikipedia.org/wiki/Quadratic_sieve
Цитата
It is the fastest available implementation of MPQS, factoring RSA-100 in eleven hours on a 2200MHz Athlon64; on the same system, a 60-digit number takes just over six seconds, a 70-digit number 80 seconds, an 80-digit number just under ten minutes and a 90-digit number about eighty minutes.

 

UbIvItS

Ты разницу между десятичным разрядом и битом знаешь? Хватит еще и эту ветку зафлуживать.

maxdiver
Что-то несостыковывается

К сожалению у этого товарища много чего не состыковывается

 

Stiver
с каких это пор rsa -100 в десятичных разрядах?
может rsa -1024 тоже в десятичных разрядах??

 

хотя я прогнал ) -бывает