题解 | #椭圆曲线#

椭圆曲线

http://www.nowcoder.com/practice/ea3e46bc7bc64879ba6fa1737b5d4df7

题意整理：

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

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

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

核心思想：

题目已经给出了椭圆曲线上的加法公式，而椭圆曲线的加法满足结合律，所以 $n P$ 实际上就是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 (n l o g n)$ 。既对n个P进行累加的开销,每次对 $I n v (n)$ 的计算开销为 $O (l o g n)$ ,进行 $n - 1$ 次

空间复杂度： $O (l o g n)$ ,主要是计算 $I n v (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;
    }
};