题意整理:

题目给出一个椭圆曲线 Ep(1,1):y2=x3+x+1E_p(1,1):y^2=x^3+x+1Ep(1,1):y2=x3+x+1,其中p=1000000007p=1000000007p=1000000007,以及一个点P(x,y)P(x,y)P(x,y),求解nPnPnP的值。 椭圆曲线上的加法公式题目已经给出,既: 图片说明 需要注意的是,其中出现了模p的除法,既模逆元,这部分模数相关的知识此处不做详细介绍,只给出一个求模的方法。 利用拓展欧几里得算法和费马小定理,可以得出对除法求模的递归方法, 当p是素数时,记Inv(n)Inv(n)Inv(n)为n对p的除法求模结果,有

Inv(n)=(pp/n)Inv(p%n)Inv(n) = (p - p / n) * In***) % p Inv(n)=(pp/n)Inv(p%n),而递归终条件为 Inv(1)=1Inv(1)=1Inv(1)=1 知道这部分知识后,就可以对本题进行求解了。

方法一:暴力累加(超时)

核心思想:

题目已经给出了椭圆曲线上的加法公式,而椭圆曲线的加法满足结合律,所以nPnPnP实际上就是n个P结点相加即可

核心代码:

class Solution {
public:
    long long mod = 1000000007;
    int Inv(long long n) {
        //除法求模算法
        if(n == 1) return 1;
        return (mod - mod / n) * Inv(mod % n) % mod;
    }
    
    Point AddPoint(Point P, Point Q) {
        //两点相加算法
        uint64_t k;
        if(P.x == Q.x && P.y == Q.y) {
            //此时为2P
            k = (3 * (long long)P.x * P.x + 1) % mod * Inv(2 * P.y % mod) % mod;
        } else {
            k = (Q.y - P.y + mod) * Inv((Q.x - P.x + mod) % mod) % mod;
        }
        long long x = (k * k + 2 * mod - P.x - Q.x) % mod;
        long long y = (k * (P.x + mod - x) + mod - P.y) % mod;
        return Point((int)x, (int)y);
    }

    Point NTimesPoint(Point P, int n) {
        Point ans = P;
        for(int i = 1; i < n; ++i) {
            ans = AddPoint(ans, P);
        }
        return ans;
    }
};

复杂度分析:

时间复杂度:O(nlogn)O(nlogn)O(nlogn)。既对n个P进行累加的开销,每次对Inv(n)Inv(n)Inv(n)的计算开销为O(logn)O(logn)O(logn),进行n1n-1n1

空间复杂度:O(logn)O(logn)O(logn),主要是计算Inv(n)Inv(n)Inv(n)时的栈开销的上限,其他部分的开销均为常数个变量

方法二:

核心思想:

方法一时间复杂度很高,因为只是一直累加,且满足结合律,实际上对于大数的加法都有通用的方法,既快速幂。 图片说明

核心代码:

class Solution {
public:
    long long mod = 1000000007;
    int Inv(long long n) {
        //除法求模算法
        if(n == 1) return 1;
        return (mod - mod / n) * Inv(mod % n) % mod;
    }
    
    Point AddPoint(Point P, Point Q) {
        //两点相加算法
        uint64_t k;
        if(P.x == Q.x && P.y == Q.y) {
            //此时为2P
            k = (3 * (long long)P.x * P.x + 1) % mod * Inv(2 * P.y % mod) % mod;
        } else {
            k = (Q.y - P.y + mod) * Inv((Q.x - P.x + mod) % mod) % mod;
        }
        long long x = (k * k + 2 * mod - P.x - Q.x) % mod;
        long long y = (k * (P.x + mod - x) + mod - P.y) % mod;
        return Point((int)x, (int)y);
    }

    Point NTimesPoint(Point P, int n) {
        Point ans;
        bool flag = true;
        while(n > 0) {
            //快速幂
            if(n % 2 == 1) {
                //第一次赋值时令ans=P,因为此处不能让ans=(0,0),椭圆曲线加法不存在零元
                ans = flag ? P : AddPoint(ans, P);
                flag = false;
            }
            n /= 2;
            P = AddPoint(P, P);
        }
        return ans;
    }
};

复杂度分析:

时间复杂度:O((logn)2)O((logn)^2)O((logn)2),n每次迭代都减小一半,故迭代次数为O(logn)O(logn)O(logn),每次对Inv(n)Inv(n)Inv(n)的计算开销为O(logn)O(logn)O(logn),总开销为O((logn)2)O((logn)^2)O((logn)2)

空间复杂度:O(logn)O(logn)O(logn),主要是计算Inv(n)Inv(n)Inv(n)时的栈开销的上限,其他部分的开销均为常数个变量