Lines Matching refs:algorithm
209 rendering any protocol based on the algorithm insecure. Multiple precision algorithms solve this v…
213 primitives. Faster modular reduction and exponentiation algorithms such as Barrett's algorithm, wh…
235 precision algorithm would augment the precision of the destination to accomodate the result while a…
259 In most cases how an algorithm is explained and how it is actually implemented are two very differe…
260 example, the Handbook of Applied Cryptography (\textit{HAC}), algorithm 14.7 on page 594, gives a r…
261 algorithm for performing multiple precision integer addition. However, the description lacks any d…
263 as the text would lead people to believe. Similarly the division routine (\textit{algorithm 14.20,…
277 by the actual C source code that implements the algorithm. The pseudo-code can be used to implemen…
278 algorithm in other programming languages as the reader sees fit.
294 synonymous. When an algorithm is specified to accept an mp\_int variable it is assumed the various…
300 …ssions more generic algorithms are presented to help the reader understand the final algorithm used
301 to solve a given problem. When an algorithm is described as accepting an integer input it is assum…
305 precision algorithm to solve the same problem.
315 Within the source code that will be presented for each algorithm, the data type \textbf{mp\_digit} …
332 Within the algorithm descriptions all variables are assumed to be scalars of either single or doubl…
359 result small constant factors in the work effort will make an observable difference in algorithm ef…
408 are also designed to be easy but will require a program or algorithm to be implemented to arrive at…
413 involve devising a new algorithm or implementing a variation of another algorithm previously presen…
442 …ten entirely in ISO C, considerable care has been taken to optimize the algorithm implementations …
450 algorithm \textbf{mp\_mul()} which will automatically use Toom--Cook, Karatsuba, Comba or baseline …
461 integer arithmetic. To this end the source code has been given quite a few comments and algorithm …
532 before implementing a modular exponentiation algorithm one would implement a modular reduction algo…
553 …er discusses the core algorithms of the library which are the dependents for every other algorithm.
730 structure are set to valid values. The mp\_init algorithm will perform such an action.
799 …rough @31,sign@) to their respective default states. At this point the algorithm has succeeded and
805 returned to the application's memory pool with the mp\_clear algorithm.
829 This algorithm accomplishes two goals. First, it clears the digits and the other mp\_int members. …
833 The logic behind the algorithm is extended by marking cleared mp\_int structures so that subsequent…
834 algorithm will not try to free the memory multiple times. Cleared mp\_ints are detectable by havin…
837 …p\_int has been cleared the mp\_int structure is no longer in a valid state for any other algorithm
842 The algorithm only operates on the mp\_int if it hasn't been previously cleared. The if statement …
869 must be re-sized appropriately to accomodate the result. The mp\_grow algorithm will provide this …
922 of input mp\_ints to a given algorithm. The purpose of algorithm mp\_init\_size is similar to mp\_…
950 This algorithm will initialize an mp\_int structure $a$ like algorithm mp\_init with the exception …
955 Like algorithm mp\_init, the mp\_int structure is initialized to a default state representing the i…
956 particular algorithm is useful if it is known ahead of time the approximate size of the input. If …
974 The purpose of algorithm mp\_init\_multi is to initialize a variable length array of mp\_int struct…
998 The algorithm will initialize the array of mp\_int variables one at a time. If a runtime error has…
1011 the algorithm can backtrack and free the previously initialized structures (lines @27,if@ to @46,}@…
1031 The mp\_clamp algorithm is designed to solve this very problem. It will trim high-order zeros by d…
1054 As can be expected this algorithm is very simple. The loop on step one is expected to iterate only…
1075 $\left [ 1 \right ]$ & Discuss the relevance of the algorithm mp\_clamp. What does it prevent? \\
1077 $\left [ 1 \right ]$ & Give an example of when the algorithm mp\_init\_copy might be useful. \\
1091 level basis of the entire library. While these algorithm are relatively trivial it is important to…
1102 value as the mp\_int it was copied from. The mp\_copy algorithm provides this functionality.
1126 This algorithm copies the mp\_int $a$ such that upon succesful termination of the algorithm the mp\…
1131 algorithm. The digits of $a$ are copied over the digits of $b$ and any excess digits of $b$ are se…
1135 \textbf{Remark.} This algorithm also introduces a new idiosyncrasy that will be used throughout th…
1137 step one of the mp\_copy algorithm the return of mp\_grow is not explicitly checked to ensure it su…
1138 limited so it is assumed that if a algorithm fails it will clear all temporarily allocated mp\_ints…
1144 Occasionally a dependent algorithm may copy an mp\_int effectively into itself such as when the inp…
1149 $a.used$ the algorithm mp\_grow is used to augment the precision of $b$ (lines @29,alloc@ to @33,}@…
1189 The second reason is that pointer aliases often can make an algorithm simpler to read. Consider th…
1217 mp\_init\_copy algorithm has been designed to help perform this task.
1236 This algorithm will initialize an mp\_int variable and copy another previously initialized mp\_int …
1237 such this algorithm will perform two operations in one step.
1246 …ult state is a common step in many algorithms. The mp\_zero algorithm will be the algorithm used …
1267 This algorithm simply resets a mp\_int to the default state.
1276 …ation of an integer, calculating the absolute value is trivial. The mp\_abs algorithm will compute
1297 This algorithm computes the absolute of an mp\_int input. First it copies $a$ over $b$. This is a…
1298 algorithm where the check in mp\_copy that determines if the source and destination are equal prove…
1304 This fairly trivial algorithm first eliminates non--required duplications (line @27,a != b@) and th…
1308 …tation of an integer, calculating the negation is also trivial. The mp\_neg algorithm will compute
1333 This algorithm computes the negation of an input. First it copies $a$ over $b$. If $a$ has no use…
1334 the algorithm returns immediately. Otherwise it flips the sign flag and stores the result in $b$. …
1335 …hen it must be positive by definition. Had step three been omitted then the algorithm would return
1346 …t to a relatively small value such as $1$ or $2$. For these cases the mp\_set algorithm is useful.
1368 This algorithm sets a mp\_int to a small single digit value. Step number 1 ensures that the intege…
1386 To overcome the limitations of the mp\_set algorithm the mp\_set\_int algorithm is ideal. It accep…
1410 The algorithm performs eight iterations of a simple loop where in each iteration four bits from the…
1428 Comparing a multiple precision integer is performed with the exact same algorithm used to compare t…
1478 …after all of the digits have been compared, no difference is found, the algorithm returns \textbf{…
1491 comparison a trivial signed comparison algorithm can be written.
1527 $\left [ 2 \right ]$ & Modify algorithm mp\_set\_int to accept as input a variable length array of …
1529 $\left [ 3 \right ]$ & Give the probability that algorithm mp\_cmp\_mag will have to compare $k$ di…
1569 An unsigned addition of multiple precision integers is performed with the same long-hand algorithm …
1570 …and propagate the resulting carry upwards. Since this is a lower level algorithm the name will ha…
1617 This algorithm is loosely based on algorithm 14.7 of HAC \cite[pp. 594]{HAC} but has been extended …
1618 …incidentally the description of algorithm A in Knuth \cite[pp. 266]{TAOCPV2} shares the same defic…
1662 The low level unsigned subtraction algorithm is very similar to the low level unsigned addition alg…
1663 unsigned subtraction algorithm requires the result to be positive. That is when computing $a - b$ …
1664 be met for this algorithm to function properly. Keep in mind this low level algorithm is not meant…
1665 This algorithm as will be shown can be used to create functional signed addition and subtraction al…
1669 For this algorithm a new variable is required to make the description simpler. Recall from section…
1671 this algorithm we will assume that the variable $\gamma$ represents the number of bits available in…
1713 This algorithm performs the unsigned subtraction of two mp\_int variables under the restriction tha…
1714 …he condition that $\vert a \vert \ge \vert b \vert$ must be met for the algorithm to function corr…
1715 algorithm is loosely based on algorithm 14.9 \cite[pp. 595]{HAC} and is similar to algorithm S in \…
1716 of the algorithm s\_mp\_add both other references lack discussion concerning various practical deta…
1718 The initial sorting of the inputs is trivial in this algorithm since $a$ is guaranteed to have at l…
1720 most $max$ digits in length as opposed to $max + 1$. Similar to the addition algorithm the \textbf…
1723 …at begins on step seven is essentially the same as the addition loop of algorithm s\_mp\_add excep…
1745 within this algorithm. The aliases $tmpa$, $tmpb$ and $tmpc$ are initialized
1761 …btraction algorithms have been established an effective high level signed addition algorithm can be
1762 established. This high level addition algorithm will be what other algorithms and developers will …
1793 This algorithm performs the signed addition of two mp\_int variables. There is no reference algori…
1794 …{TAOCPV2} or \cite{HAC} since they both only provide unsigned operations. The algorithm is fairly
1826 forwarded to step three to check for errors. This simplifies the description of the algorithm cons…
1830 …clamp function is used at the end to trim excess digits. The mp\_clamp algorithm will set the \te…
1833 For example, consider performing $-a + a$ with algorithm mp\_add. By the description of the algori…
1834 …n is set first then the unsigned addition is performed the subsequent usage of algorithm mp\_clamp
1835 within algorithm s\_mp\_add will force $-0$ to become $0$.
1839 The source code follows the algorithm fairly closely. The most notable new source code addition is…
1840 is used to pass result of the unsigned operations forward. Unlike in the algorithm, the variable $…
1841 … and returning the constant \textbf{MP\_OKAY}. The observation is this algorithm will succeed or …
1845 The high level signed subtraction algorithm is essentially the same as the high level signed additi…
1875 This algorithm performs the signed subtraction of two inputs. Similar to algorithm mp\_add there i…
1876 \cite{HAC}. Also this algorithm is restricted by algorithm s\_mp\_sub. Chart \ref{fig:SubChart} l…
1902 Similar to the case of algorithm mp\_add the \textbf{sign} is set first before the unsigned additio…
1903 algorithm from producing $-a - -a = -0$ as a result.
1907 Much like the implementation of algorithm mp\_add the variable $res$ is used to catch the return co…
1957 This algorithm will quickly multiply a mp\_int by two provided $\beta$ is a power of two. Neither …
1958 an algorithm despite the fact it arises often in other algorithms. The algorithm is setup much lik…
2012 This algorithm will divide an mp\_int by two using logical shifts to the right. Like mp\_mul\_2 it…
2013 … the basis of the algorithm. Unlike mp\_mul\_2 the shift operations work from the leading digit t…
2067 This algorithm multiplies an mp\_int by the $b$'th power of $x$. This is equivalent to multiplying…
2070 …inputs are often still required. Algorithm mp\_lshd (\textit{and similarly algorithm mp\_rshd}) is
2071 typically used on values where the original value is no longer required. The algorithm will return…
2072 $b \le 0$ since the rest of algorithm is only valid when $b > 0$.
2124 This algorithm divides the input in place by the $b$'th power of $x$. It is analogous to dividing …
2125 it does not require single precision division. This algorithm does not actually return an error co…
2127 If the input $b$ is less than one the algorithm quickly returns without performing any work. If th…
2130 …s have been handled the sliding window is setup. Much like the case of algorithm mp\_lshd a slidi…
2145 example, to quickly multiply by $2^k$ for any $k$ without using a full multiplier algorithm would p…
2184 This algorithm multiplies $a$ by $2^b$ and stores the result in $c$. The algorithm uses algorithm …
2187 First the algorithm will multiply $a$ by $x^{\lfloor b / lg(\beta) \rfloor}$ which will ensure that…
2193 Essentially the loop is a generic version of algorithm mp\_mul\_2 designed to handle any shift coun…
2196 This algorithm is loosely measured as a $O(2n)$ algorithm which means that if the input is $n$-digi…
2197 …mplete. It is possible to optimize this algorithm down to a $O(n)$ algorithm at a cost of making …
2247 This algorithm will divide an input $a$ by $2^b$ and produce the quotient and remainder. The algor…
2248 mp\_mul\_2d by first using whole digit shifts then single precision shifts. This algorithm will al…
2249 by using algorithm mp\_mod\_2d.
2253 The implementation of algorithm mp\_div\_2d is slightly different than the algorithm specifies. Th…
2263 The last algorithm in the series of polynomial basis power of two algorithms is calculating the rem…
2264 algorithm benefits from the fact that in twos complement arithmetic $a \mbox{ (mod }2^b\mbox{)}$ is…
2296 This algorithm will quickly calculate the value of $a \mbox{ (mod }2^b\mbox{)}$. First if $b$ is l…
2312 $\left [ 3 \right ] $ & Devise an algorithm that performs $a \cdot 2^b$ for generic values of $b$ \\
2315 $\left [ 3 \right ] $ & Devise an efficient algorithm to multiply by small low hamming \\
2319 $\left [ 2 \right ] $ & Modify the preceding algorithm to handle values of the form \\
2323 & algorithm to multiply two integers in roughly $O(2n^2)$ time for \\
2327 $\left [ 5 \right ] $ & Improve the previous algorithm to have a working time of at most \\
2354 overall algorithm used is essentially the same. Only ``recently'' have faster algorithms been stud…
2355 1962. This algorithm can multiply two numbers with considerably fewer single precision multiplicat…
2363 algorithm that school children are taught. The algorithm is considered an $O(n^2)$ algorithm since…
2367 The ``baseline multiplication'' algorithm is designed to act as the ``catch-all'' algorithm, only t…
2368 used. This algorithm does not use any particularly interesting optimizations and should ideally be…
2369 facet of this algorithm, is that it has been modified to only produce a certain amount of output di…
2371 will be at most $n + m$ digits. Therefore, this algorithm can be reduced to a full multiplier by h…
2386 …c = \vert a \vert \cdot \vert b \vert$ by the Comba method (\textit{see algorithm~\ref{fig:COMBAMU…
2417 This algorithm computes the unsigned product of two inputs $a$ and $b$, limited to an output precis…
2419 algorithm. The algorithm is loosely based on algorithm 14.12 from \cite[pp. 595]{HAC} and is simil…
2423 The first thing this algorithm checks for is whether a Comba multiplier can be used instead. If t…
2424 …hod may be used instead. After the Comba method is ruled out, the baseline algorithm begins. A
2425 …$ is used to hold the intermediate result of the product. This allows the algorithm to be used to
2429 …inside the nested loop. If $pb \le 1$ then no more output digits can be produced and the algorithm
2456 double precision result. The step is somewhat optimized from a long-hand multiplication algorithm …
2497 At the heart of the Comba technique is once again the long-hand algorithm. Except in this case a s…
2498 twist is placed on how the columns of the result are produced. In the standard long-hand algorithm…
2499 are produced then added together to form the final result. In the baseline algorithm the columns a…
2502 In the Comba algorithm the columns of the result are produced entirely independently of each other.…
2504 …op to reduce the amount of work requiored. Succintly the first step of the algorithm is to compute
2554 With that algorithm and $k = 5$ and $\beta = 10$ the following vector is produced $\vec x= \left < …
2555 $241 \cdot 576$ is in fact $138816$ and the procedure succeeded. If the algorithm is correct and a…
2556 efficient than the baseline algorithm why not simply always use this algorithm?
2560 …s obstacle is if the carry is lost, due to lack of precision before the algorithm has a chance to …
2566 …product is known as the ``column weight'' and strictly governs when the algorithm can be used. Re…
2633 This algorithm performs the unsigned multiplication of $a$ and $b$ using the Comba method limited t…
2635 The outer loop of this algorithm is more complicated than that of the baseline multiplier. This is…
2655 the speed increase is actually much more. With $O(n)$ space the algorithm can be reduced to $O(pn …
2669 slower and also often doesn't exist. This new algorithm only performs two reads per iteration unde…
2714 As a general rule of the algorithm when the inputs are split into $n$ parts each there are $2n - 1$…
2715 …hat have $n$ times fewer digits than the inputs. The asymptotic running time of this algorithm is
2739 of solving for the 2001 terms of $W(x)$ will certainly consume any savings the algorithm could offe…
2781 this algorithm recursively, the work factor becomes $O(n^{lg(3)})$ which is substantially better th…
2795 making it an ideal algorithm to speed up certain public key cryptosystems such as RSA and Diffie-He…
2841 This algorithm computes the unsigned product of two inputs using the Karatsuba multiplication algor…
2852 of an additional temporary variable, the algorithm can avoid an addition memory allocation operatio…
2868 The first algebraic portion of the algorithm is to split the two inputs into their halves. However…
2876 When line @152,err@ is reached, the algorithm has completed succesfully. The ``error status'' vari…
2880 Toom-Cook $3$-Way \cite{TOOM} multiplication is essentially the polynomial basis algorithm for $n =…
2899 the algorithm can be faster than a baseline multiplication. However, the greater complexity of thi…
2970 This algorithm computes the product of two mp\_int variables $a$ and $b$ using the Toom-Cook approa…
2971 algorithm has a lower asymptotic running time of approximately $O(n^{1.464})$ but at an obvious cos…
2980 $f(y)$ and $g(y)$ which significantly speeds up the algorithm.
2992 The first obvious thing to note is that this algorithm is complicated. The complexity is worth it …
2995 algorithm is not practical as Karatsuba has a much lower cutoff point.
3009 …been unsigned multiplications which leaves only a signed multiplication algorithm to be establishe…
3024 \hspace{3mm}3.1 $c \leftarrow a \cdot b$ using algorithm mp\_toom\_mul \\
3026 \hspace{3mm}4.1 $c \leftarrow a \cdot b$ using algorithm mp\_karatsuba\_mul \\
3030 \hspace{6mm}5.2.1 $c \leftarrow a \cdot b \mbox{ (mod }\beta^{digs}\mbox{)}$ using algorithm fast\…
3032 \hspace{6mm}5.3.1 $c \leftarrow a \cdot b \mbox{ (mod }\beta^{digs}\mbox{)}$ using algorithm s\_mp…
3043 This algorithm performs the signed multiplication of two inputs. It will make use of any of the th…
3044 …te size. The \textbf{sign} of the result is not set until the end of the algorithm since algorithm
3091 The baseline squaring algorithm is meant to be a catch-all squaring algorithm. It will handle any …
3133 This algorithm computes the square of an input using the three observations on squaring. It is bas…
3134 \cite[pp.596-597]{HAC}. Similar to algorithm s\_mp\_mul\_digs, a temporary mp\_int is allocated to…
3137 The outer loop of this algorithm begins on step 4. It is best to think of the outer loop as walking…
3142 very algorithm. The product $a_{ix}a_{iy}$ will lie in the range $0 \le x \le \beta^2 - 2\beta + 1…
3145 Similar to algorithm s\_mp\_mul\_digs, after every pass of the inner loop, the destination is corre…
3146 …o far. This involves expensive carry propagation which will be eliminated in the next algorithm.
3156 get progressively shorter as the algorithm proceeds. This is what leads to the savings compared to…
3217 This algorithm computes the square of an input using the Comba technique. It is designed to be a r…
3219 This algorithm is very similar to the Comba multiplier except with a few key differences we shall m…
3237 The same algorithm that performs optimal polynomial basis multiplication can be used to perform pol…
3251 Karatsuba multiplication, this algorithm can be applied recursively on the input and will achieve a…
3254 …aratsuba squaring and multiplication are the same, why not simply use the multiplication algorithm
3260 …ared using Karatsuba, but instead using the faster Comba based squaring algorithm. If Karatsuba m…
3303 This algorithm computes the square of an input $a$ using the Karatsuba technique. This algorithm i…
3304 multiplication algorithm with the exception that the three half-size multiplications have been repl…
3337 This implementation is largely based on the implementation of algorithm mp\_karatsuba\_mul. It use…
3347 redirected to the error trap higher up. If the algorithm completes without error the error code is…
3351 The Toom-Cook squaring algorithm mp\_toom\_sqr is heavily based on the algorithm mp\_toom\_mul with…
3352 …ve relations. The reader is encouraged to read the description of the latter algorithm and try to
3353 derive their own Toom-Cook squaring algorithm.
3365 \hspace{3mm}1.1 $b \leftarrow a^2$ using algorithm mp\_toom\_sqr \\
3367 \hspace{3mm}2.1 $b \leftarrow a^2$ using algorithm mp\_karatsuba\_sqr \\
3371 \hspace{6mm}3.2.1 $b \leftarrow a^2$ using algorithm fast\_s\_mp\_sqr. \\
3373 \hspace{6mm}3.3.1 $b \leftarrow a^2$ using algorithm s\_mp\_sqr. \\
3384 This algorithm computes the square of the input using one of four different algorithms. If the inp…
3385 …UBA\_SQR\_CUTOFF} digits then either the Toom-Cook or the Karatsuba Squaring algorithm is used. If
3386 …e polynomial basis algorithms should be used then either the Comba or baseline algorithm is used.
3392 $\left [ 3 \right ] $ & Devise an efficient algorithm for selection of the radix point to handle in…
3438 The Barrett reduction algorithm \cite{BARRETT} was inspired by fast division algorithms which multi…
3448 It would take another common optimization to optimize the algorithm.
3492 Provided that $2^q \ge a$ this algorithm will produce a quotient that is either exactly correct or …
3496 Let $n$ represent the number of digits in $b$. This algorithm requires approximately $2n^2$ single…
3546 So far the reduction algorithm has been optimized from $3m^2$ single precision multiplications down…
3547 it stands now the algorithm is already fairly fast compared to a full integer division algorithm. …
3552 …lus $m$ is far less than $\beta$ a full product is not required for the algorithm to work properly…
3560 …een calculated it is used to reduce the input. As previously noted the algorithm is not exact and…
3566 $O(m^2)$ multiplication algorithm only the lower $m+1$ digits of the product have to be computed. …
3570 With both optimizations in place the algorithm is the algorithm Barrett proposed. It requires $m^2…
3614 This algorithm will reduce the input $a$ modulo $b$ in place using the Barrett algorithm. It is lo…
3615 \cite[pp. 602]{HAC} which is based on the paper from Paul Barrett \cite{BARRETT}. The algorithm h…
3616 be adhered to for the algorithm to work.
3621 Technically the algorithm will still work if $a \ge b^2$ but it will take much longer to finish. T…
3622 algorithm and is assumed to be calculated and stored before the algorithm is used.
3624 …uotient on step 3 must only produce digits at or above the $m-1$'th position. An algorithm called
3625 …igs$ which has not been presented is used to accomplish this task. The algorithm is based on $s\_…
3626 …vel of precision it starts at a given level of precision. This optimal algorithm can only be used…
3634 The while loop at step 9 will subtract $b$ until the residue is less than $b$. If the algorithm is…
3641 in the modulus. In the source code this is evaluated on lines @36,if@ to @44,}@ where algorithm s\…
3645 In order to use algorithm mp\_reduce the value of $\mu$ must be calculated in advance. Ideally thi…
3646 future use so that the Barrett algorithm can be used without delay.
3667 This algorithm computes the reciprocal $\mu$ required for Barrett reduction. First $\beta^{2m}$ is…
3672 …procal $\mu$ required by Barrett reduction. Note the extended usage of algorithm mp\_div where th…
3677 …footnote{Thanks to Niels Ferguson for his insightful explanation of the algorithm.} \cite{MONT} is…
3679 residue times a constant. However, as perplexing as this may sound the algorithm is relatively sim…
3682 … represent the quantity of which the residue is sought. Similar to the Barrett algorithm the input
3692 From these two simple facts the following simple algorithm can be derived.
3714 The algorithm reduces the input one bit at a time using the two congruencies stated previously. In…
3717 final result of the Montgomery algorithm. If $k > lg(n)$ and $0 \le x < n^2$ then the final result…
3743 the algorithm $r = 178$ is congruent to the value of $2^{-9} \cdot 5555 \mbox{ (mod }257\mbox{)}$. …
3746 Let $k = \lfloor lg(n) \rfloor + 1$ represent the number of bits in $n$. The current algorithm req…
3747 and $k^2$ single precision additions. At this rate the algorithm is most certainly slower than Bar…
3748 Fortunately there exists an alternative representation of the algorithm.
3769 This algorithm is equivalent since $2^tn$ is a multiple of $n$ and the lower $k$ bits of $x$ are ze…
3796 Figure~\ref{fig:MONT2} demonstrates the modified algorithm reducing $x = 5555$ modulo $n = 257$ wit…
3797 With this algorithm a single shift right at the end is the only right shift required to reduce the …
3803 previous algorithm re-written to compute the Montgomery reduction in this new fashion.
3836 extensively in this algorithm and should be precomputed. Let $\rho$ represent the negative of the …
3856 the algorithm. To get the true residue the value must be multiplied by $\beta^k$. In this case $\…
3860 The baseline Montgomery reduction algorithm will produce the residue for any size input. It is des…
3874 \hspace{3mm}2.1 Use algorithm fast\_mp\_montgomery\_reduce instead. \\
3907 This algorithm reduces the input $x$ modulo $n$ in place using the Montgomery reduction algorithm. …
3908 on algorithm 14.32 of \cite[pp.601]{HAC} except it merges the multiplication of $\mu n \beta^t$ wit…
3909 restrictions on this algorithm are fairly easy to adapt to. First $0 \le x < n^2$ bounds the input…
3910 for the Barrett algorithm. Additionally if $n > 1$ and $n$ is odd there will exist a modular inver…
3911 advance of this algorithm. Finally the variable $k$ is fixed and a pseudonym for $n.used$.
3913 Step 2 decides whether a faster Montgomery algorithm can be used. It is based on the Comba techniq…
3914 the size of the input. This algorithm is discussed in ~COMBARED~.
3916 Step 5 is the main reduction loop of the algorithm. The value of $\mu$ is calculated once per iter…
3920 Using a quick inspection this algorithm requires $n$ single precision multiplications for the outer…
3926 This is the baseline implementation of the Montgomery reduction algorithm. Lines @30,digs@ to @35,…
3936 nature of the inner loop. The Barrett reduction algorithm requires two slightly modified multiplie…
3937 technique. The Montgomery reduction algorithm cannot directly use the Comba technique to any signi…
3944 With this change in place the Montgomery reduction algorithm can be performed with a Comba style mu…
3945 the speed of the algorithm.
3992 This algorithm will compute the Montgomery reduction of $x$ modulo $n$ using the Comba technique. …
3993 faster than algorithm mp\_montgomery\_reduce and algorithm mp\_reduce (\textit{Barrett reduction}).…
3994 on the input as the baseline reduction algorithm. An additional two restrictions are imposed on th…
3995 …ate $MP\_WARRAY > 2k +1$ and $n < \delta$. When $\beta = 2^{28}$ this algorithm can be used to r…
4026 To calculate the variable $\rho$ a relatively simple algorithm will be required.
4051 This algorithm will calculate the value of $\rho$ required within the Montgomery reduction algorith…
4082 …nal congruence is reproduced, thus concluding the proof. The following algorithm is based on this…
4108 This algorithm will reduce $x$ modulo $n - k$ and return the residue. If $0 \le x < (n - k)^2$ the…
4129 sum in step 4 will exceed $n - k$. In practice fewer than three passes of the algorithm are requir…
4164 is considerably larger than $(n - k - 1)^2 = 63504$ the algorithm still converges on the modular re…
4169 On the surface this algorithm looks like a very expensive algorithm. It requires a couple of subtr…
4170 modular reductions. The usefulness of this algorithm becomes exceedingly clear when an appropriate…
4188 as well be a single digit. The smaller the value of $k$ is the faster the algorithm will be.
4191 …stricted Diminished Radix algorithm can quickly reduce an input modulo a modulus of the form $n = …
4192 an input $x$ within the range $0 \le x < n^2$ using only a couple passes of the algorithm demonstra…
4193 of this algorithm has been optimized to avoid additional overhead associated with a division by $\b…
4194 of $x$ and $q$. The resulting algorithm is very efficient and can lead to substantial improvements…
4229 This algorithm will perform the Dimished Radix reduction of $x$ modulo $n$. It has similar restric…
4232 This algorithm essentially implements the pseudo-code in figure~\ref{fig:DR} except with a slight o…
4238 … larger than $n$ another pass of the algorithm is required. First $n$ is subtracted from $x$ and …
4244 the algorithm will resume if further reduction passes are required. In theory it could be placed a…
4248 …p on line @61,for@ performs the bulk of the work (\textit{corresponds to step 4 of algorithm 7.11})
4249 in this algorithm.
4254 Since the algorithm is only valid if both $x$ and $n$ are greater than zero an unsigned comparison …
4256 … destination of the subtraction is the larger of the inputs the call to algorithm s\_mp\_sub canno…
4260 To setup the restricted Diminished Radix algorithm the value $k = \beta - n_0$ is required. This a…
4282 Another algorithm which will be useful is the ability to detect a restricted Diminished Radix modul…
4305 This algorithm determines if a value is in Diminished Radix form. Step 1 rejects obvious cases whe…
4306 …ll but the first digit to see if they are equal to $\beta - 1$. If the algorithm manages to get to
4312 …ted Diminished Radix algorithm allows modular reductions to be performed when the modulus is of th…
4313 is a straightforward adaptation of algorithm~\ref{fig:DR}.
4315 In general the restricted Diminished Radix reduction algorithm is much faster since it has consider…
4316 algorithm is much faster than either Montgomery or Barrett reduction when the moduli are of the app…
4344 This algorithm quickly reduces an input $a$ modulo an unrestricted Diminished Radix modulus $n$. D…
4345 shift which makes the algorithm fairly inexpensive to use.
4349 The algorithm mp\_count\_bits calculates the number of bits in an mp\_int which is used to find the…
4358 To setup this reduction algorithm the value of $k = 2^p - n$ is required.
4381 This algorithm computes the value of $k$ required for the algorithm mp\_reduce\_2k. By making a te…
4421 This algorithm quickly determines if a modulus is of the form required for algorithm mp\_reduce\_2k…
4448 For almost every cryptographic algorithm Montgomery reduction is the algorithm of choice. The one …
4450 …und and shared amongst users. These primes will allow the Diminished Radix algorithm to be used in
4457 $\left [ 3 \right ]$ & Prove that the ``trick'' in algorithm mp\_montgomery\_setup actually \\
4460 $\left [ 2 \right ]$ & Devise an algorithm to reduce modulo $n + k$ for small $k$ quickly. \\
4462 $\left [ 4 \right ]$ & Prove that the pseudo-code algorithm ``Diminished Radix Reduction'' \\
4476 A trivial algorithm would simply multiply $a$ against itself $b - 1$ times to compute the exponenti…
4480 Fortunately there is a very simple algorithm based on the laws of exponents. Recall that $lg_a(a^b…
4499 be computed in an auxilary variable. Consider the following equivalent algorithm.
4522 This algorithm starts from the most significant bit and works towards the least significant bit. W…
4526 … let $b = 101100_2 \equiv 44_{10}$. The following chart demonstrates the actions of the algorithm.
4545 …simplified it is equal $a^{44}$ which is the desired exponentiation. This particular algorithm is
4549 The first algorithm in the series of exponentiation algorithms will be an unbounded algorithm where…
4578 This algorithm computes the value of $a$ raised to the power of a single digit $b$. It uses the le…
4579 quickly compute the exponentiation. It is loosely based on algorithm 14.79 of HAC \cite[pp. 615]{H…
4599 slower than squaring. Recall from the previous algorithm that $b_{i}$ refers to the $i$'th bit of …
4600 …ponent of $b$. For $k = 1$ the definitions are synonymous and for $k > 1$ algorithm~\ref{fig:KARY}
4602 …exponent. Consider the following modification to the basic left to right exponentiation algorithm.
4627 precomputed this algorithm requires only $t$ multiplications and $tk$ squarings. The table can be …
4628 $2^{k - 1} + 1$ multiplications. This algorithm assumes that the number of bits in the exponent is…
4629 However, when it is not the remaining $0 < x \le k - 1$ bits can be handled with algorithm~\ref{fig…
4631 Suppose $k = 4$ and $t = 100$. This modified algorithm will require $109$ multiplications and $408…
4632 original algorithm would on average have required $200$ multiplications and $400$ squrings to compu…
4638 …nd compares the number of multiplication and squarings required against algorithm~\ref{fig:LTOR}.
4663 A simple modification to the previous algorithm is only generate the upper half of the table in the…
4665 algorithm values of $g$ in the range $0 \le g < 2^{k-1}$ must be avoided.
4667 …f $k$ for various exponent sizes and compares the work required against algorithm~\ref{fig:KARY}.
4716 Similar to the previous algorithm this algorithm must have a special handler when fewer than $k$ bi…
4717 algorithm requires the same number of squarings it can potentially have fewer multiplications. The…
4720 …000_2 \equiv 31432_{10}$ with $k = 3$ using both algorithms. The first algorithm will divide the …
4721 …ords $b \equiv \left ( 111, 101, 011, 001, 000 \right )_{2}$. The second algorithm will break the
4737 … the actual modular exponentiation algorithm can be written a wrapper algorithm must be written fi…
4739 …uted using the modular inverse (\textit{see \ref{sec;modinv}}). If no inverse exists the algorithm
4756 \hspace{3mm}3.1 Compute $y \equiv g^{x} \mbox{ (mod }p\mbox{)}$ via algorithm mp\_exptmod\_fast. \\
4758 \hspace{3mm}4.1 Compute $y \equiv g^{x} \mbox{ (mod }p\mbox{)}$ via algorithm s\_mp\_exptmod. \\
4767 The first algorithm which actually performs modular exponentiation is algorithm s\_mp\_exptmod. It…
4768 which uses Barrett reduction to reduce the product modulo $p$. The second algorithm mp\_exptmod\_f…
4770 algorithm since their arguments are essentially the same (\textit{two mp\_ints and one mp\_digit}).…
4775 negative the algorithm tries to perform a modular exponentiation with the modular inverse of the ba…
4776 the modular inverse of $G$ and $tmpX$ is assigned the absolute value of $X$. The algorithm will re…
4779 If the exponent is positive the algorithm resumes the exponentiation. Line @63,dr_@ determines if …
4789 Line @69,if@ determines if the fast modular exponentiation algorithm can be used. It is allowed if…
4790 the slower s\_mp\_exptmod algorithm is used which uses Barrett reduction.
4892 This algorithm computes the $x$'th power of $g$ modulo $p$ and stores the result in $y$. It takes …
4893 algorithm to keep the product small throughout the algorithm.
4900 the rest of the algorithm more efficient. The first element of the table at $2^{winsize - 1}$ is f…
4911 …\item When $mode = 2$ the algorithm is in the middle of forming a window and new bits are appended…
4932 algorithm from having to perform trivial squaring and reduction operations before the first non-zer…
4938 a Left-to-Right algorithm is used to process the remaining few bits.
4995 Integer division aside from modular exponentiation is the most intensive algorithm to compute. Lik…
4996 the basis of this algorithm is the long-hand division algorithm taught to school children. Through…
4998 let $r$ represent the remainder $r = y - x \lfloor y / x \rfloor$. The following simple algorithm …
5024 As children we are taught this very simple algorithm for the case of $\beta = 10$. Almost instinct…
5188 This algorithm will calculate quotient and remainder from an integer division given a dividend and …
5195 divisor $y$ and dividend $x$ are made as well. The core of the division algorithm is an unsigned d…
5199 At this point the division algorithm can begin producing digits of the quotient. Recall that maxim…
5215 algorithm~\ref{fig:raddiv}} and then subsequently add a multiple of the divisor if the quotient was…
5218 remainder. An important aspect of this algorithm seemingly overlooked in other descriptions such a…
5225 The implementation of this algorithm differs slightly from the pseudo code presented previously. I…
5227 algorithm with only the quotient is
5239 exactly what is required. For the algorithm to operate $k$ must equal $lg(\beta) - 1$ and when it …
5245 The conditional ``continue'' on line @186,continue@ is used to prevent the algorithm from reading p…
5246 algorithm eliminates multiple non-zero digits in a single iteration. This ensures that $x_i$ is al…
5281 This algorithm initiates a temporary mp\_int with the value of the single digit and uses algorithm …
5288 The single digit subtraction algorithm mp\_sub\_d is essentially the same except it uses mp\_sub to…
5292 multiplication algorithm. Essentially this algorithm is a modified version of algorithm s\_mp\_mul…
5325 This algorithm quickly multiplies an mp\_int by a small single digit value. It is specially tailor…
5326 Unlike the full multiplication algorithms this algorithm does not require any significnat temporary…
5334 Like the single digit multiplication algorithm, single digit division is also a fairly common algor…
5335 divisor is only a single digit a specialized variant of the division algorithm can be used to compu…
5346 2. If $b = 3$ then use algorithm mp\_div\_3 instead. \\
5370 This algorithm divides the mp\_int $a$ by the single mp\_digit $b$ using an optimized approach. Es…
5371 algorithm another digit of the dividend is reduced and another digit of quotient produced. Provide…
5374 If the divisor $b$ is equal to three a variant of this algorithm is used which is called mp\_div\_3…
5380 Like the implementation of algorithm mp\_div this algorithm allows either of the quotient or remain…
5381 … is not required. This allows a trivial single digit modular reduction algorithm, mp\_mod\_d to b…
5398 simply $f'(x) = nx^{n - 1}$. Of particular importance is that this algorithm will be used over the…
5400 algorithm the $n$'th root $b$ of an integer $a$ is desired such that $b^n \le a$.
5439 This algorithm finds the integer $n$'th root of an input using the Newton-Raphson approach. It is …
5444 The initial value of the approximation is t$2 = 2$ which allows the algorithm to start with very sm…
5445 root. Ideally this algorithm is meant to find the $n$'th root of an input where $n$ is bounded by …
5452 …es as starting points to find factors of a composite integer. In this case the algorithm presented
5479 This algorithm produces a pseudo-random integer of $b$ digits. By ensuring that the first digit is…
5555 This algorithm will read an ASCII string and produce the radix-$\beta$ mp\_int representation of th…
5556 string to indicate the value is negative, otherwise it is assumed to be positive. The algorithm w…
5557 and will stop when it reads a character it cannot map the algorithm stops reading characters from t…
5563 Generating radix-$n$ output is fairly trivial with a division and remainder algorithm.
5597 This algorithm computes the radix-$r$ representation of an mp\_int $a$. The ``digits'' of the repr…
5623 …sential components in several key cryptographic algorithms such as the RSA public key algorithm and
5655 This algorithm will quickly converge on the greatest common divisor since the residue $r$ tends dim…
5681 The algorithm in figure~\ref{fig:gcd2} will eventually terminate since $b \ge a$ the subtraction in…
5683 …or (\textit{until the last iteration}) and in the last iteration of the algorithm $b = 0$, therefo…
5684 second to last iteration of the algorithm $b = a$ and clearly $(a, a) = a$ which concludes the proo…
5686 As a matter of practicality algorithm \ref{fig:gcd1} decreases far too slowly to be useful. Specia…
5687 $b - a$ is still very much larger than $a$. A simple addition to the algorithm is to divide $b - a…
5725 This algorithm is based on the first except it removes powers of $p$ first and inside the main loop…
5736 … so far cannot handle inputs which are zero or negative. The following algorithm can handle all i…
5778 This algorithm will produce the greatest common divisor of two mp\_ints $a$ and $b$. The algorithm…
5784 $a$ and $b$ respectively and the algorithm will proceed to reduce the pair.
5812 … are guaranteed to be an odd integer before hitting the main body of the algorithm. The while loop
5845 This algorithm computes the least common multiple of two mp\_int inputs $a$ and $b$. It computes t…
5906 further details.} will be used to derive an efficient Jacobi symbol algorithm. Where $p$ is an odd…
5946 factors of $p$ do not have to be known. Furthermore, if $(a, p) = 1$ then the algorithm will termi…
5990 …his algorithm computes the Jacobi symbol for an arbitrary positive integer $a$ with respect to an …
5991 is based on algorithm 2.149 of HAC \cite[pp. 73]{HAC}.
6007 …are handled at the very beginning to simplify the algorithm. If the input is non-trivial the algo…
6012 bit of $k$ is required, however, it makes the algorithm simpler to follow to perform an addition. I…
6019 Finally, if $a1$ does not equal one the algorithm must recurse and compute $\left ( {p' \over a'} \…
6048 $a$ modulo $p$. The extended Euclidean algorithm (Knuth \cite[pp. 342]{TAOCPV2}) can be used to so…
6049 However, instead of using that algorithm directly a variant known as the binary Extended Euclidean …
6050 binary approach is very similar to the binary greatest common divisor algorithm except it will prod…
6063 2. If $b_0 \equiv 1 \mbox{ (mod }2\mbox{)}$ then use algorithm fast\_mp\_invmod. \\
6103 This algorithm computes the modular multiplicative inverse of an integer $a$ modulo an integer $b$.…
6104 extended binary Euclidean algorithm from HAC \cite[pp. 608]{HAC}. It has been modified to only com…
6110 …ven through nine are very similar to the binary greatest common divisor algorithm mp\_gcd. In thi…
6111 the other variables to the Diophantine equation are solved. The algorithm terminates when $u = 0$ …
6117 If $v$, the greatest common divisor of $a$ and $b$ is not equal to one then the algorithm will repo…
6129 The algorithm fast\_mp\_invmod is a direct adaptation of algorithm mp\_invmod with all all steps in…
6140 prime the algorithm may be incorrect.
6152 of the primes less than $\sqrt{n} + 1$ the algorithm cannot prove if a candidate is prime. However…
6186 This algorithm attempts to determine if a candidate integer $n$ is composite by performing trial di…
6190 The algorithm defaults to a return of $0$ in case an error occurs. The values in the prime table a…
6231 This algorithm determines whether an mp\_int $a$ is a Fermat prime to the base $b$ or not. It uses…
6238 candidate integers. The algorithm is based on the observation that if $n - 1 = 2^kr$ and if $b^r …
6273 This algorithm performs one trial round of the Miller-Rabin algorithm to the base $b$. It will set…
6276 …b^r$ is congruent to $\pm 1$ then the algorithm cannot prove if $a$ is composite or not. Otherwis…
6277 …y when $y \equiv -1$. If $y^2 \equiv 1$ and $y \nequiv \pm 1$ then the algorithm can report that …
6278 is provably composite. If the algorithm performs $s - 1$ squarings and $y \nequiv -1$ then $a$ is …