모듈:NumberTheory

이 모듈에 대한 설명문서는 모듈:NumberTheory/설명문서에서 만들 수 있습니다

local getArgs = require('모듈:Arguments').getArgs
local p = {}

function _inverseMod( z, m )
	local a = math.abs(m)
	local b = math.abs(z) % a
	local qt = {1}
	local c
	local p = 1
	local q
	local r
	while c ~= 0 do
		c = a % b
		qt[#qt + 1] = 0 - math.floor(a / b)
		a = b
		b = c
	end
	q = qt[#qt - 1]
	local i
	for i = #qt - 2, 2, -1 do
		r = p
		p = q
		q = r + q * qt[i]
	end
	while q < 0 do
		q = q + m
	end
	return q % m
end

function _powerMod( root, expo, modulo )
	local BaseConvert = require( '모듈:BaseConvert' );
	if expo < 0 then
		root = _inverseMod( root, modulo )
		expo = -expo
	end
	local power = 1;
	local expo2 = BaseConvert.convert({n = expo, base = 2});
	local i;
	for i = 1, #expo2 do
		power = (power * power) % modulo;
		power = power * (root ^ expo2:sub(i,i)) % modulo;
		end
	return power
end

function p.powerMod(frame)
	local args
    if frame == mw.getCurrentFrame() then
        args = frame.args
    else
        args = frame
    end
    
    local root = args.root
    local expo = args.expo
    local modulo = args.modulo
    
    return _powerMod( root, expo, modulo )
end

function _gcd(args)
	if args[1] == nil then
		return 1
	else
		gc = math.abs(args[1])
		if args[2] == nil then
			return gc
		else
			local i = 2;
			while args[i] ~= nil do
				local a = gc;
				local b = math.abs(args[i]);
				local c;
				while c ~= 0 do
					c = a % b;
					a = b;
					b = c;
				end
				gc = a
				i = i + 1
			end
			return gc
		end
	end
end
		

function p.gcd(frame)
	local args = getArgs(frame)
	return _gcd(args)
end

return p