Lines Matching +refs:ps +refs:left +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 \\
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}
569 (\textit{to the left}) are said to be in a different power of ten column. That is, the number $123$ can be described as having a $1$ in the hundreds
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.
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.}
935 the re-allocation. All that is left is to clear the newly allocated digits and return.
1096 Note on line 28 how to test for the \textbf{used} count is made on the left of the \&\& operator. In the C programming
1097 language the terms to \&\& are evaluated left to right with a boolean short-circuit if any condition fails. This is
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. \\
1289 and \textbf{a} will be left intact.
1418 3. $a.used \leftarrow \left \lbrace \begin{array}{ll}
1528 \textbf{Output}. Unsigned comparison results ($a$ to the left of $b$). \\
1543 By saying ``$a$ to the left of $b$'' it is meant that the comparison is with respect to $a$, that is if $a$ is greater than $b$ it will return
1574 \textbf{Output}. Signed Comparison Results ($a$ to the left of $b$) \\
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
1956 \hspace{6mm}2.2.1 $c.sign \leftarrow \left \lbrace \begin{array}{ll}
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
2021 operation to perform. A single precision logical shift left is sufficient to multiply a single digit by two.
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.
2190 \includegraphics{pics/sliding_window.ps}
2313 left.
2315 After the digits have been shifted appropriately at most $lg(\beta) - 1$ shifts are left to perform. Step 5 calculates the number of remaining shifts
2335 of $lg(\beta)$. Leaving only a remaining shift of $lg(\beta) - 1$ or fewer bits left. Inside the actual shift
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 \\
2590 Each row of the product is added to the result after being shifted to the left (\textit{multiplied by a power of the radix}) by the appropriate
2599 At step 5.5 the nested loop is finished and any carry that was left over should be forwarded. The carry does not have to be added to the $ix+pb$'th
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
2859 Using such points will allow the values of $f(y)$ and $g(y)$ to be independently calculated using only left shifts. For example, when $n = 2$ the
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$ \\
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 \\
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
4822 of $b$ is shifted left one bit to make the next bit down from the most signficant bit the new most significant bit. In effect each
4842 portion of the entire exponent. Consider the following modification to the basic left to right exponentiation algorithm.
4956 Similar to the previous algorithm this algorithm must have a special handler when fewer than $k$ bits are left in the exponent. While this
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
5048 2. $winsize \leftarrow \left \lbrace \begin{array}{ll}
5065 \hspace{3mm}8.1 $M_k \leftarrow \left ( M_k \right )^2$ (\textit{mp\_sqr}) \\
5117 No more windows left. Check for residual bits of exponent. \\
5159 \item The variable $bitcnt$ indicates how many bits are left in the current digit of the exponent left to be read. When it reaches zero a new digit
5169 inside this loop is to extract a new digit if no more bits are available in the current digit. If there are no bits left a new digit is
5170 read and if there are no digits left than the loop terminates.
5182 \includegraphics{pics/expt_state.ps}
5188 By step 13 there are no more digits left in the exponent. However, there may be partial bits in the window left. If $mode = 2$ then
5211 Calculating $b = 2^a$ can be performed much quicker than with any of the previous algorithms. Recall that a logical shift left $m << k$ is
5375 6. $sign \leftarrow \left \lbrace \begin{array}{ll}
5458 This is performed by shifting both to the left by enough bits to get the desired normalization.
5462 to the left (\textit{step ten}) so that it has the same number of digits as $x$. The loop on step eleven will subtract multiples of the
5506 them to the left by $lg(\beta) - 1 - k$ bits.
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 >$
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 \\
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