Сайт о программировании, математике и моделировании
Записи с метками метод Брента
Оценка ускорения РО-алгоритма
1 Декабрь
Для оценки скорости работы и ускорения алгоритма построенному с помощью различных методов была разработана программа, реализующая данные методы и проведены экспериментальные исследования. Измерения производились на Celeron 900MH, 256Mb оперативной памяти, ОС Windows XP. Читать дальше >
Ускорение РО-алгоритма с помощью алгоритма нахождения периода последовательности методом Брента.
1 Декабрь
1. [Начальная установка.] Присвоить x←5, x’←2, k←1, l←1, n←N. (Во время выполнения этого алгоритма число n не является множителем числа N, а переменные x и x’ представляют величины xm mod n xl(m)-1 mod n в выражении (1), где также f(x)=x2+1, A=2, l=l(m) и k=2l-m.)
2.1. [Проверить, будет ли число простым.] Если n – простое число Читать дальше >
Методы ускорения алгоритмов
1 Декабрь
Первый метод ускорения заключается в том, что время вычисления НОД занимает много времени, поэтому используем китайскую теорему об остатках и попробуем ускорить начальный алгоритм. Китайская теорема об остатках: любое не отрицательное число которое не превышает каждого из множителей модуля можно однозначно восстановить если известны его остатки по этим модулям. Читать дальше >
