Как быстро посчитать M! mod N?

вернёмся-ка к вопросу о phi(x)==phi(N), если N содержит надёжные множители произведение, коих == T, то x==T*Z, где gcd(N, T)==T & gcd(Z, N)==1. для рса x==2*N.

 

UbIvItS
Тихо сам с собою я веду беседу... Live Journal?

 

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

 

кто-нить ведает как уличить на делимость x на А или y на А (А-нечёт>3 и x^2-y^2==N-нечёт)?? для 3 этот момент определяется элементарно, а дальше тёмныыый лес

 

Уважаемые, пожалуйста, посоветуйте мне более/менее быстрый релиз MPQS - желательно более
возникла шальная мысля - попробую.... )

 

Вот mpqs4linux для винды (каламбур-с).
Но сейчас GNFS (например, ggnfs или msieve) больше в моде.

 

UbIvItS

Если я правильно понял, под "уличить делимость" здесь подразумевается вопрос о том, насколько вероятно, что x или y, удовлетворяющие равенству x^2 - y^2 = N, делятся на A.
Здесь можно предполагать, что по модулю A, значения x и y ведут себя как случайные, связанные сравнением x^2 - y^2 == N (mod A). Прикинем число решений этого сравнения в предположении, что A - простое, а N - нечетное.

По модулю A у нас имеется примерно A/2 квадратов, соответственно разностей различных квадратов будет (A/2)^2, и они покрывают весь интервал вычетов по модулю A примерно равномерно; поэтому число решений примерно равно A/4. Но делящихся на A из них будет не более 4 (либо x делится, тогда y определяется однозначно с точностью до знака; либо y, и тогда определяется x).
Поэтому вероятность делимости хотя бы одного из x,y на A для больших A примерно равна 16/A.

 

RElf
ситуация выглядит примерно так: N==t mod A; A - простое число; теперь если t - неквадратичный вычет, то А не делит Y с вероятностью 100%; если t - квадратичный вычет, то А|Y c вероятностью Z/M, где Z - кол-во делителей X, а M - кол-во простых чисел (А), дающих (t, А)==1 ( () - символ Лежандра ).

 

UbIvItS
Ну и какой смысл выражать это через X и Y, которые нам неизвестны? Выше я дал приближенную оценку вероятности, не зависящую от X,Y, а только от A (которое мы выбираем сами).

 

RElf
а смысл выщимить максимально факторы X & Y - тем самым сократив область перебора для поиска факторов N, но, как это обычно бывает, объективная реальность гадит хорошие идеи). со 100% вероятностью мы можем только выяснить делиться ли X || Y на 3 и 16, а остальные вопросы делают исследователю нехорошие жесты и посылают за тридевять земель)

точней Y

 

Приветствую!
Воможно это будет оффтопик, вроде приблизительно по теме, надеюсь простите, но вопрос весьма важный.
Есть-ли тут кто понял Тест Миллера — Рабина ?
( http://ru.wikipedia.org/wiki/Тест_Миллера_—_Рабина )
При поиске свидетеля при проверке числа 17, получается : m-1 = 16; s=4; t=1
При подстановке а=5, получается a^t = 5^1 = 5
При взятии остатка от деления получается: (a^t mod m) = (5 mod 17) = 5;
5 не равно ни единице ни минус_единице, т.е. 17 - составное? =)

 

Ernesto

Нет. Если a^t не равно плюс или минус 1, то это число нужно возводить в квадрат пока не получится плюс или минус 1 (не более s возведений в квадрат):
5^2 mod 17 = 8
8^2 mod 17 = 13
13^2 mod 17 = 16 = -1 mod 17.
Таким образом, a=5 является свидетелем простоты для 17.
Теперь нужно брать другое случайное a и проверять то же самое для него и т.д.

 

Йухты! Я видел, что перечислению подлежат и свидетели и степень, но трактовать это можно по разному.
(Поправочка "не более s-1 возведений в квадрат")

Огромное спасибо! (Единственный мат-форум, где можно получить ответ)

Еще один вопрос "почти_в_тему" -
При расчете ключей RSA рекомендуется использовать "Расширенный алгоритм Евклида и соотношение Безу" (с) Вики.
Но он позволяет найти A и B для AX+BY=0. А в алгоритме расчета ключей требуется найти их для AX+BY=1. Как быть не подкинете советик? =)

(И еще - вы что - все это на асме делаете? Я когда-то гордился тем что на асме написал компиллятор асмы. Теперь посмотрел на вас, теперь не горжусь)

 

Ernesto

"Перечисления" здесь нет никакого. Много свидетелей простоты находят для большей достоверности - чем их больше получено (их количество регулируется числом раундов), тем больше веротяность, что алгоритм не соврет, назвав составное число простым. Возведения в квадрат здесь являются частью под-алгоритма, определяющего является ли выбранное a свидетелем простоты или нет.
Причем возведений в степень для каждого конкретного a может потребоваться вплоть до s включительно (в случае если выбранное a не является свидетелем простоты).

Нет! Перечитайте внимательно. Расширенный алгоритм Евклида находит такие A и B, что AX+BY=НОД(X,Y). В случае RSA X,Y выбраны так, что НОД(X,Y)=1, и поэтому результатом алгоритма Евклида будет в точности равенство AX+BY=1.

 

Упс. Нулю результат будет равен если продлить процесс на еще одну, видимо, лишнюю итерацию.
Для взаимно-простых ведь действительно НОД равен 1 и на этом стоит остановится!

А если моя реализация расчитывает "X^Y mod Z" при их размерностях порядка 10^616 примерно за 15 секунд - это повод еще поработать над оптимизацией?
(компьютер специально выбран среднестатистический)

Вы не даете платных уроков? =)

 

Ernesto

Нет. Только бесплатные и только по настроению =)

 

Я попросту в тупике.
Если я "X^Y mod Z" расчитываю 15 секунд, до для получения четырех тысяч свидетелей простоты, мне в лучшем случае потребуется 16 часов 40 минут. (длина искомого простого числа - 2048 бит)
Если вероятностный подход со свидетелями простоты - ускорение поиска простых чисел, то должно быть и ускорение этого ускорения! и его юзают!
Я видел шифровальные проги (тот-же PGP-диск), они не работают по 32 часа над генерацией пары ключей. Вы, господа математики, что-то от меня скрываете! ;]

При длинах X, Y и Z в 512 бит, операция "X^Y mod Z" выполняется за 0.5-0.7 сек.
Это крах.

 

Долго делал (часов 5), долго думал (дня два), синтезировал из кучи источников следующее:

Для перечисляемых свидетелей простоты, подтверждение свидетельства обязательно для каждого. (Т.е. "логическое И")
А для каждого отдельно взятого свидетеля равенство его модуля единице либо минус_единице - достаточно одного ня всех ( "ИЛИ" ).

Т.е. степени свидетеля должны пройти тест на равенство "+-1" по принципу "ХОТЬ_ОДИН", а сами свидетели должны пройти тест в целом по принципу "ВСЕ_БЕЗ_ИСКЛЮЧЕНИЯ".

И плюс к тому примечание: "+1" ожидается лишь для изначальной нечетной степени t ( равной (m-1)/2^s ), для всех остальных степеней ожидается лишь "-1". Иные попадают в т.н. перечень "лжесвидетелей". (да, такое я тоже слышал)
Я все правильно понял? (Надеюсь хоть раз первым словом окажется "Да" =) )

Фуф. Выговорился.

 

Ernesto
не лезь на вики, а лезь на sourceforge.net и там бери нормальный релиз на с/с++ усех ентих метод и возьми нормальную книжечку: вот тут полазий: http://functions.wolfram.com/, ну, и русские ресурсы найти можно.

 

Ух. Сенкс.