0 ? implode("a", $random) : "");
}
function randomEncode($s) {
$enc = array('a'=>'a','0'=>'b','1'=>'c','2'=>'d','3'=>'e','4'=>'f','5'=>'B','6'=>'C','7'=>'D','8'=>'E','9'=>'F');
for ($i = 0; $i < strlen($s); $i++) $s[$i] = $enc[$s[$i]];
return $s;
}
function randomDecode($s) {
$dec = array('a'=>'a','b'=>'0','c'=>'1','d'=>'2','e'=>'3','f'=>'4','B'=>'5','C'=>'6','D'=>'7','E'=>'8','F'=>'9');
for ($i = 0; $i < strlen($s); $i++) $s[$i] = $dec[$s[$i]];
return $s;
}
function coprimeFactors($l, $m, $a) {
$r = array();
foreach ($l as $k)
if (gcd($m, $k) == 1 && $a % $k == 0)
$r[] = $k;
return $r;
}
function coprimes($l, $m) {
$r = array();
foreach ($l as $k)
if (gcd($m, $k) == 1)
$r[] = $k;
return $r;
}
////////////////////////////////////////////////////////////////
// Exercise generators.
$data = array(
'small primes' => array(2,3,5,7,11,13),
'medium primes' => array(2,3,5,7,11,13,17,19,23,29,31),
'large primes' => array(2,3,5,7,11,13,17,19,23,29,31,37),
'small primes 3 mod 4' => array(3,7,11),
'medium primes 3 mod 4' => array(3,7,11,19,23),
'small composites and primes' => array(2,3,4,5,6,7,8,9,10,11),
'medium composites and primes' => array(2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30),
'medium composites' => array(4,6,8,9,10,12,14,15,16,18,20,21,22,24,25,26,27,28,30)
);
$templates = array(
"exercise_equation_prime_modulus",
"exercise_equation_fermat_little_theorem",
"exercise_phi_simple_compute",
"exercise_CRT_coprime_two_solve",
"exercise_CRT_general_two_solve",
"exercise_CRT_general_two_solve",
"exercise_CRT_general_two_solve",
"exercise_CRT_general_two_solve"
//,"exercise_sqrt_mod_prime_solve"
);
function gcd($a,$b) {
return ($a % $b) ? gcd($b,$a % $b) : $b;
}
function prime_powers($n) {
$primes = array(2,3,5,7,11,13,17,19,23,29,31,37);
$pps = array();
while ($n > 1) {
foreach ($primes as $p) {
if ($n % $p == 0) {
if (!array_key_exists($p, $pps))
$pps[$p] = 0;
$pps[$p]++;
$n = $n / $p;
}
}
}
return $pps;
}
function exercise_equation_prime_modulus($data) {
$c = null;
while ($c == null) {
$m = randomElement($data['medium composites and primes']);
$d = randomElement($data['medium composites']);
$b = randomInRange(1, $d);
$c = randomElement(coprimeFactors(rangeFromTo(2,$m), $m, $d));
}
$a = ($d + $b) % $m;
$solution = $d / $c;
$x = $solution;
$e = (($a - $b) % $m);
while ($e < 0)
$e = $e + $m;
$exercise = '
';
$solution =
'
';
return array($exercise, $solution);
}
function exercise_equation_fermat_little_theorem($data) {
$p = randomElement($data['large primes']);
$a = randomElement(rangeFromTo(1,$p));
$e = $p-1;
$exercise = '
'.$e.' (\mod '.$p.')
\end{eqnarray}
]]>';
$solution =
'Fermat\'s little theorem, the solution is:
\begin{eqnarray}
%x & \equiv & '.$a.'('.$p.' %- 1) (\mod '.$p.') %%
& \equiv & 1
\end{eqnarray}
]]>
';
return array($exercise, $solution);
}
function exercise_phi_simple_compute($data) {
$n = randomElement($data['medium composites and primes']);
$phi = 0;
for ($a = 0; $a < $n; $a++)
if (gcd($a,$n) === 1)
$phi++;
$prime_powers = prime_powers($n);
$phi_exps = array(0 => array(), 1 => array());
foreach ($prime_powers as $p => $k) {
if ($k == 1) {
$phi_exps[0][] = "\phi(".$p.")";
$phi_exps[1][] = "(".$p." %- 1)";
} else {
$phi_exps[0][] = "\phi(".$p."".$k.")";
$phi_exps[1][] = "(".$p."".$k." %- ".$p."".$k." %- 1)";
}
}
$exercise = '
';
$solution = '
Euler totient function \varphi for
prime numbers,
powers of primes, and
products of coprime numbers,
we can compute the solution as follows:
\begin{eqnarray}
\phi('.$n.') & = & '.implode(" \cdot ", $phi_exps[0]).' %%
& = & '.implode(" \cdot", $phi_exps[1]).' %%
& = & '.$phi.'
\end{eqnarray}
]]>
';
return array($exercise, $solution);
}
function exercise_CRT_coprime_two_solve($data) {
$n = randomElement(remove($data['small composites and primes'], 2));
//$m = randomElement(remove($data['small composites and primes'], $n));
$m = randomElement(coprimes(rangeFromTo(2,$n), $n));
$g = gcd($m, $n);
$x = randomInRange($m, ($m * $n / $g));
$a = $x % $n;
$b = $x % $m;
$r = $x % $g;
$exercise = '
';
if ($g == 1) {
$solution = '
formula for a Chinese remainder theorem solution for a system of two equations when the moduli are coprime, we find that the unique congruence class of solutions is:
\begin{eqnarray}
%x & \equiv & '.$a.' \cdot ('.$m.' \cdot '.$m.'^{-1}) + '.$b.' \cdot ('.$n.' \cdot '.$n.'^{-1}) (\mod ('.$n.' \cdot '.$m.')) %%
& \equiv & '.($x % (($n * $m) / $g)).' (\mod '.(($n * $m) / $g).')
\end{eqnarray}
]]>
';
} else {
$solution = '
process for computing a Chinese remainder theorem solution for a system of two equations when the moduli are not necessarily coprime, we find that the unique congruence class of solutions is:
\begin{eqnarray}
%x & \equiv & '.($x % (($n * $m) / $g)).' (\mod '.(($n * $m) / $g).')
\end{eqnarray}
]]>
';
}
return array($exercise, $solution);
}
function exercise_CRT_general_two_solve($data) {
$n = randomElement($data['small composites and primes']);
$m = randomElement(remove($data['small composites and primes'], $n));
$g = gcd($m, $n);
$x = randomInRange($m, ($m * $n / $g));
$a = $x % $n;
$b = $x % $m;
$r = $x % $g;
$exercise = '
';
if ($g == 1) {
$solution = '
formula for a Chinese remainder theorem solution for a system of two equations when the moduli are coprime, we find that the unique congruence class of solutions is:
\begin{eqnarray}
%x & \equiv & '.$a.' \cdot ('.$m.' \cdot '.$m.'^{-1}) + '.$b.' \cdot ('.$n.' \cdot '.$n.'^{-1}) (\mod ('.$n.' \cdot '.$m.')) %%
& \equiv & '.($x % (($n * $m) / $g)).' (\mod '.(($n * $m) / $g).')
\end{eqnarray}
]]>
';
} else {
$solution = '
process for computing a Chinese remainder theorem solution for a system of two equations when the moduli are not necessarily coprime, we find that the unique congruence class of solutions is:
\begin{eqnarray}
%x & \equiv & '.($x % (($n * $m) / $g)).' (\mod '.(($n * $m) / $g).')
\end{eqnarray}
]]>
';
}
return array($exercise, $solution);
}
function exercise_sqrt_mod_prime_solve($data) {
$p = randomElement($data['small primes 3 mod 4']);
$r = randomInRange(1, $p);
$solution = null;
$attempt = pow($r,(($p+1)/4)) % $p;
for ($x = 0; $x < $p; $x++) {
if ((($x * $x) % $p) === $r) {
$solution = $x;
break;
}
}
if ($solution !== null)
$x = $solution;
$exercise = '
';
$solution = $solution != null ?
'explicit formula for computing square roots of congruence classes modulo a prime, the solution is:
\begin{eqnarray}
%x & \equiv & \pm ('.$r.')('.$p.'+1)/4 (\mod '.$p.') %%
& \equiv & \pm '.$solution.' (\mod '.$p.')
\end{eqnarray}
]]>
'
:
'explicit formula for computing roots of congruence classes modulo a prime:
\begin{eqnarray}
%x & \equiv & \pm ('.$r.')('.$p.'+1)/4 (\mod '.$p.') %%
& \equiv & \pm '.$attempt.' (\mod '.$p.') %%
('.$attempt.')^2 & \not\equiv & '.$r.' (\mod '.$p.')
\end{eqnarray}
Since the formula did not return a valid root, there is no solution; '.$r.' is not a quadratic residue in \Z/'.$p.'\Z]]>';
return array($exercise, $solution);
}
////////////////////////////////////////////////////////////////
// Generate the exercise.
$exercise = call_user_func(randomElement($templates), $data);
function wrapXML($link, $exercise_solution) {
return
''
. ''
. $exercise_solution[0] . $exercise_solution[1]
. ''
. '';
}
////////////////////////////////////////////////////////////////
// Render the exercise as a lecture-notes-like page.
// Load the library and rendering hooks.
include("sheaf/sheaf.php");
include("sheaf/hooks/math.php");
include("sheaf/hooks/Python.php");
// Build the course material data structure instance by setting
// the configuration parameters for the material invocation.
$s = new Sheaf(
array(
'path' => 'sheaf/',
'content' => wrapXML('exercises.php?exercise='.deterministicLink(), $exercise),
'message' => 'NOTE: This page randomly generates an exercise and its solution. Click here to refresh the page and generate a new exercise. Use the [link] below if you want to return to the same exercise again at a later time. Click here to go back to the main page with the course information and schedule.
',
'toc' => 'false'
)
);
// Render the course materials in the specified XML file.
$s->html();
/* eof */ ?>