Алгоритм (тест простоты) для определения очень больших простых чисел / Программирование

Мобильная версия Контакт Правила FAQ Помощь

Гость

Войти | Регистрация | Профиль | Очистить

Форумы | Пользователи | Статистика | Мод. лог | Поиск

Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр

Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритм (тест простоты) для определения очень больших простых чисел

1 сообщений из 76, страница 4 из 4

все

Алгоритм (тест простоты) для определения очень больших простых чисел

#39893132

Gennadiy Usov

Гость

Gennadiy Usov

Нашел для Питона распечатку программы pow:
http://qaru.site/questions/132239/how-did-python-implement-the-built-in-function-pow

Код: sql

1.
2.
3.
4.
5.
6.
7.
8.
9.

def pow_mod(x, y, z):				
	"Calculate (x ** y) % z efficiently."			
	number = 1			
	while y:			
		if y & 1:		
			number = number * x % z	
		y >>= 1		
		x = x * x % z		
	return number

Это самая быстрая программа для Питона для pow?

Решил ещё раз исследовать эту программу.

Если проверяемое число будет немного меньше 2^n - 1, то данная программа вычисляет 2*n умножений по модулю.

Эвристический алгоритм 22015600 для аналогичного числа вычисляет n + 1 умножений по модулю.

Это объясняет то, что эвристический алгоритм работает быстрее алгоритма pow для чисел, которые немного меньше 2^n - 1.

...

Рейтинг:

0 / 0

22.11.2019, 19:14

| Ответить | Цитировать | Написать

1 сообщений из 76, страница 4 из 4

все

Цитировать

Написать

Автор*:

Ввести пароль для входа

Тема*:

Сообщение

Данное сообщение тематическое

Сообщение содержит картинки или видео 18+

Автор:

ВНИМАНИЕ! На данном подфоруме действуют строгие правила. Удостоверьтесь, что ваше сообщение соответствует им!

Форум или тема закрыты для гостей. Необходима авторизация!

Загрузить последнюю сохраненную версию

Вложение:

Вставить как галерею

Максимальный размер вложений: 4,0 МБ, аудио/видео: 8,0 МБ. Картинки большего размера ужимаются, если возможно.

Введите код, изображенный на картинке. Если код нечитаемый, кликните картинку, чтобы загрузить другой вариант.

Отправляя сообщение, я выражаю свое согласие с правилами форума и принимаю пользовательское соглашение.

Читали тему (0):

Читали форум (0):

Пользователи онлайн (0):

start [/forum/topic.php?fid=16&msg=39893132&tid=1339872]:	0ms
get settings:	8ms
get forum list:	12ms
check forum access:	4ms
check topic access:	4ms
track hit:	322ms
get topic data:	11ms
get forum data:	3ms
get page messages:	42ms
get tp. blocked users:	1ms
others:	267ms

total:	674ms