Skip to content
The Chat Archive
gpt-3.5-turbo-0301· OpenAI WildChat-4.8M (AI2)

Перепиши код на С++ import time import random import math A = 907898232 B = 317181867…

  1. 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_t
    

    def 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 % p
    

    def 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 True
    

    def 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)

  2. 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; }