Lines Matching +refs:ps +refs:right +refs:header
26 \newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
27 \newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil}
384 \hline $\left [ 1 \right ]$ & An easy problem that should only take the reader a manner of \\
387 \hline $\left [ 2 \right ]$ & An easy problem that involves a marginal amount of computer \\
390 \hline $\left [ 3 \right ]$ & A moderately hard problem that requires a non-trivial amount \\
393 \hline $\left [ 4 \right ]$ & A moderately hard problem that involves a non-trivial amount \\
396 \hline $\left [ 5 \right ]$ & A hard problem that involves concepts that are difficult for a \\
417 additional research to be completed. The reader will most likely not know the answer right away, nor will the text provide
537 Usually when I start a project I will begin with the header files. I define the data types I think I will need and
549 \includegraphics{pics/design_process.ps}
581 if one starts writing a large number too far to the right on a piece of paper they will have to erase it and move left.
625 significant digit order. As a pencil and paper analogy the array is organized such that the right most digits are stored
654 In LibTomMath the multiple precision integer functions accept parameters from left to right as pointers to mp\_int
655 structures. That means that the source (input) operands are placed on the left and the destination (output) on the right.
664 The left to right order is a fairly natural way to implement the functions since it lets the developer read aloud the
668 of assignment expressions. That is, the destination (output) is on the left and arguments (inputs) are on the right. In
767 name represents a constant\footnote{Defined in the ``tommath.h'' header file within LibTomMath.}
1038 appended on the right.
1097 language the terms to \&\& are evaluated left to right with a boolean short-circuit if any condition fails. This is
1098 important since if the \textbf{used} is zero the test on the right would fetch below the array. That is obviously
1104 $\left [ 1 \right ]$ & Discuss the relevance of the \textbf{used} member of the mp\_int structure. \\
1106 $\left [ 1 \right ]$ & Discuss the consequences of not using padding when performing allocations. \\
1108 $\left [ 2 \right ]$ & Estimate an ideal value for \textbf{MP\_PREC} when performing 1024-bit RSA \\
1111 $\left [ 1 \right ]$ & Discuss the relevance of the algorithm mp\_clamp. What does it prevent? \\
1113 $\left [ 1 \right ]$ & Give an example of when the algorithm mp\_init\_copy might be useful. \\
1421 \end{array} \right .$ \\
1589 The first two steps compare the signs of the two inputs. If the signs do not agree then it can return right away with the appropriate
1608 $\left [ 2 \right ]$ & Modify algorithm mp\_set\_int to accept as input a variable length array of bits. \\
1610 $\left [ 3 \right ]$ & Give the probability that algorithm mp\_cmp\_mag will have to compare $k$ digits \\
1613 $\left [ 1 \right ]$ & Suggest a simple method to speed up the implementation of mp\_cmp\_mag based \\
1626 All of the algorithms within this chapter make use of the logical bit shift operations denoted by $<<$ and $>>$ for left and right
1628 number $0.9345$ is equivalent to $93.45\%$ which is found by sliding the the decimal two places to the right (\textit{multiplying by $\beta^2 = 10^2$}).
1818 is needed is a single zero or one bit for the carry. Therefore a single logical shift right by $\gamma - 1$ positions is sufficient to extract the
1959 \end{array} \right .$ \\
2015 the digits left or right as well to shift individual bits of the digits left and right. It is important to note that not all ``shift'' operations
2082 A division by two can just as easily be accomplished with a logical shift right as multiplication by two can be with a logical shift left.
2115 This algorithm will divide an mp\_int by two using logical shifts to the right. Like mp\_mul\_2 it uses a modified low level addition
2190 \includegraphics{pics/sliding_window.ps}
2211 Division by powers of $x$ is easily achieved by shifting the digits right and removing any that will end up to the right of the zero'th digit.
2442 than the input we just mp\_copy() the input and return right away. After this point we know we must actually
2451 $\left [ 3 \right ] $ & Devise an algorithm that performs $a \cdot 2^b$ for generic values of $b$ \\
2454 $\left [ 3 \right ] $ & Devise an efficient algorithm to multiply by small low hamming \\
2458 $\left [ 2 \right ] $ & Modify the preceding algorithm to handle values of the form \\
2461 $\left [ 3 \right ] $ & Using only algorithms mp\_mul\_2, mp\_div\_2 and mp\_add create an \\
2466 $\left [ 5 \right ] $ & Improve the previous algorithm to have a working time of at most \\
2467 & $O \left (2^{(k-1)}n + \left ({2n^2 \over k} \right ) \right )$ for an appropriate choice of $k$. Again ignore \\
2470 $\left [ 2 \right ] $ & Devise a chart to find optimal values of $k$ for the previous problem \\
2473 $\left [ 2 \right ] $ & Using only algorithms mp\_abs and mp\_sub devise another method for \\
2674 At this point the vector $x = \left < 10, 34, 45, 31, 6 \right >$ is the result of the first step of the Comba multipler.
2697 With that algorithm and $k = 5$ and $\beta = 10$ the following vector is produced $\vec x= \left < 1, 3, 8, 8, 1, 6 \right >$. In this case
2714 k \cdot \left (\beta - 1 \right )^2 < 2^{\alpha}
2720 k \cdot \left ( \beta^2 - 2\beta + 1 \right ) < 2^{\alpha}
2727 k < {{2^{\alpha}} \over {\left (2^{2\rho} - 2^{\rho + 1} + 1 \right )}}
2797 $O \left ((p + q)n^2 \right )$ time to multiply two $n$-digit numbers. The Comba method requires only $O(pn^2 + qn)$ time, however in practice,
2844 $W(1) = \left (\sum_{i = 0}^{n} a_i \right ) \left (\sum_{i = 0}^{n} b_i \right )$. The third point $\zeta_{\infty}$ is less obvious but rather
2850 $\left (2^q \right )^{2n} \cdot \zeta_{2^{-q}}$ for small values of $q$. The term ``mirror point'' stems from the fact that
2851 $\left (2^q \right )^{2n} \cdot \zeta_{2^{-q}}$ can be calculated in the exact opposite fashion as $\zeta_{2^q}$. For
2864 $O \left ( k^{lg_n(2n - 1)} \right )$ for $k$ digit inputs (\textit{assuming they have the same number of digits}). Figure~\ref{fig:exponent}
3125 description, several statements have been compounded to save space. The intention is that the statements are executed from left to right across
3225 For any $n$-digit input, there are ${{\left (n^2 + n \right)}\over 2}$ possible unique single precision multiplications required compared to the $n^2$
3241 Starting from zero and numbering the columns from right to left a very simple pattern becomes obvious. For the purposes of this discussion let $x$
3242 represent the number being squared. The first observation is that in row $k$ the $2k$'th column of the product has a $\left (x_k \right)^2$ term in it.
3269 \hspace{3mm}4.1 $\hat r \leftarrow t_{2ix} + \left (a_{ix} \right )^2$ \\
3318 extracted from the mp\_word accumulator using a right shift. Aliases for $a_{ix}$ and $t_{ix+iy}$ are initialized
3359 \hspace{3mm}5.5 $iy \leftarrow \mbox{MIN}(iy, \lfloor \left (ty - tx + 1 \right )/2 \rfloor)$ \\
3364 \hspace{6mm}5.8.1 $\_ \hat W \leftarrow \_ \hat W + \left ( a_{\lfloor ix/2 \rfloor}\right )^2$ \\
3415 Let $h(x) = \left ( f(x) \right )^2$ represent the square of the polynomial. The Karatsuba equation can be modified to square a
3419 h(x) = a^2x^2 + \left ((a + b)^2 - (a^2 + b^2) \right )x + b^2
3424 $O \left ( n^{lg(3)} \right )$.
3482 By expanding $\left (x1 + x0 \right )^2$, the $x1^2$ and $x0^2$ terms in the middle disappear, that is $(x0 - x1)^2 - (x1^2 + x0^2) = 2 \cdot x0 \cdot x1$.
3574 $\left [ 3 \right ] $ & Devise an efficient algorithm for selection of the radix point to handle inputs \\
3577 $\left [ 2 \right ] $ & In section 5.3 the fact that every column of a squaring is made up \\
3580 $\left [ 3 \right ] $ & Prove the equation for Karatsuba squaring. \\
3582 $\left [ 1 \right ] $ & Prove that Karatsuba squaring requires $O \left (n^{lg(3)} \right )$ time. \\
3584 $\left [ 2 \right ] $ & Determine the minimal ratio between addition and multiplication clock cycles \\
3587 $\left [ 3 \right ] $ & Implement a threaded version of Comba multiplication (and squaring) where you \\
3591 $\left [ 4 \right ] $ & Same as the previous but also modify the Karatsuba and Toom-Cook. You must \\
3643 This technique became popular since a normal integer multiplication and logical shift right are the only required operations to perform a multiplication
3653 modular exponentiation pre-computing $2^q/b$ will allow a division to be performed with a multiplication and a right shift. Both operations
3731 After the first multiplication inside the quotient ($q_0 \cdot \mu$) the value is shifted right by $m + 1$ places effectively nullifying the lower
3988 With this algorithm a single shift right at the end is the only right shift required to reduce the input instead of $k$ right shifts inside the
4167 Shift right and reduce modulo $\beta$ simultaneously. \\
4273 then a x86 multiplier could produce the 62-bit product and use the ``shrd'' instruction to perform a double-precision right shift. The proof
4378 Division by ten for example is simple for pencil and paper mathematics since it amounts to shifting the decimal place to the right. Similarly division
4380 which would imply that $\lfloor x / n \rfloor$ is a simple shift of $x$ right $p$ bits.
4383 performed by moving whole digits to the right $p$ places. In practice division by $\beta^p$ is much faster than division by $2^p$ for any $p$.
4564 This algorithm quickly reduces an input $a$ modulo an unrestricted Diminished Radix modulus $n$. Division by $2^p$ is emulated with a right
4692 $\left [ 3 \right ]$ & Prove that the ``trick'' in algorithm mp\_montgomery\_setup actually \\
4695 $\left [ 2 \right ]$ & Devise an algorithm to reduce modulo $n + k$ for small $k$ quickly. \\
4697 $\left [ 4 \right ]$ & Prove that the pseudo-code algorithm ``Diminished Radix Reduction'' \\
4729 The term $a^{2^i}$ can be found from the $i - 1$'th term by squaring the term since $\left ( a^{2^i} \right )^2$ is equal to
4813 This algorithm computes the value of $a$ raised to the power of a single digit $b$. It uses the left to right exponentiation algorithm to
4842 portion of the entire exponent. Consider the following modification to the basic left to right exponentiation algorithm.
4961 the following five $3$-bit words $b \equiv \left ( 111, 101, 011, 001, 000 \right )_{2}$. The second algorithm will break the
4962 exponent as $b \equiv \left ( 111, 101, 0, 110, 0, 100, 0 \right )_{2}$. The single digit $0$ in the second representation are where
4978 will allow the exponent $b$ to be negative which is computed as $c \equiv \left (1 / a \right )^{\vert b \vert} \mbox{(mod }d\mbox{)}$. The
5056 \end{array} \right .$ \\
5065 \hspace{3mm}8.1 $M_k \leftarrow \left ( M_k \right )^2$ (\textit{mp\_sqr}) \\
5182 \includegraphics{pics/expt_state.ps}
5378 \end{array} \right .$ \\
5933 $r$ is also divisible by $k$. The reduction pattern follows $\left < a , b \right > \rightarrow \left < b, a \mbox{ mod } b \right >$.
5983 words in every iteration that tuple $\left < a, b \right >$ decrease in magnitude until eventually $a = b$. Since both $a$ and $b$ are always
6026 This algorithm is based on the first except it removes powers of $p$ first and inside the main loop to ensure the tuple $\left < a, b \right >$
6032 to compute. The ideal choice of $p$ is two since division by two amounts to a right logical shift. Another important observation is that by
6096 After $v = 0$ occurs the variable $u$ has the greatest common divisor of the pair $\left < u, v \right >$ just after step six. The result
6188 0 \equiv x^{p-1} - 1 \equiv \left \lbrace \left (x^2 \right )^{(p-1)/2} - a^{(p-1)/2} \right \rbrace + \left ( a^{(p-1)/2} - 1 \right ) \mbox{ (mod }p\mbox{)}
6196 \left (x^2 \right )^{(p-1)/2} - a^{(p-1)/2} \equiv 0 \nonumber \\
6197 \left (x^2 \right )^{(p-1)/2} \equiv a^{(p-1)/2} \nonumber \\
6206 One of the terms on the right hand side must be zero. \textbf{QED}
6210 the Jacobi symbol $\left ( { a \over p } \right )$ is equal to the following equation.
6213 \left ( { a \over p } \right ) = \left ( { a \over p_0} \right ) \left ( { a \over p_1} \right ) \ldots \left ( { a \over p_n} \right )
6221 \item $\left ( { a \over p} \right )$ equals $-1$, $0$ or $1$.
6222 \item $\left ( { ab \over p} \right ) = \left ( { a \over p} \right )\left ( { b \over p} \right )$.
6223 \item If $a \equiv b$ then $\left ( { a \over p} \right ) = \left ( { b \over p} \right )$.
6224 \item $\left ( { 2 \over p} \right )$ equals $1$ if $p \equiv 1$ or $7 \mbox{ (mod }8\mbox{)}$. Otherwise, it equals $-1$.
6225 \item $\left ( { a \over p} \right ) \equiv \left ( { p \over a} \right ) \cdot (-1)^{(p-1)(a-1)/4}$. More specifically
6226 $\left ( { a \over p} \right ) = \left ( { p \over a} \right )$ if $p \equiv a \equiv 1 \mbox{ (mod }4\mbox{)}$.
6232 \left ( { a \over p } \right ) = \left ( {{2^k} \over p } \right ) \left ( {a' \over p} \right ) \nonumber \\
6233 = \left ( {2 \over p } \right )^k \left ( {a' \over p} \right )
6240 \left ( { a \over p } \right ) = \left ( { p \over a } \right ) \cdot (-1)^{(p-1)(a-1)/4}
6246 \left ( { a \over p } \right ) = \left ( { {p \mbox{ mod } a} \over a } \right ) \cdot (-1)^{(p-1)(a-1)/4}
6252 \left ( { a \over p } \right ) = \left ( {2 \over p } \right )^k \left ( {{p\mbox{ mod }a'} \over a'} \right ) \cdot (-1)^{(p-1)(a'-1)/4}
6255 The value of $\left ( {{p \mbox{ mod }a'} \over a'} \right )$ can be found by using the same equation recursively. The value of
6256 $\left ( {2 \over p } \right )^k$ equals $1$ if $k$ is even otherwise it equals $\left ( {2 \over p } \right )$. Using this approach the
6258 Jacobi symbol computation of $\left ( {1 \over a'} \right )$ which is simply $1$.
6266 \textbf{Output}. The Jacobi symbol $c = \left ( {a \over p } \right )$. \\
6305 input $a$. If $k$ is even than the term $\left ( { 2 \over p } \right )^k$ must always evaluate to one. If $k$ is odd than the term evaluates to one
6306 if $p_0$ is congruent to one or seven modulo eight, otherwise it evaluates to $-1$. After the the $\left ( { 2 \over p } \right )^k$ term is handled
6311 $\left ( {p' \over a'} \right )$ which is multiplied against the current Jacobi product.
6331 Line 58 through 71 determines the value of $\left ( { 2 \over p } \right )^k$. If the least significant bit of $k$ is zero than
6335 Finally, if $a1$ does not equal one the algorithm must recurse and compute $\left ( {p' \over a'} \right )$.
6350 ab \equiv a \left (a^{\Phi(p) - 1} \right ) \equiv a^{\Phi(p)} \equiv a^0 \equiv 1 \mbox{ (mod }p\mbox{)}
6363 Where $a$, $b$, $p$ and $q$ are all integers. If such a pair of integers $ \left < b, q \right >$ exist than $b$ is the multiplicative inverse of