椭圆曲线

[编程题]椭圆曲线

热度指数：181 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

椭圆曲线加密算法是在椭圆曲线有限域上进行加密的算法，一般的椭圆曲线为 $E_{p}(a,b): y^2=x^3+ax+b$ ，其中p为质数。

椭圆曲线上的点的运算满足以下规则:

曲线上A、B不同两点相加，过A、B两点画一条直线，找到直线与椭圆曲线的交点，交点关于x轴对称位置的点，定义为A+B，即为加法。如下图所示：A + B = C
相同点A与A相加，过A点做切线，与椭圆曲线的交点，交点关于x轴对称位置的点，定义为A + A，即2A，即为二倍运算。

$E_{p}(a,b): y^2=x^3+ax+b$ ， $P(x_1,x_2),Q(x_2,y_2),R(x_3,y_3)$ ，其中R=P+Q，有

$x_3\equiv k^2-x_1-x_2\: (mod\: p)$

$y_3\equiv k(x_1-x_3)-y_1\: (mod\: p)$

$若P=Q,则k=\frac{3x_1^2+a}{2y_1}\: (mod\: p)$

$若P\neq Q,则k=\frac{y_2-y_1}{x_2-x_1}\: (mod\: p)$

现有 $E_p(1,1),其中p=1000000007$ ，牛牛得到了点 $P(x_1,y_1)$ ，你能告诉她 $\ nP$ 是多少吗。

示例1

输入

(0,1),3

输出

(72,611)

备注:

，

算法知识视频讲解

牛客516598323号

参考答案：

/**
 *  * struct Point {
 *  * int x;
 *  * int y;
 *  * };
 *  */

class Solution
{
    uint64_t Modp = 1000000007;
    uint32_t Inv(uint64_t num)
    {
        uint32_t result = 1, Power = 1000000005;
        while (Power > 0)
        {
            if (Power & 1)
                result = result * num % Modp;
            Power >>= 1;
            num = num * num % Modp;
        }
        return result;
    }
    Point TwoTimesPoint(Point P)
    {
        Point R;
        uint64_t k = (3 * (uint64_t)P.x * P.x + 1) % Modp * Inv(2 * P.y % Modp) % Modp;
        R.x = (k * k + 2 * Modp - 2 * P.x) % Modp;
        R.y = (k * (P.x + Modp - R.x) + Modp - P.y) % Modp;
        return R;
    }
    Point TwoPointsAdd(Point P, Point Q)
    {
        Point R;
        uint64_t k = (Q.y + Modp - P.y) * Inv((Q.x + Modp - P.x) % Modp) % Modp;
        R.x = (k * k % Modp + 2 * Modp - P.x - Q.x) % Modp;
        R.y = (k * (P.x + Modp - R.x) + Modp - P.y) % Modp;
        return R;
    }

public:
    /**
   * 
   * @param P Point类 
   * @param n int整型 
   * @return Point类
   */
    Point NTimesPoint(Point P, int n)
    {
        // write code here
        Point PointTimes[30] = {P}, NP;
        uint8_t NBin[30], Leath = 0, Flag = 0;
        for (; n > 0; Leath += 1)
        {
            NBin[Leath] = n & 1;
            n >>= 1;
        }
        for (uint8_t i = 1; i < Leath; i += 1)
            PointTimes[i] = TwoTimesPoint(PointTimes[i - 1]);
        while (!NBin[Flag++])
            ;
        NP = PointTimes[Flag - 1];
        for (uint8_t i = Flag; i < Leath; i++)
        {
            if (NBin[i])
                NP = TwoPointsAdd(NP, PointTimes[i]);
        }
        return NP;
    }
};

发表于 2020-10-20 20:31:30 回复(0)