Перепиши код на С++ import time import random import math A = 907898232 B = 317181867…
- User
Перепиши код на С++ import time import random import math
A = 907898232 B = 317181867
def elliptic_curve(x, y, p): return (y 2) % p == (x 3 + (A % p) * x + (B % p)) % p
def print_curve(p): print(f"y^2 = x^3 + {A % p} * x + {B % p} [p = {p}]")
def euclidean_algo(a, b): s, old_s = 0, 1 t, old_t = 1, 0 r, old_r = b, a
while r != 0: quotient = old_r // r old_r, r = r, old_r - quotient * r old_s, s = s, old_s - quotient * s old_t, t = t, old_t - quotient * t return old_r, old_s, old_tdef inverse(n, p): gcd, x, y = euclidean_algo(n, p) assert (n * x + p * y) % p == gcd
if gcd != 1: return -1 else: return x % pdef add_points(p1, p2, p): if p1 == (0, 0): return p2 elif p2 == (0, 0): return p1 elif p1[0] == p2[0] and p1[1] != p2[1]: return (0, 0)
if p1 == p2: s = ((3 * p1[0] 2 + (A % p)) * inverse(2 * p1[1], p)) % p else: s = ((p1[1] - p2[1]) * inverse(p1[0] - p2[0], p)) % p x = (s 2 - 2 * p1[0]) % p y = (p1[1] + s * (x - p1[0])) % p return (x, -y % p)def order_point(point, p): i = 1 check = add_points(point, point, p) while check != (0, 0): check = add_points(check, point, p) i += 1 return i
def is_prime_number(number): if number < 2: return False if number == 2: return True if number % 2 == 0: return False
for i in range(3, int(math.sqrt(number)) + 1, 2): if number % i == 0: return False return Truedef get_next_prime_number(start): number = start while not is_prime_number(number): number += 1 return number
def find_opt_p(p, time_limit): last_p = p i = 0 while True: i += 1 print(f'Iteration {i}:') print_curve(p) points = [] start = time.time() cnt = 0 for x in range(0, p): for y in range(0, p): cnt += 1 if elliptic_curve(x, y, p): points.append((x, y)) if cnt % 1000 == 0: cnt = 0 if time.time() - start > time_limit: break if time.time() - start > time_limit: print('------------Selection is over------------') print(f'[RESULT]: y^2 = x^3 + {A % last_p} * x + {B % last_p} [p = {last_p}]') break cnt_points = len(points) print("Order curve = {0}".format(cnt_points)) point = random.choice(points) print("Order point {0}: {1}".format(point, order_point(point, p))) print("Time: {} sec.".format(time.time() - start)) print("-----------------------------------------") last_p = p p = get_next_prime_number(p + 4500)
if name == 'main': start_p = 191 time_lim = 600 find_opt_p(start_p, time_lim)
- Assistant
#include #include #include #include #include
using namespace std;
int A = 907898232; int B = 317181867;
bool elliptic_curve(int x, int y, int p) { return (y * y) % p == (x * x * x + (A % p) * x + (B % p)) % p; }
void print_curve(int p) { cout << "y^2 = x^3 + " << A % p << " * x + " << B % p << " [p = " << p << "]" << endl; }
int gcd(int a, int b, int &x, int &y) { int d; if (b == 0) { x = 1; y = 0; return a; } int x1, y1; d = gcd(b, a % b, x1, y1); x = y1; y = x1 - y1 * (a / b); return d; }
int inverse(int n, int p) { int x, y; int d = gcd(n, p, x, y); if (d != 1) { return -1; } return (x % p + p) % p; }
pair<int, int> add_points(pair<int, int> p1, pair<int, int> p2, int p) { if (p1.first == 0 && p1.second == 0) { return p2; } if (p2.first == 0 && p2.second == 0) { return p1; } if (p1.first == p2.first && p1.second != p2.second) { return make_pair(0, 0); }
int s, x, y; if (p1 == p2) { s = ((3 * p1.first * p1.first + (A % p)) * inverse(2 * p1.second, p)) % p; } else { s = ((p1.second - p2.second) * inverse(p1.first - p2.first, p)) % p; } x = (s * s - p1.first - p2.first) % p; y = (p1.second + s * (x - p1.first)) % p; return make_pair(x, -y % p);}
int order_point(pair<int, int> point, int p) { int i = 1; pair<int, int> check = add_points(point, point, p); while (check != make_pair(0, 0)) { check = add_points(check, point, p); i++; } return i; }
bool is_prime_number(int number) { if (number < 2) { return false; } if (number == 2) { return true; } if (number % 2 == 0) { return false; }
for (int i = 3; i <= sqrt(number); i += 2) { if (number % i == 0) { return false; } } return true;}
int get_next_prime_number(int start) { int number = start; while (!is_prime_number(number)) { number++; } return number; }
void find_opt_p(int p, int time_limit) { int last_p = p; int i = 0; while (true) { i++; cout << "Iteration " << i << ":" << endl; print_curve(p); vector<pair<int, int>> points; clock_t start = clock(); int cnt = 0; for (int x = 0; x < p; x++) { for (int y = 0; y < p; y++) { cnt++; if (elliptic_curve(x, y, p)) { points.push_back(make_pair(x, y)); } } if (cnt % 1000 == 0) { cnt = 0; if ((double)(clock() - start) / CLOCKS_PER_SEC > time_limit) { break; } } } if ((double)(clock() - start) / CLOCKS_PER_SEC > time_limit) { cout << "------------Selection is over------------" << endl; cout << "[RESULT]: y^2 = x^3 + " << A % last_p << " * x + " << B % last_p << " [p = " << last_p << "]" << endl; break; } int cnt_points = points.size(); cout << "Order curve = " << cnt_points << endl; pair<int, int> point = points[rand() % cnt_points]; cout << "Order point (" << point.first << ", " << point.second << "): " << order_point(point, p) << endl; cout << "Time: " << (double)(clock() - start) / CLOCKS_PER_SEC << " sec." << endl; cout << "-----------------------------------------" << endl; last_p = p; p = get_next_prime_number(p + 4500); } }
int main() { int start_p = 191; int time_lim = 600; find_opt_p(start_p, time_lim); return 0; }