모듈:NumberTheory: 두 판 사이의 차이
둘러보기로 이동
검색으로 이동
백괴게임>Riemann 잔글편집 요약 없음 |
백괴게임>Riemann 잔글 (역원을 계산할 수 없을 때, 무한 루프에 빠지지 않게 함.) |
||
(같은 사용자의 중간 판 6개는 보이지 않습니다) | |||
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 | 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