algorytm.org

Implementacja w Python

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Szybkie potęgowanie modularne - Implementacja w Python
Ocena użytkownikóww: *****  / 0
SłabyŚwietny
Nadesłany przez Adam Chrapkowski, 07 grudnia 2013 20:04
Kod przedstawiony poniżej przedstawia główną część rozwiązania problemu.
Pobierz pełne rozwiązanie.

fme.py:
# Szybkie potegowanie modularne
# www.algorytm.org
#
# tested with Python 3.3
# license: Public Domain

def fme(a, k, n):
	"""
	modular exponentiation
	a ** k mod n
	"""
	b = bin(k)[2:] # list of bits
	m = len(b)
	r = 1 # result
	x = a % n

	for i in range(m - 1, -1, -1):
		if b[i] == '1':
			r = r * x % n

		x **= 2
		x  %= n

	return r

# Python built-in alternative:
#     pow(a, k, n)
Dodaj komentarz