Lines Matching defs:If
297 evaluate to the number of characters in the string. If the string $a$ equals ``hello'' then it follows that
725 the initial integer will represent zero. If only a single digit were allocated quite a few subsequent re-allocations
730 If the memory for the digits has been successfully allocated then the rest of the members of the structure must
747 2. If the allocation failed return(\textit{MP\_MEM}) \\
766 the digits is allocated. If this fails the function returns before setting any of the other members. The \textbf{MP\_PREC}
772 heap operations later functions will have to perform in the future. If \textbf{MP\_PREC} is set correctly the slack
783 iteration the variable $a$ is substituted for a new integer that lies inclusively between $b$ and $c$. If $b > c$ occured
799 if there is an error. If the allocation fails the routine will return \textbf{MP\_MEM} to the caller to indicate there
811 a success code is returned to the calling function. If this function returns \textbf{MP\_OKAY} it is safe to assume the
825 1. If $a$ has been previously freed then return(\textit{MP\_OKAY}). \\
859 checks to see if the \textbf{dp} member is not \textbf{NULL}. If the mp\_int is a valid mp\_int then \textbf{dp} cannot be
898 5. If the allocation failed then return(\textit{MP\_MEM}). \\
928 if the \textbf{alloc} member of the mp\_int is smaller than the requested digit count. If the count is not larger than \textbf{alloc}
977 particular algorithm is useful if it is known ahead of time the approximate size of the input. If the approximation is
988 \textbf{MP\_PREC} and then adding \textbf{MP\_PREC} to the result. If the memory can be successfully allocated the
994 to \textbf{MP\_ZPOS} to achieve a default valid mp\_int state (lines 33, 34 and 35). If the function
1012 \hspace{+3mm}1.2. If initialization failed then do \\
1024 The algorithm will initialize the array of mp\_int variables one at a time. If a runtime error has been detected
1147 1. If $b.alloc < a.used$ then grow $b$ to $a.used$ digits. (\textit{mp\_grow}) \\
1166 If $b$ does not have enough room for the digits of $a$ it must first have its precision augmented via the mp\_grow
1189 The mp\_int $b$ must have enough digits to accomodate the used digits of the mp\_int $a$. If $b.alloc$ is less than
1338 2. If the copy failed return(\textit{MP\_MEM}). \\
1375 2. If the copy failed return(\textit{MP\_MEM}). \\
1376 3. If $a.used = 0$ then return(\textit{MP\_OKAY}). \\
1377 4. If $a.sign = MP\_ZPOS$ then do \\
1389 This algorithm computes the negation of an input. First it copies $a$ over $b$. If $a$ has no used digits then
1402 have to make sure that only non--zero values get a \textbf{sign} of \textbf{MP\_NEG}. If the mp\_int is zero
1442 check if the resulting digit is zero or not. If it is not then we set the \textbf{used} count to one, otherwise
1502 positions. If any leading digit of one integer is greater than a digit in the same position of another integer then obviously it must be greater.
1530 1. If $a.used > b.used$ then return(\textit{MP\_GT}) \\
1531 2. If $a.used < b.used$ then return(\textit{MP\_LT}) \\
1546 If both have the same number of digits than the actual digits themselves must be compared starting at the leading digit.
1549 the zero'th digit. If after all of the digits have been compared, no difference is found, the algorithm returns \textbf{MP\_EQ}.
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
1601 The two if statements (lines 23 and 24) perform the initial sign comparison. If the signs are not the equal then which ever
1602 has the positive sign is larger. The inputs are compared (line 32) based on magnitudes. If the signs were both
1670 3. If $c.alloc < max + 1$ then grow $c$ to hold at least $max + 1$ digits (\textit{mp\_grow}) \\
1716 Now all of the digit positions that both inputs have in common have been exhausted. If $min \ne max$ then $x$ is an alias
1771 3. If $c.alloc < max$ then grow $c$ to hold at least $max$ digits. (\textit{mp\_grow}) \\
1821 If $b$ has a smaller magnitude than $a$ then step 9 will force the carry and copy operation to propagate through the larger input $a$ into $c$. Step
1846 If $a$ has a larger magnitude than $b$ an additional loop (lines 64 through 73) is required to propagate
2031 1. If $b.alloc < a.used + 1$ then grow $b$ to hold $a.used + 1$ digits. (\textit{mp\_grow}) \\
2039 6. If $r \ne 0$ then do \\
2042 7. If $b.used < oldused - 1$ then do \\
2092 1. If $b.alloc < a.used$ then grow $b$ to hold $a.used$ digits. (\textit{mp\_grow}) \\
2093 2. If the reallocation failed return(\textit{MP\_MEM}). \\
2101 7. If $b.used < oldused - 1$ then do \\
2154 1. If $b \le 0$ then return(\textit{MP\_OKAY}). \\
2155 2. If $a.alloc < a.used + b$ then grow $a$ to at least $a.used + b$ digits. (\textit{mp\_grow}). \\
2156 3. If the reallocation failed return(\textit{MP\_MEM}). \\
2221 1. If $b \le 0$ then return. \\
2222 2. If $a.used \le b$ then do \\
2246 If the input $b$ is less than one the algorithm quickly returns without performing any work. If the \textbf{used} count is less than or equal
2283 2. If $c.alloc < c.used + \lfloor b / lg(\beta) \rfloor + 2$ then grow $c$ accordingly. \\
2284 3. If the reallocation failed return(\textit{MP\_MEM}). \\
2285 4. If $b \ge lg(\beta)$ then \\
2287 \hspace{3mm}4.2 If step 4.1 failed return(\textit{MP\_MEM}). \\
2289 6. If $d \ne 0$ then do \\
2296 \hspace{3mm}6.4 If $r > 0$ then do \\
2316 required. If it is non-zero a modified shift loop is used to calculate the remaining product.
2334 If the shift count $b$ is larger than $lg(\beta)$ then a call to mp\_lshd() is used to handle all of the multiples
2350 1. If $b \le 0$ then do \\
2356 4. If $b \ge lg(\beta)$ then do \\
2359 6. If $k \ne 0$ then do \\
2408 1. If $b \le 0$ then do \\
2411 2. If $b > a.used \cdot lg(\beta)$ then do \\
2415 4. If step 3 failed return(\textit{MP\_MEM}). \\
2431 result is set to zero. If $b$ is greater than the number of bits in $a$ then it simply copies $a$ to $c$ and returns. Otherwise, $a$
2524 1. If min$(a.used, b.used) < \delta$ then do \\
2530 3. If step 2 failed return(\textit{MP\_MEM}). \\
2537 \hspace{3mm}5.3 If $pb < 1$ then goto step 6. \\
2562 The first thing this algorithm checks for is whether a Comba multiplier can be used instead. If the minimum digit count of either
2568 is given the count of digits to read from $b$ inside the nested loop. If $pb \le 1$ then no more output digits can be produced and the algorithm
2596 5.4.1 is propagated through the nested loop. If the carry was not propagated immediately it would overflow the single precision digit
2615 If we cannot use the Comba method we proceed to setup the baseline routine. We allocate the the destination mp\_int
2698 $241 \cdot 576$ is in fact $138816$ and the procedure succeeded. If the algorithm is correct and as will be demonstrated shortly more
2705 three single precision multiplications. If the precision of the accumulator for the output digits is less then $3 \cdot (\beta - 1)^2$ then
2743 1. If $c.alloc < digs$ then grow $c$ to $digs$ digits. (\textit{mp\_grow}) \\
2744 2. If step 1 failed return(\textit{MP\_MEM}).\\
2795 To measure the benefits of the Comba method over the baseline method consider the number of operations that are required. If the
2849 If more points are required they should be of small values and powers of two such as $2^q$ and the related \textit{mirror points}
2954 2. If step 2 failed then return(\textit{MP\_MEM}). \\
3177 1. If $a.sign = b.sign$ then \\
3181 3. If min$(a.used, b.used) \ge TOOM\_MUL\_CUTOFF$ then \\
3187 \hspace{3mm}5.2 If $digs < MP\_ARRAY$ and min$(a.used, b.used) \le \delta$ then \\
3265 2. If step 1 failed return(\textit{MP\_MEM}) \\
3349 1. If $b.alloc < 2a.used + 1$ then grow $b$ to $2a.used + 1$ digits. (\textit{mp\_grow}). \\
3350 2. If step 1 failed return(\textit{MP\_MEM}). \\
3389 products are to be doubled. If we had added the previous carry in we would be doubling too much. Next we perform an
3426 If the asymptotic times of Karatsuba squaring and multiplication are the same, why not simply use the multiplication algorithm
3432 The 100 digit halves will not be squared using Karatsuba, but instead using the faster Comba based squaring algorithm. If Karatsuba multiplication
3444 2. If any of the initializations on step 1 failed return(\textit{MP\_MEM}). \\
3524 redirected to the error trap higher up. If the algorithm completes without error the error code is set to \textbf{MP\_OKAY} and
3541 1. If $a.used \ge TOOM\_SQR\_CUTOFF$ then \\
3547 \hspace{3mm}3.2 If $digs < MP\_ARRAY$ and $a.used \le \delta$ then \\
3561 This algorithm computes the square of the input using one of four different algorithms. If the input is very large and has at least
3562 \textbf{TOOM\_SQR\_CUTOFF} or \textbf{KARATSUBA\_SQR\_CUTOFF} digits then either the Toom-Cook or the Karatsuba Squaring algorithm is used. If
3644 of two fixed point numbers. Using fixed point arithmetic, division can be easily approximated by multiplying by the reciprocal. If $2^q$ is
3652 The precision of the division is proportional to the value of $q$. If the divisor $b$ is used frequently as is the case with
3686 Using the fixed point representation a modular reduction can be performed with $3n^2$ single precision multiplications. If that were the best
3695 express this is by re-writing $a$ as two parts. If $a' \equiv a \mbox{ (mod }b^m\mbox{)}$ and $a'' = a - a'$ then
3708 exponent on the divisor when added to the amount $q_0$ was shifted by equals $2m$. If the optimization had not been performed the divisor
3733 multiplications. If the number of digits in the modulus $m$ is far less than $\beta$ a full product is not required for the algorithm to work properly.
3742 multiple of the modulus, that is $0 \le a - b \cdot \lfloor (q_0 \cdot \mu) / \beta^{m+1} \rfloor < 3b$. If $b$ is $m$ digits than the
3777 8. If $a < 0$ then (\textit{mp\_cmp\_d}) \\
3799 First the modulus $b$ is assumed to be positive and greater than one. If the modulus were less than or equal to one than subtracting
3801 for the quotient to have enough precision. If $a$ is the product of two numbers that were already reduced modulo $b$, this will not be a problem.
3815 The while loop at step 9 will subtract $b$ until the residue is less than $b$. If the algorithm is performed correctly this step is
3879 \textbf{Fact 2.} If $x$ is even then performing a division by two in $\Z$ is congruent to $x \cdot 2^{-1} \mbox{ (mod }n\mbox{)}$. Actually
3894 \hspace{3mm}1.1 If $x$ is odd then \\
3908 final result of the Montgomery algorithm. If $k > lg(n)$ and $0 \le x < n^2$ then the final result is limited to
3950 \hspace{3mm}1.1 If the $t$'th bit of $x$ is one then \\
4014 The value $\mu n \beta^t$ is a multiple of the modulus $n$ meaning that it will not change the residue. If the first digit of
4064 2. If $digs < MP\_ARRAY$ and $m.used < \delta$ then \\
4068 3. If $x.alloc < digs$ then grow $x$ to $digs$ digits. \\
4087 7. If $x \ge n$ then \\
4176 10. If $x \ge n$ then \\
4237 2. If $b$ is even return(\textit{MP\_VAL}) \\
4301 5. If $x \ge (n - k)$ then \\
4313 This algorithm will reduce $x$ modulo $n - k$ and return the residue. If $0 \le x < (n - k)^2$ then the algorithm will loop almost always
4382 However, there is one operation related to division of power of twos that is even faster than this. If $n = \beta^p$ then the division may be
4412 2. If $x.alloc < 2m$ then grow $x$ to $2m$ digits. \\
4422 8. If $x \ge n$ then \\
4508 1. If $n.used < 2$ then return($0$). \\
4510 \hspace{3mm}2.1 If $n_{ix} \ne \beta - 1$ return($0$). \\
4521 in the mp\_int. Step 2 tests all but the first digit to see if they are equal to $\beta - 1$. If the algorithm manages to get to
4553 \hspace{3mm}2.5 If $a \ge n$ then do \\
4624 If either condition is true than there is a power of two $2^p$ such that $0 < 2^p - n < \beta$. If the input is only
4637 1. If $n.used = 0$ then return($0$). \\
4638 2. If $n.used = 1$ then return($1$). \\
4641 \hspace{3mm}4.1 If the ($x \mbox{ mod }lg(\beta)$)'th bit of the $\lfloor x / lg(\beta) \rfloor$ of $n$ is zero then return($0$). \\
4717 significant bit. If $b$ is a $k$-bit integer than the following equation is true.
4800 \hspace{3mm}3.2 If $b$ AND $2^{lg(\beta) - 1} \ne 0$ then \\
4866 The squaring on step 2.1 can be calculated by squaring the value $c$ successively $k$ times. If the values of $a^g$ for $0 < g < 2^k$ have been
4941 \hspace{3mm}2.1 If the $i$'th bit of $b$ is a zero then \\
4979 value of $(1/a) \mbox{ mod }c$ is computed using the modular inverse (\textit{see \ref{sec;modinv}}). If no inverse exists the algorithm
4990 1. If $c.sign = MP\_NEG$ return(\textit{MP\_VAL}). \\
4991 2. If $b.sign = MP\_NEG$ then \\
5019 In order to keep the algorithms in a known state the first step on line 29 is to reject any negative modulus as input. If the exponent is
5024 If the exponent is positive the algorithm resumes the exponentiation. Line 77 determines if the modulus is of the restricted Diminished Radix
5025 form. If it is not line 70 attempts to determine if it is of a unrestricted Diminished Radix form. The integer $dr$ will take on one
5076 \hspace{3mm}12.2 If $bitcnt = 0$ then do \\
5077 \hspace{6mm}12.2.1 If $digidx = -1$ goto step 13. \\
5107 \hspace{3mm}12.10 If $bitcpy = winsize$ then do \\
5118 13. If $mode = 2$ and $bitcpy > 0$ then do \\
5123 \hspace{6mm}13.1.4 If $bitbuf$ AND $2^{winsize} \ne 0$ then do \\
5155 are read and a single squaring is performed. If a non-zero bit is read a new window is created.
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
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
5223 2. If $a.alloc < \lfloor b / lg(\beta) \rfloor + 1$ then grow $a$ appropriately. \\
5365 1. If $b = 0$ return(\textit{MP\_VAL}). \\
5366 2. If $\vert a \vert < \vert b \vert$ then do \\
5410 \hspace{3mm}13.1 If $i > x.used$ then jump to the next iteration of this loop. \\
5411 \hspace{3mm}13.2 If $x_{i} = y_{t}$ then \\
5426 \hspace{6mm}13.5.6 If $\vert t1 \vert > \vert t2 \vert$ then goto step 13.5. \\
5430 \hspace{3mm}13.9 If $x.sign = MP\_NEG$ then \\
5452 First the divisor $b$ must be non-zero which is enforced in step one. If the divisor is larger than the dividend than the quotient is implicitly
5621 1. If $b = 0$ then return(\textit{MP\_VAL}).\\
5622 2. If $b = 3$ then use algorithm mp\_div\_3 instead. \\
5629 \hspace{3mm}7.2 If $\hat w \ge b$ then \\
5650 If the divisor $b$ is equal to three a variant of this algorithm is used which is called mp\_div\_3. It replaces the division by three with
5691 1. If $b$ is even and $a.sign = MP\_NEG$ return(\textit{MP\_VAL}). \\
5703 \hspace{3mm}5.8 If t$1 \ne $ t$2$ then goto step 5. \\
5706 \hspace{3mm}6.2 If t$2 > a$ then \\
5750 2. If $b \le 0$ return(\textit{MP\_OKAY}) \\
5824 1. If $r < 2$ or $r > 64$ return(\textit{MP\_VAL}). \\
5826 3. If $str_0 =$ ``-'' then do \\
5834 \hspace{3mm}6.2 If $str_{iy}$ is not in the map or $y \ge r$ then goto step 7. \\
5837 7. If $a \ne 0$ then $a.sign \leftarrow sign$ \\
5869 1. If $r < 2$ or $r > 64$ return(\textit{MP\_VAL}). \\
5870 2. If $a = 0$ then $str = $ ``$0$'' and return(\textit{MP\_OKAY}). \\
5881 7. If $str_0 = $``$-$'' then \\
6048 1. If $a = 0$ then \\
6051 2. If $b = 0$ then \\
6065 \hspace{3mm}8.1 If $\vert u \vert > \vert v \vert$ then \\
6083 The first two steps handle the cases where either one of or both inputs are zero. If either input is zero the greatest common divisor is the
6084 largest input or zero if they are both zero. If the inputs are not trivial than $u$ and $v$ are assigned the absolute values of
6127 The least common multiple arises often in coding theory as well as number theory. If two functions have periods of $a$ and $b$ respectively they will
6192 Whether equation \ref{eqn:root} has a solution or not equation \ref{eqn:rooti} is always true. If $a^{(p-1)/2} - 1 \equiv 0 \mbox{ (mod }p\mbox{)}$
6201 As a result there must be a solution to the quadratic equation and in turn $a$ must be a quadratic residue. If $a$ does not divide $p$ and $a$
6209 The Jacobi symbol is a generalization of the Legendre function for any odd non prime moduli $p$ greater than 2. If $p = \prod_{i=0}^n p_i$ then
6223 \item If $a \equiv b$ then $\left ( { a \over p} \right ) = \left ( { b \over p} \right )$.
6268 1. If $a = 0$ then \\
6271 2. If $a = 1$ then \\
6279 6. If $k \equiv 0 \mbox{ (mod }2\mbox{)}$ then \\
6283 \hspace{3mm}7.2 If $r = 1$ or $r = 7$ then \\
6287 8. If $p_0 \equiv a'_0 \equiv 3 \mbox{ (mod }4\mbox{)}$ then \\
6289 9. If $a' \ne 1$ then \\
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
6323 The two simple cases of $a = 0$ and $a = 1$ are handled at the very beginning to simplify the algorithm. If the input is non-trivial the algorithm
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
6346 The simplest approach is to compute the algebraic inverse of the input. That is to compute $b \equiv a^{\Phi(p) - 1}$. If $\Phi(p)$ is the
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
6378 1. If $b \le 0$ then return(\textit{MP\_VAL}). \\
6379 2. If $b_0 \equiv 1 \mbox{ (mod }2\mbox{)}$ then use algorithm fast\_mp\_invmod. \\
6381 4. If $x_0 \equiv y_0 \equiv 0 \mbox{ (mod }2\mbox{)}$ then return(\textit{MP\_VAL}). \\
6385 \hspace{3mm}6.2 If ($A.used > 0$ and $A_0 \equiv 1 \mbox{ (mod }2\mbox{)}$) or ($B.used > 0$ and $B_0 \equiv 1 \mbox{ (mod }2\mbox{)}$) then \\
6392 \hspace{3mm}7.2 If ($C.used > 0$ and $C_0 \equiv 1 \mbox{ (mod }2\mbox{)}$) or ($D.used > 0$ and $D_0 \equiv 1 \mbox{ (mod }2\mbox{)}$) then \\
6397 8. If $u \ge v$ then \\
6405 10. If $u \ne 0$ goto step 6. \\
6406 11. If $v \ne 1$ return(\textit{MP\_VAL}). \\
6423 If $b \le 0$ than the modulus is invalid and MP\_VAL is returned. Similarly if both $a$ and $b$ are even then there cannot be a multiplicative
6433 If $v$, the greatest common divisor of $a$ and $b$ is not equal to one then the algorithm will report an error as no inverse exists. Otherwise, $C$
6435 within $1 \le a^{-1} < b$. Step numbers twelve and thirteen adjust the inverse until it is in range. If the original input $a$ is within $0 < a < p$
6468 Trial division means to attempt to evenly divide a candidate integer by small prime integers. If the candidate can be evenly divided it obviously
6495 \hspace{3mm}1.2 If $d = 0$ then \\
6535 If $n$ is composite then any given base $a$ does not have to have a period which divides $n - 1$. In which case
6550 2. If $t = b$ then \\
6575 value must be equal to $-1$. The squarings are stopped as soon as $-1$ is observed. If the value of $1$ is observed first it means that
6593 6. If $y \nequiv \pm 1$ then \\
6597 \hspace{6mm}6.2.2 If $y = 1$ then goto step 8. \\
6599 \hspace{3mm}6.3 If $y \nequiv a'$ goto step 8. \\
6612 If the value $y \equiv b^r$ is congruent to $\pm 1$ then the algorithm cannot prove if $a$ is composite or not. Otherwise, the algorithm will
6613 square $y$ upto $s - 1$ times stopping only when $y \equiv -1$. If $y^2 \equiv 1$ and $y \nequiv \pm 1$ then the algorithm can report that $a$
6614 is provably composite. If the algorithm performs $s - 1$ squarings and $y \nequiv -1$ then $a$ is provably composite. If $a$ is not provably