52 Things: Number 23: Write a C program to implement Montgomery arithmetic.
52件事：第23件：写一个C程序来实现Montgomery算术。 This is the latest in a series of blog posts to address the list of这是一系列博客文章中最新的一篇'52 Things Every PhD Student Should Know'
“每个博士生都应该知道的52件事” to do Cryptography: a set of questions compiled to give PhD candidates a sense of what they should know by the end of their first year. This next blog continues the topic of 'Cryptographic Implementation Details'.
做密码学：一组问题，旨在让博士生在第一年结束时了解他们应该知道什么。下一篇博客继续主题“加密实现细节”。
In this post I will aim to compliment what we saw last week regarding the more theoretical aspects of Montgomery arithmetic with a practical implementation of it. The implementation is written in C and written for a computer with a word size of 64 bits. The moduls m can therefore be as large as 264 – 1 and a and b can be as large as m – 1. We will take r = 264. As in the previous post, most of what is given here is derived from [1] so please refer to this for more information.
在这篇文章中，我将用蒙哥马利算法的实际实现来补充我们上周看到的关于蒙哥马利算法的更多理论方面的内容。该实现是用C编写的，是为64位的计算机编写的。因此，模m可以大到2 64 –1，a和b可以大到m–1。我们将取r＝2 64 。与上一篇文章一样，这里给出的大部分内容都来源于[1]，因此请参阅本文以获取更多信息。 You will remember from the last blog post, that four steps were given to the algorithm (please see post for a full description of the algorithm if this is hazy). For the purposes of our implementation, we will eamine each of these stages separately.
你会记得从上一篇博客文章中，算法有四个步骤（如果不清楚，请参阅文章中对算法的完整描述）。为了我们的实施，我们将分别对这些阶段中的每一个阶段进行分析。
1. The GCD Operation 1.GCD操作 This function uses the binary extended gcd operation to find the integers r-1 and m’ such that rr-1 = 1 + mm’. These integers are required for the subsequent steps of the Montgomery reduction. The algorithm takes r and m and pointers to values r-1 and m’ which the algorithm derives. This is done using the extended gcd algorithm which could be implemented in a number of ways (the purpose of which this blog is not about) and I refer the reader to [1] or [2] for detailed descriptions of it.
此函数使用二进制扩展gcd运算来查找整数r -1 和m'，使得rr -1 =1+mm'。这些整数是Montgomery归约的后续步骤所必需的。该算法获取r和m以及指向该算法导出的值r -1 和m'的指针。这是使用扩展的gcd算法完成的，该算法可以通过多种方式实现（本博客不涉及其目的），我请读者参考[1]或[2]了解其详细描述。
2. Transform the Multipliers
2.变换乘法器 The second stage aims to compute abar = ar mod m and bbar = br mod m. As r = 264, no multiplication is required but only a shifting by 64 bits (due to our selection of r = 264), giving a 128 bit output with 64 0s tailing the value of a or b. The remainder of the division by m is then given as abar or bbar. A function which takes the high 64 bits (x) and the low 64 bits (y) and the value for m (z) and returns the 64 bit result could be written to do this. Such a function could be defined as follows:
第二阶段的目标是计算abar＝ar mod m和bbar＝br mod m。由于r＝2 64 ，不需要乘法，只需要移位64位（由于我们选择了r＝2 64 ），得到128位输出，64 0落后于a或b的值。然后将除以m的余数作为abar或bbar。可以编写一个函数来实现这一点，该函数取高64位（x）和低64位（y）以及m（z）的值并返回64位结果。这种功能可以定义如下：
uint64 modul64(uint64 x, uint64 y, uint64 z);
uint64模64（uint64 x，uint64 y，uint64z）； Where uint64 is a type defined as follows:
其中uint64是如下定义的类型： typedef unsigned long long uint64;
typedef无符号长整型uint64； 3. Montgomery Multiplication
3蒙哥马利乘法 The function which carries out the Montgomery multiplication can be defined as a function which takes the 64 bit values abar, bbar, m and mprine and returns a 64 bit value for the output of the Montgomery multiplication step.
执行Montgomery乘法的函数可以定义为取64位值abar、bbar、m和mprine并返回64位值作为Montgomerly乘法步骤的输出的函数。
The first sub-stage to of the function is to calculate t = abar*bbar. This is done by multiplying abar and bbar together to give a 128 bit product. An additional function could be written to do this which takes abar and bbar and returns two 64bit values, one with the high 64 bits (thi) and one with the low 64 bits (tlow).
函数的第一个子阶段是计算t=abar*bbar。这是通过将abar和bbar相乘得到128位乘积来实现的。可以编写一个额外的函数来实现这一点，该函数采用abar和bbar并返回两个64位值，一个具有高64位（thi），另一个具有低64位（tlow）。
The next stage is the computation of u = (t + (tm’ mod r)m)/r. Here t is a 128 bit integer and m’ is a 64 bit integer. As we mod by r, only the lower 64 bits of tm’ are required, meaning that we can disregard the top 64 bits of t.
下一阶段是u＝（t+（tm'mod r）m）/r的计算。这里t是128位整数，m'是64位整数。当我们用r进行mod时，只需要tm’的低64位，这意味着我们可以忽略t的前64位。
tm = tlo*mprime; // Disregard thi
tm=tlo*mptime；//无视这一点 mulul64(tm, m, &tmmhi, &tmmlo); // Function which performs 128 bit multiplication
mulul64（tm，m，&tmmhi，&tmmlo）；//执行128位乘法的函数
The subsequent multiplication by m gives an output of 128 bits and the addition of t an output of 129 bits, which can be carried out as 128bit + 128bit = 128bit output and compute the carry separately. In C:
随后乘以m得到128位的输出，加上t得到129位的输出。这可以作为128位+128位=128位的输出来执行，并单独计算进位。在C:
ulo = tlo + tmmlo;
ulo=tlo+tmmlo； uhi = thi + tmmhi;
uhi=thi+tmmhi；
if (ulo < tlo) uhi = uhi +1; // test for overflow from ulo and add if necessary to uhi
如果（ulo<tlo）uhi=uhi+1；//测试ulo是否溢出，必要时添加到uhi
ov = (uhi < thi) | ((uhi == thi) & (ulo < tlo)); // check for carry
ov=（uhi＜thi）|（（uhi＝＝thi）&（ulo＜tlo））；//检查进位
The last step is the calculation of if(u >=m) then return u – m; else return u. This is shown below:
最后一步是计算如果（u>=m），则返回u–m；否则返回u。如下所示： ulo = uhi; ulo=uhi； uhi = 0; uhi＝0；
if(ov > 0 || ulo >= m) // test if there was overflow or ulo is higher that
如果（ov>0||ulo>=m）//测试是否存在溢出或ulo高于
ulo = ulo – m;
ulo=ulo–m；
return ulo; 返回ulo；
4. The Inverse Transformation
4.逆变换 In the final stage we compute ur-1 mod m which is the product of a and b modulo m. This could be done by calling the following functions:
在最后阶段，我们计算ur -1 mod m，它是a和b模m的乘积。这可以通过调用以下函数来完成：
mulul64(p, rinv, &phi, &plo); // performs multiplication and returns two 64 bit values phi and plo
mulul64（p，rinv，&phi，&plo）；//执行乘法运算并返回两个64位值phi和plo
p = modul64(phi, plo, m); // returns value of 128bit input mod m
p=模64（phi，plo，m）；//返回128位输入mod m的值
This gives the output p which is the 64 bit output equal to ab mod m and the Montgomery reduction is complete.
这给出了等于ab mod m的64位输出的输出p，并且Montgomery归约完成。 标签：23,Things,Number,Montgomery,64,ulo,128,uhi,mod From： https://www.cnblogs.com/3cH0-Nu1L/p/18106119