Subversion Repositories mitteramskogler

Compare Revisions

Ignore whitespace Rev 5 → Rev 6

/trunk/Software/Maple/ModularSquareRoot/modSqrt.mpl
5,8 → 5,8
# INPUT:
# ------
# Let D := \bar{Q}[x], then
# - A ... polynomial in D,
# - M ... polynomial in D (the modulus) such that degree(M) > 0 and M is
# - A ... polynomial \in D,
# - M ... polynomial \in D (the modulus) such that degree(M) > 0 and M is
# square-free (all linear factors are distinct),
# - x ... variable of the polynomial ring D.
#
13,7 → 13,10
# OUTPUT:
# -------
# - MsqrtA \in D such that MsqrtA(m_i)^2 = A(m_i), where m_i are the roots
# of M, and degree(MsqrtA) < degree(M).
# of M, and degree(MsqrtA) < degree(M). In other words,
# MsqrtA^2 = A mod (x - m_i)
# and since A is square-free,
# MsqrtA^2 = A mod M.
#
# EXAMPLES:
# ---------
22,12 → 25,20
# > modSqrt(A, M, x);
# 4*x^2 - 1
#
# The result is not necessarily of lowest degree due to its special form. For
# more details take a look at the construction in the for-loop at the end of
# the algorithm.
# > M := (x - sqrt(2))*(x - 2);
# > A := x^2;
# > modSqrt(A, M, x);
# 3*x + 2*x*2^(1/2) - 4 - 4*2^(1/2)
# (3 + 2*2^(1/2))*x - 4 - 4*2^(1/2)
#
# > M := t - RootOf(_Z^2 - _Z - 1);
# > M := t^2 + t + 1;
# > A := t^3 - t^2 - t - 1;
# > modSqrt(A, M, t);
# 2/3*I*3^(1/2)*t + 1/3*I*3^(1/2)
#
# > M := (t - RootOf(_Z^2 - _Z - 1));
# > A := t^3;
# > modSqrt(A, M, t);
# (2*RootOf(_Z^2 - _Z - 1) + 1)^(1/2)
39,7 → 50,7
# factor non-trivially.
#
# AUTHOR: Johann Mitteramskogler
# EMAIL: Johann.Mitteramskogler@risc.jku.at
# EMAIL: johann.mitteramskogler@risc.jku.at
 
modSqrt := proc(A, M, x)
 
/trunk/Software/Maple/ModularSquareRoot/testModSqrt.mpl
1,37 → 1,58
# Test function
# Test file for 'modSqrt.mpl'.
#
# AUTHOR: Johann Mitteramskogler
# EMAIL: johann.mitteramskogler@risc.jku.at
testModSqrt := proc(A, M, x)
local mi, MsqrtA;
 
# Test with evaluation
# 'MsqrtA^2 - A' must be divisible by the modulus, since 'M' is square-free
MsqrtA := modSqrt(A, M, x);
for mi in solve(M, x) do
if simplify(evala(Simplify( eval(MsqrtA, x=mi)^2 - eval(A, x=mi) ))) <> 0 then
error("Computation wrong!");
if Algebraic:-Remainder(MsqrtA^2 - A, M, x) <> 0 then
error("failure: not divisible by the modulus!");
end if;
 
# Redundant, but for the sake of verification of the output condition
for mi in PolynomialTools:-Splits(Algebraic:-ConvertRootOf(M), x)[2] do
 
# Use division by linear polynomial instead of evaluation (polynomial
# remainder theorem)
if Algebraic:-Remainder(MsqrtA^2 - A, mi[1], x) <> 0 then
error("failure: not divisible by factors of the modulus!");
end if;
end do;
 
# Test with polynomial division
if simplify(rem(MsqrtA^2 - A, M, x)) <> 0 then
error("Computation wrong!");
end if;
 
print("Passed");
print("Test passed");
end proc;
 
 
# A few tests:
M := x^3 - x - 1; A := x; testModSqrt(A, M, x);
M := x^2 - x - 1; A := x + 2; testModSqrt(A, M, x);
M := z^4 - z^3 + z; A := z^3 + z; testModSqrt(A, M, z);
M := t^2 + 1; A := t^2 - 1; testModSqrt(A, M, t);
M := w - 1; A := w; testModSqrt(A, M, w);
M := 100*(x^3 - x - 1); A := 20*x - 1; testModSqrt(A, M, x);
# A couple of tests:
M := x^3 - x - 1; A := x; testModSqrt(A, M, x);
M := x^2 - x - 1; A := x + 2; testModSqrt(A, M, x);
M := z^4 - z^3 + z; A := z^3 + z; testModSqrt(A, M, z);
M := t^2 + 1; A := t^2 - 1; testModSqrt(A, M, t);
M := w - 1; A := w; testModSqrt(A, M, w);
M := 100*(x^3 - x - 1); A := 20*x - 1; testModSqrt(A, M, x);
M := t^2 + t + 1; A := t^3 - t^2 - t - 1; testModSqrt(A, M, t);
M := x - 2; A := 0; testModSqrt(A, M, x);
M := z^4 - z^3 + z; A := 1; testModSqrt(A, M, z);
M := 100*(x^3 - x - 1); A := 2; testModSqrt(A, M, x);
 
M := (x - 1)*(x - 2)*(x - 3);
A := 32*x^12 - x^4 + 4*x^2 - I*x + sqrt(5);
testModSqrt(A, M, x);
 
M := 10*(x + 1)*x*(x - 1);
A := 8*x^2 + 1;
testModSqrt(A, M, x);
 
M := x - 2; A := 0; testModSqrt(A, M, x);
M := z^4 - z^3 + z; A := 1; testModSqrt(A, M, z);
M := 100*(x^3 - x - 1); A := 2; testModSqrt(A, M, x);
M := (x - sqrt(2))*(x - 2);
A := x^2;
testModSqrt(A, M, x);
 
M := t^2 + t + 1;
A := t^3 - t^2 - t - 1;
testModSqrt(A, M, t);
 
M := (t - RootOf(_Z^2 - _Z - 1));
A := t^3;
testModSqrt(A, M, t);