#M079. 素域椭圆曲线数点

    ID: 5708 传统题 2000ms 512MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>CF3200NOI/NOI+/CTS椭圆曲线数点Hasse 界椭圆曲线二次扭曲椭圆曲线群运算BSGS随机采样Tonelli–Shanks 算法哈希表模逆元快速幂快速乘防溢出难度分类

素域椭圆曲线数点

题目描述

这是一道模板题。

给定质数 p≥5p\ge 5,a,b∈Fpa,b\in\mathbb{F}_p 满足 4a3+27b2≠04a^3+27b^2\ne 0。

求椭圆曲线 y2z=x3+axz2+bz3y^2z=x^3+axz^2+bz^3 的点的个数。满足方程的一组不全为 00 的 (x,y,z)∈Fp3(x,y,z)\in\mathbb{F}_p^3 称为椭圆曲线上的点,若 λ∈Fp\lambda\in\mathbb{F}_p,λ≠0\lambda\ne 0,那么 (x,y,z)(x,y,z) 和 (λx,λy,λz)(\lambda x,\lambda y,\lambda z) 被考虑为同一个点。

输入格式

一行,三个整数 p,a,bp,a,b,用空格分隔。

输出格式

一行,一个正整数表示答案。

7 1 3
6
318743863128339547 105037157051741234 168782265549960835
318743863620705102

数据范围与提示

保证 5≤p<2605\le p<2^{60},0≤a,b<p0\le a,b<p。