모듈:NumberTheory: 두 판 사이의 차이

리버티게임(개발), 모두가 만들어가는 자유로운 게임
둘러보기로 이동 검색으로 이동
백괴게임>Riemann
잔글편집 요약 없음
백괴게임>Riemann
잔글 (역원을 계산할 수 없을 때, 무한 루프에 빠지지 않게 함.)
 
(같은 사용자의 중간 판 7개는 보이지 않습니다)
1번째 줄: 1번째 줄:
local getArgs = require('모듈:Arguments').getArgs
local getArgs = require('모듈:Arguments').getArgs
local p = {}
local p = {}
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
function _inverseMod( z, m )
if _gcd( z, m ) ~= 1 then
return nil
else
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
end


function _powerMod( root, expo, modulo )
function _powerMod( root, expo, modulo )
local BaseConvert = require( '모듈:BaseConvert' );
local BaseConvert = require( '모듈:BaseConvert' );
if tonumber(expo) < 0 then
root = _inverseMod( root, modulo )
expo = -expo
end
local power = 1;
local power = 1;
local expo2 = BaseConvert.convert({n = expo, base = 2});
local expo2 = BaseConvert.convert({n = expo, base = 2});
27번째 줄: 93번째 줄:
      
      
     return _powerMod( root, expo, modulo )
     return _powerMod( root, expo, modulo )
end
function _gcd(args)
gc = math.abs(args[1])
local i;
for i = 2, #args 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
end
return args[2] --gc
end
function p.gcd(frame)
local args = getArgs(frame)
return _gcd(args)
end
end


return p
return p

2018년 3월 1일 (목) 22:12 기준 최신판

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

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

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

function _inverseMod( z, m )
	if _gcd( z, m ) ~= 1 then
		return nil
	else
		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
end

function _powerMod( root, expo, modulo )
	local BaseConvert = require( '모듈:BaseConvert' );
	if tonumber(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

return p